Turingkomplett

Från Rilpedia

(Omdirigerad från Turingkomplett maskin)
Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif


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

Personliga verktyg