Vad är Turing fullständighet?

Turing fullständighet är när ett programmeringsspråk kan utföra en Turing-maskin. Detta är ett koncept för en mycket grundläggande mekanisk dator, ibland beskrivet som den enklaste maskinen som kan betraktas som en dator. Praktiskt taget alla programmeringsspråk som används idag, och i teorin, datorerna som kör dem, har Turing fullständighet.

Begreppet Turing fullständighet kommer från Alan Turing, en brittisk datorforskare vars arbete inkluderade avkryptering av kodade meddelanden under andra världskriget. Bland hans arbete med datoranvändning var utvecklingen av en filosofi om vad en dator faktiskt kunde göra. Detta inkluderade konceptet att datorer fungerar helt enkelt genom att köra algoritmer. Det vill säga att de följer en fast uppsättning regler för att bearbeta data och i sin tur löser problem. Detta betyder att en dator inte "tänker" eller fattar beslut som en person kan.

För att illustrera konceptet beskrev Turing en hypotetisk maskin som han kallade en "a-maskin", med "a" som står för automatisk; andra kallade det senare Turing-maskinen. Maskinen skulle behandla en bandrulle som kunde röra sig bakåt eller framåt och innehålla en rad symboler. När som helst kan maskinen bearbeta en symbol och vid behov ändra den. För konceptets syfte kan bandets rulle vara oändligt lång, vilket innebär att datorns minne inte i sig var begränsat. Detta är en analogi för idén att när en dator har en uppsättning instruktioner att följa, är mängden data den kan tillämpa dessa anvisningar endast föremål för fysiska gränser.

Ironiskt nog har de flesta datorer idag inte Turing-fullständighet. Detta beror på att de har begränsningar på tillgängligt lagringsutrymme och därmed de data de kan bearbeta. De har också fysiska begränsningar, särskilt att de så småningom kommer att slitna. Det är faktiskt programmeringsspråket som har Turing-fullständighet. På grund av detta är en dator som kör ett sådant program inte en Turing-dator utan kan användas för att simulera en.

Turing-fullständighet bör inte förväxlas med Turing-testet. Detta var ett experiment designat av Turing för att se om datorer kan prata på naturligt språk. Principen för testet är att om en människa inte kan se skillnaden mellan en textsamtal med datorn och en annan människa, klarar datorn testet. Vissa datorer har klarat testet när intervallet av konversationsämnen är begränsat, men ingen har gjort det i obegränsad konversation.