Incomputability Export

by: C. A. R. Hoare, D. C. S. Allison

ACM Computing Surveys, Vol. 4, No. 3. (1972), pp. 169-178.

[Posts]

View FullText article

ACM, DOI, Rent at DeepDyve

michaelbanks's tags for this article

1972 computability paradox recursion

Reviews [Write a review of this article]

Find related articles from these CiteULike users

michaelbanks

Find related articles with these CiteULike tags

1972, computability, paradox, recursion

Abstract

Russell's logical paradox, formulated in terms of English adjectives, is considered as a convenient starting point for this discussion of incomputability. 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 will 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.

@article{Hoare72b, abstract = {Russell's logical paradox, formulated in terms of English adjectives, is considered as a convenient starting point for this discussion of incomputability. 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 will 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.}, address = {New York, NY, USA}, author = {Hoare, C. A. R. and Allison, D. C. S.}, citeulike-article-id = {5491465}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=356606}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/356603.356606}, doi = {10.1145/356603.356606}, issn = {0360-0300}, journal = {ACM Computing Surveys}, keywords = {1972, computability, paradox, recursion}, number = {3}, pages = {169--178}, posted-at = {2009-08-20 17:56:35}, priority = {2}, publisher = {ACM}, title = {Incomputability}, url = {http://dx.doi.org/10.1145/356603.356606}, volume = {4}, year = {1972} }

RIS record

TY - JOUR ID - Hoare72b L3 - citeulike-article-id:5491465 N2 - Russell's logical paradox, formulated in terms of English adjectives, is considered as a convenient starting point for this discussion of incomputability. 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 will 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. IS - 3 JF - ACM Computing Surveys SN - 0360-0300 AD - New York, NY, USA EP - 178 TI - Incomputability PB - ACM VL - 4 SP - 169 KW - 1972 KW - computability KW - paradox KW - recursion AU - Hoare, CAR AU - Allison, DCS PY - 1972/// UR - http://dx.doi.org/10.1145/356603.356606 ER -

Incomputability Export

Citation Format