Door Aad Offerman

Freelancer

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.

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