Editing Alan Turing (section)

===University and work on computability===
[[File:Alan Turing az 1930-as években.jpg|thumb|Turing in the 1930s]]
After graduating from Sherborne, Turing applied for several Cambridge colleges scholarships, including [[Trinity College, Cambridge|Trinity]] and [[King's College, Cambridge|King's]], eventually earning an £80 per annum scholarship (equivalent to about £4,300 as of 2023) to study at the latter.<ref>{{cite book |last1=Hodges |first1=Andrew |title=Alan Turing: The Enigma |date=10 November 2014 |publisher=Princeton University Press |isbn=978-0-691-16472-4 |pages=74–5 |edition=2014}}</ref><ref>{{cite web | url=https://www.bankofengland.co.uk/monetary-policy/inflation/inflation-calculator | title=Inflation calculator | access-date=26 August 2024 | archive-date=5 October 2018 | archive-url=https://web.archive.org/web/20181005211045/https://www.bankofengland.co.uk/monetary-policy/inflation/inflation-calculator | url-status=live }}</ref> There, Turing studied the undergraduate course in Schedule B <ref>(Schedule B was a three-year scheme consisting of Parts I and II, of the [[Mathematical Tripos]], with extra courses at the end of the third year, as Part III only emerged as a separate degree in 1934</ref> from February 1931 to November 1934 at [[King's College, Cambridge]], where he was awarded first-class honours in mathematics. His dissertation, ''On the Gaussian error function'', written during his senior year and delivered in November 1934 (with a deadline date of 6 December) proved a version of the [[central limit theorem]]. It was finally accepted on 16 March 1935. By spring of that same year, Turing started his master's course ([[Part III of the Mathematical Tripos|Part III]])—which he completed in 1937—and, at the same time, he published his first paper, a one-page article called ''Equivalence of left and right almost periodicity'' (sent on 23 April), featured in the tenth volume of the ''[[London Mathematical Society|Journal of the London Mathematical Society]]''.<ref>{{cite web | url=https://turingarchive.kings.cam.ac.uk/publications-lectures-and-talks-amtb/amt-b-10 | title=AMT-B-10 &#124; the Turing Digital Archive }}</ref> Later that year, Turing was elected a [[Fellow]] of King's College on the strength of his dissertation<ref>{{Cite journal |last=Aldrich |first=John |date=December 2009 |title=England and Continental Probability in the Inter-War Years |journal=Electronic Journ@l for History of Probability and Statistics |volume=5 |number=2 |url=https://www.jehps.net/Decembre2009/Aldrich.pdf |pages=7–11}}</ref> where he served as a [[lecturer]].<ref name=lecturer>{{cite web|first=Alan|last=Turing|year=1939|url=https://archivesearch.lib.cam.ac.uk/repositories/7/archival_objects/272543|website=cam.ac.uk|title=Letter From Alan Turing to his mother, Sara Turing, 1939-01-23|quote=“My lectures are going off rather well. There are 14 people coming to them at present. No doubt the attendance will drop off as the term advances.”}}</ref> However, and, unknown to Turing, this version of the theorem he proved in his paper, had already been proven, in 1922, by [[Jarl Waldemar Lindeberg]]. Despite this, the committee found Turing's methods original and so regarded the work worthy of consideration for the fellowship. [[Abram Besicovitch]]'s report for the committee went so far as to say that if Turing's work had been published before Lindeberg's, it would have been "an important event in the mathematical literature of that year".<ref>{{cite book |last=Turing |first=Dermot |author-link=Dermot Turing |title=[[Prof: Alan Turing Decoded]] |year=2015 |publisher=[[The History Press]] |isbn=9781841656434 |page= 69}}</ref>{{sfn|Hodges|1983|p=113}}<ref>{{cite journal|title=Alan Turing and the Central Limit Theorem |first=S. L. |last=Zabell |pages=483–494 |journal=The American Mathematical Monthly |volume=102 |year=1995 |number=6 |doi=10.1080/00029890.1995.12004608}}</ref>

Between the springs of 1935 and 1936, at the same time as [[Alonzo Church]], Turing worked on the decidability of problems, starting from [[Gödel's incompleteness theorems]]. In mid-April 1936, Turing sent Max Newman the first draft typescript of his investigations. That same month, Church published his ''An Unsolvable Problem of Elementary Number Theory'', with similar conclusions to Turing's then-yet unpublished work. Finally, on 28 May of that year, he finished and delivered his 36-page paper for publication called "[[On Computable Numbers, with an Application to the Entscheidungsproblem]]".<ref name=computable>{{Cite journal | last = Turing | first = A. M. | publication-date = 1937 | title = On Computable Numbers, with an Application to the Entscheidungsproblem: A correction | periodical = Proceedings of the London Mathematical Society | series = 2 | volume = 43 | pages = 544–46 | doi = 10.1112/plms/s2-43.6.544 | year = 1938 | issue = 1 }}</ref><ref>{{Harvnb|Turing|1937}}</ref> It was published in the ''Proceedings of the London Mathematical Society'' journal in two parts, the first on 30 November and the second on 23 December.<ref>{{cite book |url=https://books.google.com/books?id=MlsJuSj2OkEC&pg=PA211 |page=211 |title=Computability: Turing, Gödel, Church, and Beyond |author1=B. Jack Copeland |author2=Carl J. Posy |author3=Oron Shagrir |publisher=MIT Press |year=2013|isbn=978-0-262-01899-9 }}</ref> In this paper, Turing reformulated [[Kurt Gödel]]'s 1931 results on the limits of proof and computation, replacing Gödel's universal arithmetic-based formal language with the formal and simple hypothetical devices that became known as [[Turing machine]]s. The ''[[Entscheidungsproblem]]'' (decision problem) was originally posed by German mathematician [[David Hilbert]] in 1928. Turing proved that his "universal computing machine" would be capable of performing any conceivable mathematical computation if it were representable as an [[algorithm]]. He went on to prove that there was no solution to the ''decision problem'' by first showing that the [[halting problem]] for Turing machines is [[Decision problem|undecidable]]: it is not possible to decide algorithmically whether a Turing machine will ever halt. This paper has been called "easily the most influential math paper in history".<ref>{{cite book |page=15 |title=Mathematics and Computation |author=Avi Wigderson |publisher=Princeton University Press |year=2019|isbn=978-0-691-18913-0 }}</ref>

[[File:20130808 Kings College Front Court Fountain Crop 03.jpg|thumb|right|[[King's College, Cambridge]], where Turing was an undergraduate in 1931 and became a Fellow in 1935. The computer room is named after him.]]
Although [[Turing's proof]] was published shortly after Church's equivalent proof using his [[lambda calculus]],<ref>{{Harvnb|Church|1936}}</ref> Turing's approach is considerably more accessible and intuitive than Church's.<ref>{{cite web|last1=Grime|first1=James|title=What Did Turing Do for Us?|url=https://nrich.maths.org/8050|website=[[NRICH]]|publisher=[[University of Cambridge]]|access-date=28 February 2016|date=February 2012|archive-url=https://web.archive.org/web/20160304175703/http://nrich.maths.org/8050|archive-date=4 March 2016|url-status=live}}</ref> It also included a notion of a 'Universal Machine' (now known as a [[universal Turing machine]]), with the idea that such a machine could perform the tasks of any other computation machine (as indeed could Church's lambda calculus). According to the [[Church–Turing thesis]], Turing machines and the lambda calculus are capable of computing anything that is computable. [[John von Neumann]] acknowledged that the central concept of the modern computer was due to Turing's paper.<ref>"von Neumann&nbsp;... firmly emphasised to me, and to others I am sure, that the fundamental conception is owing to Turing—insofar as not anticipated by Babbage, Lovelace and others." Letter by [[Stanley Frankel]] to [[Brian Randell]], 1972, quoted in [[Jack Copeland]] (2004) ''The Essential Turing'', p.&nbsp;22.</ref> To this day, Turing machines are a central object of study in [[theory of computation]].<ref>{{Citation |last=De Mol |first=Liesbeth |title=Turing Machines |date=2021 |url=https://plato.stanford.edu/archives/win2021/entries/turing-machine/ |encyclopedia=The Stanford Encyclopedia of Philosophy |editor-last=Zalta |editor-first=Edward N. |access-date=12 July 2023 |edition=Winter 2021 |publisher=Metaphysics Research Lab, Stanford University |archive-url= https://web.archive.org/web/20221016224306/https://plato.stanford.edu/archives/win2021/entries/turing-machine/ |archive-date= 16 October 2022 |url-status=live }}</ref>

From September 1936 to July 1938, Turing spent most of his time studying under Church at [[Princeton University]],<ref name="bowen19" /> in the second year as a [[Jane Eliza Procter Fellowship|Jane Eliza Procter Visiting Fellow]]. In addition to his purely mathematical work, he studied cryptology and also built three of four stages of an electro-mechanical [[binary multiplier]].<ref>{{Harvnb|Hodges|1983|p=138}}</ref> In June 1938, he obtained his PhD from the [[Princeton University Department of Mathematics|Department of Mathematics]] at Princeton;<ref>{{Cite journal
| last1 = Turing | first1 = A.M.
| author-link = Alan Turing
| title = Systems of Logic Based on Ordinals
| doi = 10.1112/plms/s2-45.1.161
| journal = Proceedings of the London Mathematical Society
| pages = 161–228
| year = 1939
| volume=s2-45
| issue = 1
| hdl = 21.11116/0000-0001-91CE-3
| hdl-access = free
}}</ref> his dissertation, ''[[Systems of Logic Based on Ordinals]]'',<ref name="turingphd">{{cite thesis |degree=PhD |first=Alan|last=Turing |title=Systems of Logic Based on Ordinals|journal=Proceedings of the London Mathematical Society |publisher=Princeton University |year=1938 |volume=s2-45 |issue=1 |doi=10.1112/plms/s2-45.1.161|author-link=Alan Turing|id={{ProQuest|301792588}}|hdl=21.11116/0000-0001-91CE-3|hdl-access=free}}</ref><ref>{{cite web | last = Turing | first = A.M. | author-link = Alan Turing | title = Systems of Logic Based on Ordinals | year = 1938 | url = https://webspace.princeton.edu/users/jedwards/Turing%20Centennial%202012/Mudd%20Archive%20files/12285_AC100_Turing_1938.pdf | access-date = 4 February 2012 | archive-url = https://web.archive.org/web/20121023103503/https://webspace.princeton.edu/users/jedwards/Turing%20Centennial%202012/Mudd%20Archive%20files/12285_AC100_Turing_1938.pdf | archive-date = 23 October 2012 | url-status = dead }}</ref> introduced the concept of [[ordinal logic]] and the notion of [[Turing reduction|relative computing]], in which Turing machines are augmented with so-called [[oracle machine|oracles]], allowing the study of problems that cannot be solved by Turing machines. John von Neumann wanted to hire him as his [[Postdoctoral researcher|postdoctoral assistant]], but he went back to the United Kingdom.<ref>''John Von Neumann: The Scientific Genius Who Pioneered the Modern Computer, Game Theory, Nuclear Deterrence, and Much More'', Norman MacRae, 1999, American Mathematical Society, Chapter 8</ref>