Vad är Turing fullständighet?

Turing -fullständighet är när ett programmeringsspråk kan utföra funktionerna hos 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 har datorerna som driver dem Turing fullständighet.

Konceptet med Turing -fullständighet kommer från Alan Turing, en brittisk datavetare vars arbete inkluderade dechiffrering 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 behandla data och i sin tur lösa problem. Detta betyder att en dator inte "tänker" eller fatta beslut som en person kan.

för att illustrera konceptet,Turing beskrev en hypotetisk maskin som han kallade en "A-maskin", med "A" stående för automatisk; Andra kallade det senare Turing -maskinen. Maskinen skulle bearbeta en rulle med tejp som kunde röra sig eller framåt och innehöll en rad symboler. När som helst kan maskinen bearbeta en symbol och, vid behov, ändra den. I konceptets syfte kunde tejprullen 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 instruktioner endast föremål för fysiska gränser.

ironiskt nog har de flesta datorer idag inte faktiskt fullständighet. Detta beror på att de har begränsningar av det tillgängliga lagringsutrymmet och därmed de data de kan behandla. 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, men kan användas för att simulera en.

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