×

Computability and recursion. (English) Zbl 0861.03031

This paper considers the informal concept of “computability” and two of the different (but equivalent) definitions used for it: computable and recursive. This paper examines the origin, exact technical definition, concepts, history, and English meaning of these terms. He also describes how they became fixed in their current roles (e.g., why the field is called ‘recursive function theory’ rather than ‘computability theory’) and the effect their usage has on the non-specialist. After this careful exposition the author makes a bold suggestion: we should stop speaking of the two as they are the same and we should use the term ‘computable’ instead of ‘recursive’ throughout.

MSC:

03Dxx Computability and recursion theory
03-03 History of mathematical logic and foundations
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Volume II: Elements of logic (1960)
[2] Rivista di Matematica 1 pp 256– (1891)
[3] Arithmetices principia, nova methodo exposita pp 83– (1889)
[4] Oxford english dictionary (1989)
[5] DOI: 10.2307/2974762 · Zbl 0833.01016 · doi:10.2307/2974762
[6] Webster’s third new international dictionary of the English language (unabridged) (1993)
[7] From Frege to Godel, a sourcebook in mathematical logic, 1879–1931 (1967)
[8] A. M. Turing’s ACE report of 1946 and other papers pp 106– (1986)
[9] Science News 31 pp 7– (1954)
[10] DOI: 10.2307/1969481 · Zbl 0037.30103 · doi:10.2307/1969481
[11] Computability: An introduction to recursive function theory (1980) · Zbl 0448.03029
[12] Mind 59 pp 433– (1950)
[13] Fundamenta Mathematicae 28 pp 11– (1936)
[14] Annals of the History of Computing 6 pp 139– (1949)
[15] DOI: 10.1090/S0002-9904-1938-06720-1 · Zbl 0018.33803 · doi:10.1090/S0002-9904-1938-06720-1
[16] Machine Intelligence 5 pp 3– (1948)
[17] Journal of Symbolic Logic 2 pp 43– (1937)
[18] Journal of Symbolic Logic 2 pp 42– (1937)
[19] DOI: 10.2307/2269326 · Zbl 0014.38503 · doi:10.2307/2269326
[20] Classical recursion theory (1989)
[21] DOI: 10.2307/2371045 · Zbl 0014.09802 · doi:10.2307/2371045
[22] Lecture notes in mathematics (1980)
[23] Bulletin of the American Mathematical Society 41 pp 332– (1935)
[24] Degrees of unsolvability: Local and global theory (1983) · Zbl 0542.03023
[25] Computability and logic (1974) · Zbl 0298.02003
[26] Mathematical thought from ancient to modern times (1972) · Zbl 0277.01001
[27] Annals ofMathematics 59 pp 379– (1954)
[28] Gödel remembered pp 49– (1987)
[29] Notre Dame Journal of Formal Logic 28 pp 490– (1987)
[30] Proc. sympos. algorithms in modern mathematics and computer science (dedicated to Al-Khowarizimi), Urgench, Khorezm Region, Uzbek, SSSR, 1979 (1981)
[31] DOI: 10.1090/S0273-0979-1981-14920-X · Zbl 0486.03023 · doi:10.1090/S0273-0979-1981-14920-X
[32] DOI: 10.1109/MAHC.1981.10004 · Zbl 05083995 · doi:10.1109/MAHC.1981.10004
[33] Transactions of the American Mathematical Society 108 pp 106– (1963)
[34] Proceedings of the London Mathematical Society 12 pp 245– (1962)
[35] Logic, methodology, and philosophy of science: Proceedings of the 1960 international congress pp 38– (1962)
[36] Transactions of the American Mathematical Society 91 pp 1– (1959)
[37] DOI: 10.1090/S0002-9904-1955-09896-3 · Zbl 0066.25901 · doi:10.1090/S0002-9904-1955-09896-3
[38] DOI: 10.2307/2372632 · Zbl 0067.25203 · doi:10.2307/2372632
[39] DOI: 10.1090/S0002-9947-1955-0070594-4 · doi:10.1090/S0002-9947-1955-0070594-4
[40] Proceedings of the international congress of mathematicians, Cambridge, Massachusetts, U.S.A., August 30-September 6, 1950 1 pp 679– (1952)
[41] Introduction to metamathematics (1952)
[42] DOI: 10.2307/2371894 · Zbl 0061.01003 · doi:10.2307/2371894
[43] DOI: 10.1090/S0002-9947-1943-0007371-8 · doi:10.1090/S0002-9947-1943-0007371-8
[44] DOI: 10.2307/2267778 · Zbl 0020.33803 · doi:10.2307/2267778
[45] DOI: 10.1090/S0002-9904-1936-06353-6 · Zbl 0015.05002 · doi:10.1090/S0002-9904-1936-06353-6
[46] DOI: 10.1215/S0012-7094-36-00227-2 · Zbl 0014.38505 · doi:10.1215/S0012-7094-36-00227-2
[47] DOI: 10.1007/BF01565439 · Zbl 0014.19402 · doi:10.1007/BF01565439
[48] Mathematics and mind (1994)
[49] Monatsch. Math. Phys. 38 pp 173– (1931)
[50] Lecture notes in logic (1991)
[51] Mathematical logic (1967) · Zbl 0149.24309
[52] The Kleene symposium pp 123– (1980)
[53] Higher recursion theory (1990) · Zbl 0716.03043
[54] DOI: 10.1090/S0273-0979-1995-00606-3 · doi:10.1090/S0273-0979-1995-00606-3
[55] Bulletin of the American Mathematical Society 54 pp 641– (1948)
[56] DOI: 10.2307/2267170 · Zbl 1263.03030 · doi:10.2307/2267170
[57] DOI: 10.1090/S0002-9904-1944-08111-1 · Zbl 0063.06328 · doi:10.1090/S0002-9904-1944-08111-1
[58] DOI: 10.2307/2371809 · Zbl 0063.06327 · doi:10.2307/2371809
[59] Computability theory, semantics, and logicprogramming (1987)
[60] The space of mathematics pp 314– (1992)
[61] Computability: computable functions, logic, and the foundations of mathematics (1989) · Zbl 0685.03001
[62] Was sind und was sollen die Zahlen? (1888) · JFM 36.0087.04
[63] Stetigkeit und irrational Zahlen (1872)
[64] DOI: 10.2307/2269031 · Zbl 0015.19301 · doi:10.2307/2269031
[65] DOI: 10.1016/S0019-9958(82)91226-8 · Zbl 0519.03033 · doi:10.1016/S0019-9958(82)91226-8
[66] The undecidable. Basicpaperson undecidablepropositions, unsolvable problems, andcomputable functions (1965)
[67] Rekursive funktionen (1951) · Zbl 0043.24802
[68] Mathematische Annalen 110 pp 612– (1934)
[69] Computability and unsolvability (1958)
[70] Shadows of the mind (1994)
[71] Alan Turing: The enigma (1983) · Zbl 0541.68001
[72] Grundlagen der Mathematik I (1934), II (1939) I (1934)
[73] Grundzüge der theoretischen Logik (1928) · JFM 54.0055.01
[74] Die Grundlagen der Mathematik 6 pp 65– (1928)
[75] DOI: 10.1007/BF01206605 · JFM 51.0044.02 · doi:10.1007/BF01206605
[76] Mathematische Annalen 78 pp 405– (1918)
[77] Verhandlungen des Dritten Internationalen Mathematiker-Kongresses in Heidelberg vom 8. bis 13. August 1904 pp 174– (1905)
[78] Grundlagen der Geometrie (1899)
[79] The universal Turing machine: A half-century survey (1988) · Zbl 0648.00002
[80] Proceedings of the London Mathematical Society 45 pp 161– (1939)
[81] DOI: 10.2307/2268280 · Zbl 0018.19305 · doi:10.2307/2268280
[82] Collected works volume III: Unpublished essays and lectures (1995)
[83] Proceedings of the London Mathematical Society 42 pp 230– (1936)
[84] Collected works volume II: Publications 1938–1974 (1990)
[85] Proceedings of the 10th international congress of logic, methodology, and philosophy ofscience, August 19–25, 1995, Florence, Italy (1995)
[86] Collected works volume I: Publications 1929–36 (1986)
[87] Recursively enumerable sets and degrees: A study of computable functions and computably generated sets (1987) · Zbl 0667.03030
[88] Recursion theory and computational complexity (1981)
[89] Proceedings of the 10th international congress of logic, methodology, and philosophy of science, August 19–25, 1995, Florence, Italy
[90] Handbook of computability theory · Zbl 0923.03001
[91] Skrifter utgit av Videnskapsselskapet i Kristiania, I. Mathematisk-Naturvidenskabelig Klasse 6 pp 302– (1923)
[92] DOI: 10.1111/j.1746-8361.1958.tb01464.x · Zbl 0090.01003 · doi:10.1111/j.1746-8361.1958.tb01464.x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.