Finitary PCF is not decidable
| Author(s) : | Ralph Loader, |
| Publisher : | N/A |
| Publication Date : | 1996 |
| ISSN : | N/A |
| Abstract : | The question of the decidability of the observational ordering of finitary PCF was raised [5] to give mathematical content to the full abstraction problem for PCF [9, 14]. We show that the ordering is in fact undecidable. This result places limits on how explicit a representation of the fully abstract model can be. It also gives a slight strengthening of the author?s earlier result on typed -definability [6]., |