Door Aad Offerman

Freelancer

Turing-machine: de grenzen van berekenbaarheid

Meer Turing-machines

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'.


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.

Tweakers maakt gebruik van cookies

Tweakers plaatst functionele en analytische cookies voor het functioneren van de website en het verbeteren van de website-ervaring. Deze cookies zijn noodzakelijk. Om op Tweakers relevantere advertenties te tonen en om ingesloten content van derden te tonen (bijvoorbeeld video's), vragen we je toestemming. Via ingesloten content kunnen derde partijen diensten leveren en verbeteren, bezoekersstatistieken bijhouden, gepersonaliseerde content tonen, gerichte advertenties tonen en gebruikersprofielen opbouwen. Hiervoor worden apparaatgegevens, IP-adres, geolocatie en surfgedrag vastgelegd.

Meer informatie vind je in ons cookiebeleid.

Sluiten

Toestemming beheren

Hieronder kun je per doeleinde of partij toestemming geven of intrekken. Meer informatie vind je in ons cookiebeleid.

Functioneel en analytisch

Deze cookies zijn noodzakelijk voor het functioneren van de website en het verbeteren van de website-ervaring. Klik op het informatie-icoon voor meer informatie. Meer details

janee

    Relevantere advertenties

    Dit beperkt het aantal keer dat dezelfde advertentie getoond wordt (frequency capping) en maakt het mogelijk om binnen Tweakers contextuele advertenties te tonen op basis van pagina's die je hebt bezocht. Meer details

    Tweakers genereert een willekeurige unieke code als identifier. Deze data wordt niet gedeeld met adverteerders of andere derde partijen en je kunt niet buiten Tweakers gevolgd worden. Indien je bent ingelogd, wordt deze identifier gekoppeld aan je account. Indien je niet bent ingelogd, wordt deze identifier gekoppeld aan je sessie die maximaal 4 maanden actief blijft. Je kunt deze toestemming te allen tijde intrekken.

    Ingesloten content van derden

    Deze cookies kunnen door derde partijen geplaatst worden via ingesloten content. Klik op het informatie-icoon voor meer informatie over de verwerkingsdoeleinden. Meer details

    janee