
doi: 10.2307/420992
AbstractWe consider the informal concept of “computability” or “effective calculability” and two of the formalisms commonly used to define it, “(Turing)computability” and “(general)recursiveness”. We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas.After a careful historical and conceptual analysis of computability and recursion we make several recommendations in section §7 about preserving theintensionaldifferences between the concepts of “computability” and “recursion.” Specifically we recommend that: the term “recursive” should no longer carry the additional meaning of “computable” or “decidable;” functions defined using Turing machines, register machines, or their variants should be called “computable” rather than “recursive;” we should distinguish the intensional difference between Church's Thesis and Turing's Thesis, and use the latter particularly in dealing with mechanistic questions; the name of the subject should be “Computability Theory” or simplyComputabilityrather than “Recursive Function Theory.”
computability, History of mathematical logic and foundations, recursively enumerable, recursion, Computability and recursion theory
computability, History of mathematical logic and foundations, recursively enumerable, recursion, Computability and recursion theory
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 173 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
