Turingkomplett

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2017-12) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Den här artikeln handlar om ett begrepp inom bland annat datavetenskap. För liknande begrepp rörande artificiell intelligens, se Turingtest.

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.

Se även

• Alonzo Church, matematiker
• Logik
• Turingmaskin