Hva er Turing komplett?

Turing fullstendighet er når et programmeringsspråk er i stand til å utføre funksjonene til en Turing-maskin. Dette er et konsept for en veldig grunnleggende mekanisk datamaskin, noen ganger beskrevet som den enkleste maskinen som kan betraktes som en datamaskin. Så godt som alle programmeringsspråk som brukes i dag, og i teorien, datamaskinene som kjører dem, har Turing fullstendighet.

Konseptet med Turing-fullstendighet kommer fra Alan Turing, en britisk dataforsker hvis arbeid inkluderte å dechiffrere kodede meldinger under andre verdenskrig. Blant hans arbeid med databehandling var utviklingen av en filosofi om hva en datamaskin faktisk kunne gjøre. Dette inkluderte konseptet om at datamaskiner fungerer ganske enkelt ved å kjøre algoritmer. Det vil si at de følger et fast regelverk for å behandle data og i sin tur løser problemer. Dette betyr at en datamaskin ikke "tenker" eller tar avgjørelser som en person kan.

For å illustrere konseptet beskrev Turing en hypotetisk maskin som han kalte en "a-maskin", med "a" som står for automatisk; andre kalte det senere Turing-maskinen. Maskinen ville behandle en rulle med tape som kunne bevege seg bakover eller fremover og inneholdt en linje med symboler. Når som helst kan maskinen behandle ett symbol og om nødvendig endre det. For konseptets formål kan båndets rulle være uendelig lang, noe som betyr at datamaskinens minne ikke i seg selv var begrenset. Dette er en analogi for ideen om at når en datamaskin har et sett instruksjoner som skal følges, er datamengden den kan bruke disse instruksjonene bare underlagt fysiske grenser.

Ironisk nok har de fleste datamaskiner i dag ikke Turing-fullstendighet. Dette fordi de har begrensninger på tilgjengelig lagringsplass og dermed dataene de kan behandle. De har også fysiske begrensninger, spesielt at de til slutt vil slite seg. Det er faktisk programmeringsspråket som har Turing-fullstendighet. På grunn av dette er en datamaskin som kjører et slikt program ikke en Turing-datamaskin, men kan brukes til å simulere en.

Turing-fullstendighet skal ikke forveksles med Turing-testen. Dette var et eksperiment designet av Turing for å se om datamaskiner kan snakke på naturlig språk. Prinsippet med testen er at hvis et menneske ikke kan fortelle forskjellen mellom en tekstbeskyttet samtale med datamaskinen og et annet menneske, består datamaskinen testen. Mens noen datamaskiner har bestått testen når utvalget av samtaleemner er begrenset, har ingen gjort det i en ubegrenset samtale.