Hvad er Turing -fuldstændighed?

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 beskrevet som den enkleste maskine, der kan betragtes som en computer.Næsten alle programmeringssprog, der er i brug i dag, og i teorien, de computere, der kører dem, har Turing -fuldstændighed.

Begrebet Turing -fuldstændighed kommer fra Alan Turing, en britisk computerforsker, hvis arbejde omfattede dechiffrende kodede meddelelser under 2. verdenskrig.Blandt hans arbejde med computing var udviklingen af en filosofi om, hvad en computer faktisk kunne gøre.Dette omfattede konceptet, at computere blot 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, med A-stående for automatisk;Andre kaldte det senere Turing -maskinen.Maskinen behandler en tape med bånd, der kunne bevæge sig tilbage eller fremad og indeholdt en linje med symboler.På ethvert tidspunkt kunne maskinen behandle et symbol og om nødvendigt ændre det.Med henblik på konceptet kunne båndet være uendeligt lang, hvilket betyder, at computerens hukommelse ikke iboende var begrænset.Dette er en analogi for ideen om, at når en computer har et sæt instruktioner at følge, er mængden af data, det kan anvende disse instruktioner på, 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 tilgængelige lagerplads og dermed de data, de kan behandle.De har også fysiske begrænsninger, især det, som de til sidst vil 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 et.

Turing -fuldstændighed bør ikke forveksles med Turing -testen.Dette var et eksperiment designet af Turing for at se, om computere kan tale på naturligt sprog.Princippet om 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.