Een turingmachine is in de informatica een model van berekening en berekenbaarheid. Het ie een zeer eenvoudig mechanisme dat is ontwikkeld door de wiskundige Alan M. Turing. De turingmachine is naar hem vernoemd en is beschreven in het inmiddels beroemde artikel “On computable numbers, with an application to the Entscheidungsproblem” uit 1936-37 dat geschreven is door Alan M. Turing.
Een turingmachine is een mechanisme dat symbolen kan manipuleren en de logica van elke mogelijke computer simuleren. In één stap kunnen door de turingmachine twee verschillende waarden worden aangepast. Door de eenvoudige werking van een turingmachine kan men met dit systeem naar alle waarschijnlijkheid elke berekening uitvoeren zolang de berekening maar beschreven kan worden.
Turingmachine is geen echte machine
Als men het over een turingmachine heeft dan zou men verwachten dat men het over een daadwerkelijke machine heeft. Dit is echter niet het geval. De turingmachine is niet bedacht voor de praktische computertechnologie, dit houdt in dat er geen turingmachine wordt gebouwd. Dit is technisch echter wel mogelijk maar totaal niet praktisch. Er zou dan een machine worden gebouwd met een eindige band die in onderverdeeld in een eindige hoeveelheid vakjes.
Een dergelijke machine zou omvangrijk zijn en totaal geen toegevoegde waarde hebben. Er zijn tegenwoordig al veel betere en complexere machines in een zeer klein formaat beschikbaar. De turingmachine is daarom vooral een theoretische machine een machine die gebruikt kan worden als een gedachte-experiment rond de limieten van mechanische berekeningen.
Waaruit bestaat een turingmachine?
Een turingmachine is geen echte machine die gebouwd wordt. In theorie bestaat de machine echter uit twee onderdelen. Een halfoneindige band waarop een oneindige hoeveelheid vakjes zijn weergegeven. Deze band heeft een beging maar heeft een oneindige lengte. Dit houdt in dat de lengte van de band altijd doorloopt en nooit stopt. Op elk moment is echter slechts een eindig deel van deze band beschreven.
Er is ook een apparaat nodig waarmee de band beschreven kan worden. bovendien moet dit apparaat de gegevens ook kunnen lezen. Een dergelijk apparaat wordt ook wel eindigetoestandsautomaat genoemd. Het feit dat de turingmachine gebruik maakt van een oneindige band maakt het in de praktijk zeer moeilijk om een dergelijke machine echt daadwerkelijk te bouwen. Bovendien heeft deze machine geen praktisch nut.