Naar inhoud
BetaAI Begrippen

AI-begrippen in gewone taal. Zoek een begrip, blader op letter of filter op onderwerp.

Turingmachine

Engels: Turing machine · Ook wel: TM, Turing machine, Turing-machine

In het kort

Een Turingmachine is een wiskundig model van een denkbeeldige machine die tekens op een lange band bewerkt. De machine volgt een vaste tabel met regels: zij leest één teken, schrijft een nieuw teken en verplaatst de leeskop één vakje. Ondanks die eenvoud kan het model elk algoritme uitvoeren, zodat wiskundigen kunnen nagaan welke taken een computer in principe kan berekenen.

Waarom is dit belangrijk?

Met een Turingmachine kunnen informatici onderscheiden welke problemen een programma altijd kan afronden en welke geen enkel programma in alle gevallen oplost. In informaticaopleidingen oefenen studenten die grens aan de hand van het stopprobleem, een vraag die geen programma altijd juist kan beantwoorden. Voor programmeurs en scholieren geeft dat meer inzicht in software, met de beperking dat sommige vragen over programma's nooit helemaal oplosbaar zijn.

Zo werkt het in de praktijk

Het Amerikaanse instituut NIST maakt cryptografiestandaarden die data en communicatie beveiligen. Die standaarden steunen op complexiteitstheorie, die voortkomt uit de Turingmachine. Veel versleuteling rekent erop dat het ontbinden van grote getallen in priemfactoren niet efficiënt lukt.

Onderzoekers van het onderzoeksinstituut CWI in Amsterdam leggen de klassen P en NP vast met een beperkte Turingmachine. De vraag is of die twee klassen samenvallen. Kansgestuurde Turingmachines analyseren snelle priemtests in cryptografische internetprotocollen.

De Church-Turing-these is de werkafspraak dat een procedure berekenbaar is als een Turingmachine haar uitvoert. NIST gebruikt die gedachte bij kwantumcomputers. Een Turingmachine kan zo’n computer nabootsen, dus blijven er grenzen aan wat die aankan.

Bron: en.wikipedia.org

Gecontroleerd op 5 november 2026