Editing Computability theory (section)

== References ==
{{Reflist|refs=
<ref name="Feferman_1990">{{cite book |chapter=<!-- What is the actual title of Gödel's 1946 chapter in this book? For now descriptive title: -->[Gödel (1946)] |title=Kurt Gödel Publications 1938–1974 Volume II |volume=II |author-first=Kurt |author-last=Gödel |author-link=Kurt Gödel |editor-first1=Solomon |editor-last1=Feferman |editor-link1=Solomon Feferman |display-editors=etal |date=1990 |pages=144ff |publisher=[[Oxford University Press]] |publication-place=New York, USA |isbn=978-0-19-514721-6 |quote-page=150 |quote=To be more precise: a function of integers is computable in any formal system containing arithmetic if and only if it is computable in arithmetic, where a function ''f'' is called computable in ''S'' if there is in ''S'' a computable term representing ''f''.}} (NB. This volume also includes the 1946 paper by [[Kurt Gödel]] (with commentary by Charles Parsons at pp. 144ff.). This 1990 edition has the cited footnote added by Gödel on p. 150 (which had also been added to Gödel's reprint in {{citeref|Davis|1965|Davis' 1965 compilation|style=plain}}).)</ref>
<ref name="Rado_1962">{{cite journal |title=On non-computable functions |author-first=Tibor |author-last=Radó |author-link=Tibor Radó |journal=[[Bell System Technical Journal]] |volume=41 |number=3 |doi=10.1002/j.1538-7305.1962.tb00480.x |date=May 1962 |pages=877–884 |url=https://archive.org/details/bstj41-3-877}}</ref>
<ref name="Soare_2011">{{cite web |title=Computability Theory and Applications: The Art of Classical Computability |author-last=Soare |author-first=Robert Irving |author-link=Robert Irving Soare |website=Department of Mathematics |publisher=[[University of Chicago]] |date=2011-12-22 |url=http://www.people.cs.uchicago.edu/~soare/Turing/frontice.pdf |access-date=2017-08-23 |url-status=live |archive-url=https://web.archive.org/web/20220630162944/http://www.people.cs.uchicago.edu/~soare/Turing/frontice.pdf |archive-date=2022-06-30}}</ref>
<ref name="Fortnow_2004">{{cite web |title=Is it Recursive, Computable or Decidable? |date=2004-02-15 |author-first=Lance Jeremy |author-last=Fortnow |author-link=Lance Jeremy Fortnow |url=https://blog.computationalcomplexity.org/2004/02/is-it-recursive-computable-or.html |access-date=2018-03-22 |url-status=live |archive-url=https://web.archive.org/web/20220807095606/https://blog.computationalcomplexity.org/2004/02/is-it-recursive-computable-or.html |archive-date=2022-08-07}}</ref>
<ref name="Simpson_1998">{{cite web |title=What is computability theory? |work=FOM email list |date=1998-08-24 |author-first=Stephen George |author-last=Simpson |author-link=Steve Simpson (mathematician) |url=http://www.cs.nyu.edu/pipermail/fom/1998-August/001993.html |access-date=2006-01-09 |url-status=live |archive-url=https://web.archive.org/web/20211218002012/https://cs.nyu.edu/pipermail/fom/1998-August/001993.html |archive-date=2021-12-18}}</ref>
<ref name="Friedman_1998">{{cite web |title=Renaming recursion theory |author-first=Harvey |author-last=Friedman |author-link=Harvey Friedman (mathematician) |work=FOM email list |date=1998-08-28 |url=http://www.cs.nyu.edu/pipermail/fom/1998-August/002017.html |access-date=2006-01-09 |url-status=live |archive-url=https://web.archive.org/web/20220301032647/https://cs.nyu.edu/pipermail/fom/1998-August/002017.html |archive-date=2022-03-01}}</ref>
<ref name="Kleene_1952">{{cite book |author-link=Stephen Cole Kleene |author-first=Stephen Cole |author-last=Kleene |title=Introduction to Metamathematics |publisher=[[North-Holland]] |date=1952 |pages=300, 376}}</ref>
<ref name="Davis_1965">{{cite book |editor-first=Martin |editor-last=Davis |editor-link=Martin Davis (mathematician) |title=The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions |url=https://books.google.com/books?id=qW8x7sQ4JXgC |date=2004 |publisher=[[Dover Publications, Inc.]]<!-- Courier Corporation? --> |orig-date=1965 |isbn=978-0-486-43228-1 |page=84 |ref={{harvid|Davis|1965}} |quote-page=84 |quote=[[Kurt Gödel]] (1946): [[Alfred Tarski|Tarski]] has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing's computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute notion to an interesting epistemological notion, i.e., one not depending on the formalism chosen.}}</ref>
<ref name="Church_1936a">{{cite journal |author-first=Alonzo |author-last=Church |author-link=Alonzo Church |title=An unsolvable problem of elementary number theory |journal=[[American Journal of Mathematics]] |issn= |volume=58 |issue=2 |pages=345–363 |date=1936a |jstor=2371045 |doi=10.2307/2371045}} Reprinted in {{harvnb|Davis|1965}}.</ref>
<ref name="Church_1936b">{{cite journal |author-first=Alonzo |author-last=Church |author-link=Alonzo Church |title=A note on the Entscheidungsproblem |journal=[[Journal of Symbolic Logic]] |issn= |volume=1 |number=1<!-- and vol. 3, n. 3.?) --> |pages=40–41 |date=1936b |jstor=2269326 |doi=10.2307/2269326 |s2cid=42323521}} Reprinted in {{harvnb|Davis|1965}}.</ref>
<ref name="Turing_1936">{{cite journal |author-first=Alan Mathison |author-last=Turing |author-link=Alan Mathison Turing |title=On computable numbers, with an application to the Entscheidungsproblem |journal=[[Proceedings of the London Mathematical Society]] |issn= |series=2 |volume=42 |issue=1 |pages=230–265 |date=1937 |orig-date=1936 |doi=10.1112/plms/s2-42.1.230 |s2cid=73712}} {{cite journal |author-first=Alan Mathison |author-last=Turing |author-link=Alan Mathison Turing |title=On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction |journal=[[Proceedings of the London Mathematical Society]] |issn= |series=2 |volume=43 |issue=1 |pages=544–546 |date=1938 |doi=10.1112/plms/s2-43.6.544 |url=http://web.comlab.ox.ac.uk/oucl/research/areas/ieg/e-library/sources/tp2-ie.pdf |access-date=2022-08-08 |url-status=live |archive-url=https://web.archive.org/web/20220718224343/https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf |archive-date=2022-07-18}} Reprinted in {{harvnb|Davis|1965}}.</ref>
<ref name="Ershov-Goncharov-Nerode-Remmel-1998">{{cite book |author-first1=Yury Leonidovich |author-last1=Ershov |author-link1=Yury Leonidovich Ershov |author-first2=Sergei<!-- Sergey--> Savostyanovich |author-last2=Goncharov |author-link2=:d:Q23371742 |author-first3=Anil |author-last3=Nerode |author-link3=Anil Nerode |author-first4=Jeffrey B. |author-last4=Remmel |author-link4=Jeffrey B. Remmel |title=Handbook of Recursive Mathematics |publisher=[[North-Holland]] |date=1998 |isbn=0-7204-2285-X}}</ref>
<ref name="Soare_1987">{{cite book |author-first=Robert Irving |author-last=Soare |author-link=Robert Irving Soare |title=Recursively Enumerable Sets and Degrees |publisher=[[Springer-Verlag]] |date=1987 |isbn=0-387-15299-7 |series=Perspectives in Mathematical Logic}}</ref>
<ref name="Soare_1996">{{cite journal |author-first=Robert Irving |author-last=Soare |author-link=Robert Irving Soare |title=Computability and recursion |journal=[[Bulletin of Symbolic Logic]] |issn= |volume=2 |issue=3 |pages=284–321 |date=1996 |doi=10.2307/420992 |url=http://www.people.cs.uchicago.edu/~soare/History/compute.pdf |jstor=420992 |s2cid=5894394}}</ref>
<ref name="Cutland_1980">{{cite book |title=Computability, An introduction to recursive function theory |author-first=Nigel J. |author-last=Cutland |author-link=Nigel J. Cutland |publisher=[[Cambridge University Press]] |date=1980 |isbn=0-521-29465-7 |url=https://archive.org/details/computabilityint0000cutl |url-access=registration}}</ref>
<ref name="Turing_1939">{{cite journal |author-first=Alan Mathison |author-last=Turing |author-link=Alan Mathison Turing |title=Systems of logic based on ordinals |journal=[[Proceedings of the London Mathematical Society]] |issn= |series=2 |volume=45 |issue=1 |pages=161–228 |date=1939 |doi=10.1112/plms/s2-45.1.161 |hdl=21.11116/0000-0001-91CE-3 |hdl-access=free}} Reprinted in {{harvnb|Davis|1965}}.</ref>
<ref name="Post_1944">{{cite journal |author-first=Emil Leon |author-last=Post |author-link=Emil Leon Post |title=Recursively enumerable sets of positive integers and their decision problems |journal=[[Bulletin of the American Mathematical Society]] |issn= |volume=50 |issue=5 |pages=284–316 |date=1944 |doi=10.1090/S0002-9904-1944-08111-1 |mr=0010514 |doi-access=free}} Reprinted in {{harvnb|Davis|1965}}.</ref>
<ref name="Shore-Slaman_1999">{{cite journal |author-last1=Shore |author-first1=Richard Arnold |author-link1=Richard Arnold Shore |author-last2=Slaman |author-first2=Theodore Allen |author-link2=Theodore Allen Slaman |title=Defining the Turing Jump |mr=1739227 |date=1999 |journal=Mathematical Research Letters |issn=1073-2780 |volume=6 |issue=6 |doi=10.4310/mrl.1999.v6.n6.a10 |doi-access=free |pages=711–722 }}</ref>
<ref name="Ambos-Spies-Fejer_2006">{{cite encyclopedia
 | last1 = Ambos-Spies | first1 = Klaus
 | last2 = Fejer | first2 = Peter A.
 | editor-last = Siekmann | editor-first = Jörg H.
 | title = Degrees of unsolvability
 | doi = 10.1016/B978-0-444-51624-4.50010-1
 | isbn = 978-0-444-51624-4
 | location = Amsterdam
 | mr = 3362163
 | pages = 443–494
 | publisher = Elsevier/North-Holland
 | series = Handbook of the History of Logic
 | encyclopedia = Computational Logic
 | url = http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
 | archive-url = https://web.archive.org/web/20130420184948/http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
 | archive-date = 2013-04-20 |url-status = dead
 | volume = 9
 | year = 2014}}</ref>
<ref name="Harrington-Soare_1991">{{cite journal |author-first1=Leo Anthony |author-last1=Harrington |author-link1=Leo Anthony Harrington |author-first2=Robert Irving |author-last2=Soare |author-link2=Robert Irving Soare |title=Post's Program and incomplete recursively enumerable sets |journal=[[Proceedings of the National Academy of Sciences USA]] |issn= |volume=88 |issue=22 |pages=10242–10246 |date=1991 |pmid=11607241 |pmc=52904 |doi=10.1073/pnas.88.22.10242 |bibcode=1991PNAS...8810242H |doi-access=free}}</ref>
<ref name="Simpson_1999">{{cite book |author-link=Steve Simpson (mathematician) |author-first=Steven George |author-last=Simpson |title=Subsystems of Second Order Arithmetic |publisher=[[Springer-Verlag]] |date=1999 |isbn=3-540-64882-8}}</ref>
<ref name="Slaman-Woodin_1986">{{cite journal |author-first1=Theodore Allen |author-last1=Slaman |author-link1=Theodore Allen Slaman |author-first2=William Hugh |author-last2=Woodin |author-link2=William Hugh Woodin |title=Definability in the Turing degrees |journal=[[Illinois Journal of Mathematics]] |issn= |volume=30 |issue=2 |pages=320–334 |date=1986 |doi=10.1215/ijm/1256044641 |mr=840131 |doi-access=free}}</ref>
<ref name="Soare_1974">{{cite journal |author-first=Robert Irving |author-last=Soare |author-link=Robert Irving Soare |title=Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets |journal=[[Annals of Mathematics]] |issn= |volume=100 |issue=1 |pages=80–120 |date=1974 |jstor=1970842 |doi=10.2307/1970842}}</ref>
<ref name="Sacks_1990">{{cite book |author-first=Gerald Enoch |author-last=Sacks |author-link=Gerald Enoch Sacks |title=Higher Recursion Theory |url=https://archive.org/details/higherrecursiont0000sack |url-access=registration |publisher=[[Springer-Verlag]] |date=1990 |isbn=3-540-19305-7}}</ref>
<ref name="Orponen_1997">{{cite book |citeseerx=10.1.1.53.1991 |author-first=Pekka |author-last=Orponen |title=Advances in Algorithms, Languages, and Complexity |chapter=A Survey of Continuous-Time Computation Theory |issn= |pages=209–224 |date=1997 |doi=10.1007/978-1-4613-3394-4_11 |isbn=978-1-4613-3396-8}}</ref>
<ref name="Moore_1996">{{cite journal |title=Recursion theory on the reals and continuous-time computation |citeseerx=10.1.1.6.5519 |author-link=Cris Moore |author-first=Cris |author-last=Moore |journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] |issn= |date=1996 |doi=10.1016/0304-3975(95)00248-0 |volume=162 |issue=1 |pages=23–44}}</ref>
<ref name="Fairtlough-Wainer_1998">{{cite book |author-first1=Matt |author-last1=Fairtlough |author-first2=Stanley S. |author-last2=Wainer |chapter=Hierarchies of Provably Recursive Functions |editor-first=Samuel R. |editor-last=Buss |editor-link=Samuel R. Buss |title=Handbook of Proof Theory |chapter-url=https://books.google.com/books?id=MfTMDeCq7ukC&pg=PA149 |date=1998 |publisher=[[Elsevier]] |isbn=978-0-08-053318-6 |pages=149–208}}</ref>
<ref name="Rogers_1987">{{cite book |author-link=Hartley Rogers Jr. |author-first=Hartley Jr. |author-last=Rogers |title=The Theory of Recursive Functions and Effective Computability |edition=2nd |publisher=[[MIT Press]] |date=1987 |isbn=0-262-68052-1}}</ref>
}}