Niet-Deterministische Turing Machine
Interessant aan NP-problemen is dat antwoorden weliswaar moeilijk te vinden zijn, maar dat eenmaal gegeven oplossingen wel makkelijk te verifiëren zijn. Een bekend NP-Compleet probleem is bijvoorbeeld het Traveling Salesman Problem. Daarbij moet een handelsreiziger alle steden op een lijst bezoeken. Het vinden van een route met een bepaalde maximale lengte blijkt heel snel moeilijker te worden naarmate het aantal steden op de lijst toeneemt. Voor een eenmaal gegeven route is het echter heel makkelijk om te controleren of deze inderdaad korter dan de gevraagde afstand is - daarvoor hoef je immers alleen maar de onderlinge afstanden op te tellen.
Voor deze zogenaamde beslissingsproblemen is de Niet-Deterministische Turing Machine bedacht. Deze bevat een gokmodule die vooraf een mogelijke oplossing op de tape zet. Het verifiëren van dit antwoord kan dan inderdaad in polynomiale tijd gebeuren. Een alternatieve uitwerking bevat geen gokmodule maar geeft de rekeneenheid van de NDTM de mogelijkheid om meerdere transities tegelijk uit te voeren - vandaar de naam 'non-deterministisch'./i/1340345340.jpeg?f=imagenormal "AO Scan NDTM")
In de praktijk bestaat er natuurlijk geen gokmodule die in een polynomiale tijdspanne een goede oplossing kan leveren - anders was het een P-probleem geweest dat we met een deterministische Turing-machine hadden kunnen oplossen. Enerzijds benadrukt dit nog eens het theoretische karakter van de Turing-machines. Anderzijds brengen quantumcomputers de oplossing voor dit soort berekeningen wel dichterbij. Helaas wordt er vermoed dat NP-Complete problemen ook met quantummachines niet in polynomiale tijd opgelost kunnen worden.
Universal Turing Machine
Er zijn nog diverse andere Turing-machines. De Universele Turing Machine bijvoorbeeld is een systeem dat andere Turing-machines kan simuleren. Behalve de invoer staat dan ook een beschrijving van de te simuleren machine op de tape. Daarmee komt dit model in de buurt van de Von Neumann-architectuur, waarbij het algoritme hetzelfde geheugen gebruikt als de input en output.
Van de verschillende manieren om de berekenbaarheid van problemen te modelleren, is de Turing-machine de meest gebruikte. Twee andere zijn de lamdba-calculus en recursie. Volgens de Church-Turing-thesis maakt het ook niet uit hoe je complexiteit modelleert: elk effectief algoritme kan met alle drie modellen worden beschreven. Anders gezegd: de drie methoden zijn Turing-equivalent.
:strip_exif()/i/2000637024.jpeg?f=fpa)
/i/1348829391.png?f=fpa)
:strip_exif()/i/1295441491.gif?f=fpa)
/i/1290592098.png?f=fpa)
:strip_exif()/i/1202235552.gif?f=fpa)
/i/1218702793.png?f=fpa)