Turing-machine: de grenzen van berekenbaarheid

Deterministische Turing-machine

Hoewel Turing-machines al meer dan driekwart eeuw geleden zijn bedacht, zijn ze nog steeds van groot belang voor de complexiteitstheorie. Informatici gebruiken deze conceptuele computers om te bestuderen of bepaalde problemen redelijkerwijs met behulp van computers kunnen worden opgelost. Omdat ze worden gebruikt om bewijzen te construeren, leunen deze modellen zwaar op wiskundige theorie. Desondanks hebben de uitkomsten van deze onderzoeken grote praktische consequenties, onder meer voor gegevensbeveiliging.

De eenvoudigste Turing-machine is de Deterministische Turing-machine. Deze wordt doorgaans voorgesteld als een rekeneenheid met een lees/schrijf-kop en een tape die zich naar beide kanten oneindig uitstrekt. Op de tape staat de input voor de machine, en afhankelijk van het karakter onder de leeskop wordt een nieuw karakter op de tape geschreven en wordt de kop naar links of rechts verplaatst.

De rekeneenheid bevat het programma, niet gedefinieerd in een programmeertaal zoals wij die kennen, maar in de vorm van een Finite-State Machine. Deze kan zich in een aantal states of toestanden bevinden en kan van de ene naar de andere state overgaan; dat heet een transitie.

Voor software-ontwikkelaars is dit een ongebruikelijke manier om een programma te definiëren, maar hardware-ontwikkelaars werken veel aan de hand van dit model. Het is ook mogelijk om een voorzichtige vergelijking tussen de deterministische Turing-machine en een processor te maken. De state wordt dan bepaald door alle processorregisters en de overgangen zijn vastgelegd in de microcode van de cpu, waarin wordt bepaald hoe de registers worden beïnvloed als een machinetaal-instructie wordt uitgevoerd.

We moeten wel bedenken dat deze deterministische Turing-machine niet bedoeld is om een computer of processor te modelleren, maar om iets te kunnen zeggen over de oplosbaarheid van problemen.

• Volgende pagina 3. P =? NP