Turing machine

Gemeenschappelijke basis

Een Turing machine bestaat uit de volgende componenten (vereenvoudigd):

• Een beperkte reeks toestanden (met één toestand gemarkeerd als begintoestand; tijdens het draaien heeft een Turingmachine altijd een actuele toestand).
• Een oneindige band met opslagcellen en een lees/schrijfapparaat dat over de band kan bewegen.
• Een definitie van een zogenaamde overgangsfunctie

Ook moet een werkalfabet (reeks tekens) worden gedefinieerd.

Wanneer een Turingmachine wordt gestart, moet er een woord (uit het werkalfabet) aanwezig zijn op de oneindige band van de machine. Het lees/schrijf-apparaat leest nu het eerste teken en afhankelijk van de huidige toestand van de Turing machine overschrijft het lees/schrijf-apparaat het teken met een nieuw teken of verplaatst een cel naar links of naar rechts. Bovendien kan de huidige toestand van de machine worden omgeschakeld.

Turing machines die talen beslissen

In de decidabiliteitstheorie wordt van een Turingmachine gezegd dat zij een taal beslist als zij altijd kan bepalen of een bepaald woord al dan niet in een bepaalde taal voorkomt. Daarom heeft de machine gewoonlijk twee speciale toestanden: Aanvaard en Verwerp. Na enige tijd wordt een van de twee toestanden bereikt (afhankelijk van het ingevoerde woord) en wordt de machine gestopt. Als slechts één van de twee toestanden ooit wordt bereikt, wordt gezegd dat de Turing machine een taal semi-beslist.

Turing machines die functies berekenen

Als een Turingmachine wordt gebruikt voor de berekening van functies heeft zij slechts één eindtoestand. Als de machine die toestand bereikt, wordt hij gestopt en kan het resultaat van de functie (afhankelijk van de invoer) op de band worden gevonden.

Impact van Turing machines

Turingmachines zijn niet uitgevonden om in de werkelijkheid te worden gebouwd, maar ze zijn erg belangrijk voor de theoretische informatica, omdat ze een van de eenvoudigste modellen voor computers zijn. De Church-Turing stelling stelt dat alle computers slechts zo krachtig zijn als Turing machines. Dit kan worden gebruikt om te bewijzen of een probleem al dan niet door een computer kan worden opgelost.

Variaties

• Een Turing machine kan bestaan uit meerdere oneindige tapes (en meerdere lees/schrijfapparaten). Het is echter bewezen dat dergelijke machines slechts even krachtig zijn als machines met één tape. Machines met meerdere banden zijn nuttig bij complexere problemen.
• Als een Turingmachine een niet-deterministische overgangsfunctie heeft, kunnen er bij het lezen van een teken meerdere overgangen zijn van de ene toestand naar vele andere. Ook dit vergroot de kracht van Turing machines niet. Maar niet-deterministische Turing machines (zoals ze dan heten) kunnen mogelijk de rekentijd sterk verminderen. Deze vraag wordt behandeld in de P versus NP-discussie en is nog niet opgelost. De meeste wetenschappers nemen echter aan dat niet-deterministische machines voor bepaalde problemen veel sneller kunnen werken.
• Een Universele Turing Machine is een variant die een Turing Machine kan simuleren met een input.