Incomputability

1 September 1972

journal article
Published by Association for Computing Machinery (ACM) in ACM Computing Surveys

Vol. 4 (3) , 169-178
https://doi.org/10.1145/356603.356606

Abstract

Russell's logical paradox, formulated in terms of English adjectives, is cons]dered as a convenient starting point for this discussion of incomputablhty. It is shown to be impossible, under a wide variety of circumstances, to program a function which will determine whether another function written in the same programming language wdl terminate. The theory of types is introduced in an attempt to evade the paradox Finally, it is shown that any language containing conditionals and recursive function definitions, which is powerful enough to program its own interpreter, cannot be used to program its own terminates function.

Keywords

This publication has 2 references indexed in Scilit:

Atoms and Lists
The Computer Journal, 1961
Recursive functions of symbolic expressions and their computation by machine, Part I
Communications of the ACM, 1960