1. Ausiello, Giorgio and Gambosi, Giorgio and d’Amore, Fabrizio. 2002. Linguaggi, Modelli, Complessità. Milano: Franco Angeli.
2. Bernays, Paul. Letter to Gödel, 7 January 1970. Bernays Papers, ETH Zürich Library/WHS, Hs. 975:1745.
3. Buss, Samuel R. 1995. “On Gödel’s Theorems on Lengths of Proofs II: Lower Bounds for Recognizing k Symbol Provability Bounded Arithmetic and Propositional Proof Complexity.” In Feasible Mathematics II, edited by P. Clote and J. Remmel 57-90. Basel: Birkhauser. DOI: 10.1007/978-1-4612-2566-9_4
4. Church, Alonso. 1936. “An unsolvable Problem of Elementary Number Theory”. American Journal of Mathematics 58 (2): 345-363.
5. Cook, Stephen. 1971. “The complexity of theorem-proving procedures.” In STOC ’71 Pro- ceedings of the third annual ACM symposium on Theory of computing, 151-158. New York: ACM Association for Computing Machinery. DOI: 10.7551/mitpress/12274.003.0036
6. Davis, Martin and Sigal, Ron and Elaine, Jean. 1994. Computability, complexity and language. Burlington: Morgan Kaufmann.
7. Dawson, John. 1997. Logical Dilemmas. The Life and Work of Kurt Gödel. Wellesley: A K Peters.
8. Dedekind, Richard. 1888. Was sind und was sollen die Zahlen? 1. Auflage. Braunschweig: Vieweg.
9. Du, Dingzhu and Ko, Ker-I. 2014. Theory of Computational Complexity. 2nd Edition. Hoboken: Wiley.
10. Enderton, Herbert B. A mathematical introduction to logic (Second edition). Harcourt/Academic Press: San Diego. DOI: 10.1016/C2009-0-22107-6
11. Feferman, Solomon. 2006. “Are There Absolutely Unsolvable Problems? Gödel’s Dichotomy”. Philosophia Mathematica (III) 14: 134-152. DOI: 10.1093/philmat/nkj003
12. Feferman, Solomon. 2006. “Turing’s Thesis.” Notices of the AMS, Vol. 53 (10): 2-8. DOI: 10.2307/j.ctv1vbd2dr.5
13. Gandy, Robin. 1980. “Church’s Thesis and Principles for Mechanisms.” In The Kleene Symposium, edited by J. Barwise, H. J. Keisler, K. Kunen, K. , 123-148. Amsterdam: North- Holland. DOI: 10.1016/S0049-237X(08)71257-6
14. Gödel, Kurt. 1930. “Die Vollständigkeit der Axiome des logischen Funktionenkalküls”. Translated by Stefan Bauer-Mengelberg. In Gödel’s Collected Works (1986-2005) 102–23
15. Gödel, Kurt. 1931. “Über Formal Unentscheidbare Sätze der Principia Mathematica und Verwandter Systeme I.” Monatshefte für Mathematik und Physik 38: 173-198 (reprinted in Gödel’s Collected Works (1986-2005), Vol. I: 144-195 DOI: 10.1007/BF01700692
16. Gödel, Kurt. 1986-2005. Collected Works I-V, edited by S. Feferman, J. W. Dawson, Stephen C. Kleene, W. Goldfarb, G. Moore, C. Parsons, R. Solovay and Jean Van Heijenoort. Oxford: Oxford University Press. DOI: 10.1093/oso/9780195072556.001.0001
17. Hájek, Peter and Pudlák, Pavel. 1993. Metamathematics of first order arithmetic. Berlin: Springer. DOI: 10.1007/978-3-642-78321-9
18. Hartmanis, Juris and Stearns, Richard E. 1965. “On the computational complexity of algo- rithms.” Transactions of American Mathematical Society 117 (5): 285-306. DOI: 10.1090/S0002-9947-1965-0170805-7
19. Henkin, Leon. (1950). “Completeness in the Theory of Types”. The Journal of Symbolic Logic”, 15 (2): 81-91. DOI: 10.2307/2268698
20. Hilbert, David and Ackermann, Wilhelm. 1928. Grundzüge der theoretischen Logik. Berlin: Springer.
21. Levin, Leonid. 1973. “Universal search problems.” Problems of Information Transmission 9 (3): 115-116. DOI: 10.1007/978-0-387-30164-8_603
22. Lindström, Per. 1969. “On Extensions of Elementary Logic.” Theoria 35: 1-11 DOI: 10.1111/j.1755-2567.1969.tb00356.x
23. Lucas, John R. 1961. “Minds, machines and Godel”. Philosophy 36 (137): 112-127. DOI: 10.1017/s0031819100057983
24. Kleene, Stephen C. 1967. Mathematical Logic. New York: Wiley
25. Kreisel, Georg. 1971. “Some Reasons for Generalizing Recursion Theory.” In Studies in Logic and the Foundations of Mathematics 61, edited by R.O. Gandy and C.M.E. Yates 139-198. Amsterdam: Elsevier. DOI: 10.2307/2271903
26. Mal’cev, Anatoli Ivanovic. 1971. The Metamathematics of Algebraic Systems. Collected Papers: 1936–1967. Studies in Logic and the Foundations of Mathematics, Volume 66. Amsterdam: Elsevier.
27. McCulloch, Warren S. and Pitts, Walter. 1943. “A Logical Calculus of the Ideas Immanent in Nervous Activity”. Bulletin of Mathematical Biophysics 5: 115-133. DOI: 10.2307/2268029
28. Nelson, Edward. 1986. Predicative Arithmetic. Princeton: Princeton Univ. Press. DOI: 10.2307/2274590
29. Nielsen, Michael A. and Chuang, Isaac L. 2010. Quantum Computation and Quantum Infor- mation: 10th Anniversary Edition. Cambridge: Cambridge University Press.
30. Post, E.L. 1936. “Finite Combinatory Processes - Formulation 1”. The Journal of Symbolic Logic 1: 103-105. DOI: 10.2307/2269031
31. Ryll-Nardzewski, Czesław. 1952. “The role of the axiom of induction in elementary arithmetic”. Fundamenta Mathematicae 39: 239-63.
32. Odifreddi, Piergiorgio. 1989. Classical Recursion Theory I. Amsterdam: North Holland.
33. Sipser, Michael. 2006. Introduction to the Theory of Computation, second edition. Boston: Course Technology.
34. Soare, Robert I. 1996. “Computability and Recursion.” The Bulletin of Symbolic Logic 2 (3) DOI: 10.2307/420992
35. Soare, Robert I. 2009. “Turing oracle machines, online computing, and three displacements in computability theory”. Annals of Pure and Applied Logic 160 (3): 368-399. DOI: 10.1016/j.apal.2009.01.008
36. Soare, Robert I. 2014. “Turing and the discovery of computability”. In Turing’s Legacy: Developments from Turing’s Ideas in Logic. Lecture Notes in Logic, edited by R. Downey 467-492. Cambridge: Cambridge University Press. DOI: 10.1017/CBO9781107338579.001
37. Tait, William. 1981. “Finitism.” Journal of Philosophy 78 (9): 524-546. DOI: 10.2307/2026089
38. Tarski, Alfred and Mostowski, Andrzej and Robinson, Raphael M. 1953. Undecidable Theories. Amsterdam: Elsevier.
39. Turing, Alan M. 1936. “On computable numbers, with application to the Entscheidungsproblem”, in Proceedings of London Math. Soc. 42: 230-265, 544-546. DOI: 10.1112/plms/s2-42.1.230
40. Van Emde Boas, Peter. 1990. “Machine Models and Simulations.” In Handbook of Theoretical Computer Science, Algorithms and Complexity, edited by L. Van Leeuwen, 1-66. Amsterdam: Elsevier.
41. Visser, Albert. 2009. “Why the theory R is special”. Logic Group preprint series, 279. Utrecht Univ. Now in In Friedman, H. and Tennant, N. (eds.) 2014. Foundational Adventures. Essay in honour of Harvey Friedman: 7-23. London: College Publications. DOI: 10.1007/s10992-014-9304-0

Chapter Information

Bibliographic Information