Versie van 18 jan 2016 11:38 bewerken ErikvanB (overleg \| bijdragen) uitgebreid bevestigde gebruikers, Terugdraaiers 548.640 bewerkingen →‎De turingmachine en de Von Neumann-cyclus ← Oudere bewerking		Versie van 18 jan 2016 11:38 bewerken ongedaan maken ErikvanB (overleg \| bijdragen) uitgebreid bevestigde gebruikers, Terugdraaiers 548.640 bewerkingen →‎Betekenis van de turingmachine Nieuwere bewerking →
Regel 88: Het bestaan van de turingmachine als model betekent dat wiskundigen kunnen nadenken over wat wel en niet berekenbaar is en hoe moeilijk klassen van problemen zijn om op te lossen (dit heet de [[Complexiteitsgraad\|complexiteit]] van een probleem). Sinds 1936 is bewezen dat er problemen zijn die niet ~~Turing~~turing-oplosbaar zijn (er kan geen beslisser voor bestaan). Een voorbeeld is het ''halting problem'' of [[stopprobleem]]. Ook is bewezen dat er problemen zijn die niet ~~Turing~~turing-herkenbaar zijn (er kan geen herkenner voor zijn). Merk overigens op dat het feit dat een probleem niet ~~Turing~~turing-oplosbaar is, niet betekent dat instanties van dat probleem geen oplossingen hebben. Het betekent wel dat er geen turingmachine bestaat die elke instantie van het probleem kan oplossen. ==Varianten op de basismachine en hun uitdrukkingskracht==

Turingmachine: verschil tussen versies