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.




