Turingmachine: verschil tussen versies

De Turingmachine is een uiterst eenvoudig mechanisme dat symbolen manipuleert en ondanks deze eenvoud kan men hiermee de logica van elke mogelijke [[computer]] simuleren. Hoewel ze technisch realiseerbaar zijn (zij het met eindige band, onderverdeeld in eindig veel vakjes -– dit is nauwelijks een Turingmachine meer), zijn ze niet bedoeld voor praktische computertechnologie maar als een [[gedachte-experiment]] rond de limieten van mechanische berekeningen; ze worden dus niet echt gebouwd.

Daarnaast is de Turingmachine het begin van een tak van [[wiskunde]] en [[informatica]] die vanuit formele specificaties van een probleem een programma afleidt dat het probleem oplost. Deze oplossingsstrategie (ontwikkeld door [[Tony Hoare]], [[Edsger Dijkstra]] en anderen) gebruikt [[predicatencalculus]] om de stappen uit te rekenen die nodig zijn om een Turingautomaat van de ene toestand naar een volgende te krijgen (maar niet om direct de stappen uit te rekenen die van de begintoestand tot de accepterende toestand leiden --– dat probleem is niet Turing-oplosbaar).