Turing machine, hypothetisch rekenapparaat dat in 1936 door de Engelse wiskundige en logicus Alan M. Turing werd geïntroduceerd. Turing zag de machine oorspronkelijk als een wiskundig werktuig dat onfeilbaar onbeslisbare proposities kon herkennen – dat wil zeggen, die wiskundige uitspraken waarvan, binnen een gegeven formeel axioma systeem, niet kan worden aangetoond dat ze waar of onwaar zijn. (De wiskundige Kurt Gödel had aangetoond dat dergelijke onbeslisbare stellingen bestaan in elk systeem dat krachtig genoeg is om rekenkunde te bevatten). Turing bewees in plaats daarvan dat er nooit een universele algoritmische methode kan bestaan om te bepalen of een stelling onbeslisbaar is.
De Turing machine is geen machine in de gewone zin van het woord, maar eerder een geïdealiseerd wiskundig model dat de logische structuur van elk computerapparaat tot zijn essentie terugbrengt. Zoals Turing het voor ogen had, voert de machine haar functies uit in een opeenvolging van discrete stappen en neemt zij op elk gegeven moment slechts één van een eindige lijst van interne toestanden aan. De machine zelf bestaat uit een oneindig uitrekbare band, een bandkop die in staat is verschillende bewerkingen op de band uit te voeren, en een aanpasbaar controlemechanisme in de kop dat aanwijzingen van een eindige reeks instructies kan opslaan. De band is verdeeld in vierkanten, die elk leeg zijn of waarop één van een eindig aantal symbolen is gedrukt. De bandkop kan naar elk willekeurig vakje gaan, het lezen, schrijven en wissen en kan ook op elk moment naar een andere interne toestand overschakelen. Een dergelijke handeling wordt bepaald door de interne toestand van de machine en de toestand van het gescande vierkant op een bepaald moment. De output van de machine – d.w.z. de oplossing van een wiskundige vraag – kan uit het systeem worden gelezen zodra de machine is gestopt. (In het geval van Gödel’s onbeslisbare stellingen zou de machine echter nooit stoppen, en dit werd bekend als het “halteringsprobleem.”)
Door alle essentiële kenmerken van informatieverwerking te incorporeren, werd de Turing machine de basis voor alle latere digitale computers, die het basisschema van de machine delen: een input/output apparaat (band en lezer), geheugen (opslag van het controlemechanisme), en centrale verwerkingseenheid (controlemechanisme).