Turingkomplett

Turingkomplett är ett begrepp som lanserades av den brittiske matematikern Alan Turing (1912–1954). Ett programspråk anses vara turingkomplett då man kan beräkna samtliga beräkningsbara problem i det, givet tillräcklig tid och tillräckligt minnesutrymme. En maskin anses vara turingkomplett när den kan utföra de operationer som behövs för att kunna beräkna alla beräkningsbara problem som finns. Denna maskin är då en turingmaskin. I teorin kan en maskin som är turingkomplett exekvera samtliga programvaror för andra turingkompletta maskiner, förutsatt att programvaran skrivs om för den aktuella maskinens hårdvara, eller körs i en emulator.