Portaal:Informatica/Uitgelicht/8
Een Turingmachine is een uiterst eenvoudig mechanisme dat symbolen manipuleert en ondanks deze eenvoud kan men hiermee de logica van elke mogelijke computer simuleren. Ze werden in 1936 door Alan Turing beschreven. Hoewel ze technisch realiseerbaar zijn, zijn ze niet bedoeld voor praktische computertechnologie maar als een gedachte-experiment rond de limieten van mechanische berekeningen; ze worden dus niet echt gebouwd. De studie van hun abstracte eigenschappen levert diverse inzichten in informatica en complexiteitstheorie.