Från Rilpedia

Denna artikel kan behöva städas upp för att leva upp till Wikipedias artikelstandard. Förbättra gärna artikeln om du kan, och diskutera frågan på diskussionssidan.

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

Begreppet turingkomplett härleds till dess upphovsman Alan Turing (1912–1954).

Ett programspråk anses vara turingkomplett då man kan beräkna samtliga beräkningsbara problem i det, oavsett hur lång tid och hur mycket minnesutrymme problemet kräver för att beräknas.

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