Redigerer Alan Turing (avsnitt)

=== Universitet og arbeider innen datateknologi ===
Fra 1931 til 1934 studerte Turing ved [[King's College (Cambridge)|King's College i Cambridge]], hvor han oppnådde fremragende resultater i matematikk. Allerede som 22-åring ble han i 1935 innvalgt som [[fellow]] ved King's College på bakgrunn av en avhandling der han beviste [[sentralgrenseteoremet]].<ref>See Section 3 of John Aldrich, "England and Continental Probability in the Inter-War Years", Journal Electronique d'Histoire des Probabilités et de la Statistique, vol. 5/2 [http://www.jehps.net/decembre2009.html Decembre 2009] Journal Electronique d'Histoire des Probabilités et de la Statistique
</ref> Han hadde riktignok oversett at dette allerede hadde blitt bevist i 1922 av [[Jarl Waldemar Lindeberg]].<ref>{{Harvnb|Hodges|1983|pp=88,94}}</ref>

[[Fil:Alan Turing Memorial Closer.jpg|thumb|upright|Alan Turing minnestatue i [[Whitworth Gardens|Sackville Park]], Manchester|alt=]]

I 1928 hadde den tyske matematikeren [[David Hilbert]] skapt oppmerksomhet om det såkalte «beslutningsproblemet». I sin artikkel «Om beregnbare tall og deres anvendelse på Beslutningsproblemet» fra 1936,<ref>
{{Harvnb|Turing|1937}}</ref> reformulerte Turing resultatene til [[Kurt Gödel]] fra 1931. Han erstattet Gödels aritmetikkbaserte formalspråk med formelle og enkle hypotetiske innretninger som senere ble omtalt som turingmaskiner. Turing viste at det kunne lages en maskin som kunne utføre enhver tenkbar matematisk beregning, dersom den kunne beskrives i en [[algoritme]]. Han fortsatte med å bevise at det ikke finnes noen løsning på beslutningsproblemet ved først å vise at [[stopp-problemet]] for turingmaskiner ikke kan avgjøres: eller at det ikke er mulig å sette opp en algoritme som kan avgjøre om en turingmaskin vil stoppe.{{Klargjør}}

Turings bevis kom kort tid etter et tilsvarende bevis fremsatt av [[Alonzo Church]] <ref>{{Harvnb|Church|1936}}</ref> basert på [[lambdakalkyle]]. Turing hadde ikke vært klar over arbeidene til Church.<ref>{{Harvnb|Hodges|1983|p=111}}</ref> 
Turings tilnærming til problemet er vesentlig mer tilgjengelig og intuitivt enn Church sin fremstilling. Den var også nyskapende i sin fremstilling av en «universell maskin», nå omtalt som en [[universell turingmaskin]], en maskin som kan beregne alt som kan beregnes. [[John von Neumann|Von Neumann]] har erkjent det grunnleggende prinsipp for moderne datamaskiner er basert på denne artikkelen.<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'', p22.</ref> Turingmaskiner er frem til i dag et sentralt tema innen informatikkstudiet.

I perioden fra september 1936 til juli 1938 studerte Turing under Church ved [[Princeton University]]. I tillegg til rene studier innen matematikk studerte han [[kryptologi]]. Videre bygget han tre av de fire trinnene i en elektromekanisk, binær multiplikator.<ref>{{Harvnb|Hodges|1983|p=138}}</ref> 
I juni 1938 fikk han sin ph.d. fra Princeton.<ref>{{Kilde artikkel
 | forfatter1 = A. M. Turing
 | tittel = Systems of Logic Based on Ordinals
 | publikasjon = London Mathematical Society
 | år = 1939
 | bind = s2-45
 | hefte = 1
 | sider = 161-228
 | doi = 10.1112/plms/s2-45.1.161
 | url = https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s2-45.1.161
 | besøksdato = 2019-04-05
 | arkiv-dato = 2019-10-23
 | arkiv-url = https://web.archive.org/web/20191023203913/https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s2-45.1.161
 | url-status=død
 }}</ref> 
Hans avhandling var ''Systems of Logic Based on Ordinals.''<ref name="turingphd">{{cite thesis |degree=PhD |first=Alan|last=Turing |title=Systems of Logic Based on Ordinals|publisher=Princeton University |date=1938 |url=http://search.proquest.com/docview/301792588|doi=10.1112/plms/s2-45.1.161|authorlink=Alan Turing}}</ref><ref>{{Kilde www | etternavn = Turing | fornavn = A. M. | forfatterlenke = Alan Turing | tittel = Systems of Logic Based on Ordinals | år = 1938 | url = https://webspace.princeton.edu/users/jedwards/Turing%20Centennial%202012/Mudd%20Archive%20files/12285_AC100_Turing_1938.pdf | ref = harv | besøksdato = 2014-12-28 | arkiv-dato = 2012-10-23 | arkiv-url = https://web.archive.org/web/20121023103503/https://webspace.princeton.edu/users/jedwards/Turing%20Centennial%202012/Mudd%20Archive%20files/12285_AC100_Turing_1938.pdf | url-status=død }}</ref> 
Turing returnerte i 1939 til Cambridge og deltok i [[Ludwig Wittgenstein]]s forelesninger om grunnlaget for matematikken.<ref>
{{Harvnb|Hodges|1983|p=152}}</ref> Forelesningene er gjenskapt ordrett med grunnlag i Turings og de andre studentenes notater.<ref>ed. [[Cora Diamond]]: ''Wittgenstein's Lectures on the Foundations of Mathematics'', University of Chicago Press, 1976</ref>