Versie van 17 jan 2009 00:07 bewerken GrouchoBot (overleg \| bijdragen) 212.456 bewerkingen k robot Erbij: lv:Tjūringa mašīna ← Oudere bewerking		Versie van 14 feb 2009 13:28 bewerken ongedaan maken 94.208.222.130 (overleg) →‎Betekenis van de Turingmachine Nieuwere bewerking →
Regel 82: Mechanisch berekenbaar wordt normaal gesproken ''algoritmisch berekenbaar'' genoemd. Een probleem P is algoritmisch berekenbaar als er een [[algoritme]], een stappenplan, bestaat dat het probleem oplost. Als er een Turingmachine bestaat dat een probleem oplost, dan bestaat een dergelijk algoritme. En omgekeerd. Wat betekent het ~~dat~~als een Turingmachine een probleem oplost? Een probleem P wordt opgelost door een Turingmachine als er een Turingmachine TM is die P ''beslist'': voor iedere instantie van P (iedere invoer die een voorbeeld is van probleem P), eindigt de TM in de accepterende of afwijzende toestand. Een dergelijke Turingmachine TM heet een ''beslisser'' voor probleem P. Daarnaast kennen we ook het concept van een ''herkenner'' voor P. Dit is een Turingmachine die, voor iedere instantie van P, weliswaar niet vastloopt maar verder voor die instantie ook niet de accepterende of afwijzende toestand hoeft te bereiken. Een herkenner kan dus ook een oneindig lange berekening uitvoeren. Dit noemen we over het algemeen geen oplossing van P.

Turingmachine: verschil tussen versies