Hvad er Turing komplethed?

Turing-fuldstændighed er, når et programmeringssprog er i stand til at udføre funktionerne på en Turing-maskine. Dette er et koncept til en meget grundlæggende mekanisk computer, sommetider beskrives som den enkleste maskine, der kan betragtes som en computer. Stort set alle programmeringssprog, der bruges i dag, og i teorien, de computere, der kører dem, har Turing-fuldstændighed.

Begrebet Turing-fuldstændighed stammer fra Alan Turing, en britisk datalogi, hvis arbejde omfattede afkryptering af kodede meddelelser under 2. verdenskrig. Blandt hans arbejde med computere var udviklingen af ​​en filosofi om, hvad en computer faktisk kunne gøre. Dette omfattede konceptet om, at computere simpelthen fungerer ved at køre algoritmer. Det vil sige, at de følger et fast sæt regler for at behandle data og til gengæld løse problemer. Dette betyder, at en computer ikke "tænker" eller træffer beslutninger, som en person kan.

For at illustrere konceptet beskrev Turing en hypotetisk maskine, som han kaldte en "a-maskine", hvor "a" står for automatisk; andre kaldte det senere Turing-maskinen. Maskinen behandler en rulle bånd, der kunne bevæge sig tilbage eller fremad og indeholde en linje med symboler. På ethvert tidspunkt kunne maskinen behandle et symbol og om nødvendigt ændre det. I forbindelse med konceptet kunne båndspolen være uendeligt lang, hvilket betyder, at computerens hukommelse ikke i sig selv var begrænset. Dette er en analogi til ideen om, at når en computer først har et sæt instruktioner, der skal følges, er mængden af ​​data, den kan anvende disse instruktioner, kun underlagt fysiske grænser.

Ironisk nok har de fleste computere i dag faktisk ikke Turing-fuldstændighed. Dette skyldes, at de har begrænsninger på den disponible lagerplads og dermed de data, de kan behandle. De har også fysiske begrænsninger, navnlig at de til sidst slides. Det er faktisk det programmeringssprog, der har Turing-fuldstændighed. På grund af dette er en computer, der kører et sådant program, ikke en Turing-computer, men kan bruges til at simulere en.

Turing-fuldstændighed skal ikke forveksles med Turing-testen. Dette var et eksperiment designet af Turing for at se, om computere kan tale på et naturligt sprog. Princippet for testen er, at hvis et menneske ikke kan fortælle forskellen mellem en tekst-kun-samtale med computeren og et andet menneske, består computeren testen. Mens nogle computere har bestået testen, når intervallet af samtaleemner er begrænset, har ingen gjort det i ubegrænset samtale.