Turingmachine: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
de band is geen onderdeel van de machine |
Labels: Bewerking via mobiel Bewerking via mobiele website |
||
Regel 95:
Sinds 1936 hebben onderzoekers gekeken naar zeer veel verschillende varianten van het turingmodel van berekenbaarheid en naar wat hun aanpassingen betekenden voor de beslissingskracht van de nieuwe machines.
Voor de meeste varianten geldt dat de beslissingskracht niet verandert, omdat die varianten gesimuleerd kunnen worden op een "normale" turingmachine. Voorbeelden hiervan zijn turingmachines met meerdere banden (en koppen), turingmachines met één band met meerdere koppen (de parallelle machines, die gesimuleerd kunnen worden door iedere band te verplaatsen naar een eigen sectie van de band op een "normale" machine), machines met meerzijdig oneindige banden (zet de invoer in het midden van de "normale" band en laat de turingmachine beginnen
Een variant die niet krachtiger is, maar wel een bijzonder effect heeft is de non-deterministische turingmachine (de functie <math>\delta</math> verbindt ieder paar (toestand, teken) dan aan één '''of meer''' triples (toestand, teken, richting). Deze non-deterministische machine (NDTM) kan gesimuleerd worden door op de "normale" turingmachine ''alle mogelijke'' berekeningen van NDTM parallel aan elkaar uit te voeren. Eindigt een van de mogelijke berekeningen van NDTM in een accepterende toestand, dan komt de "normale" machine hem tegen. Dit maakt de "normale" machine wel extreem langzamer dan de NDTM: een TM die equivalent is aan een NDTM heeft voor dezelfde invoer als die NDTM, bestaande uit n tekens, <math>2^{2^n}</math> zoveel stappen als de NDTM nodig om de berekening uit te voeren.
| |||