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.

Begreppet 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 innebär 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-stående för automatisk;Andra kallade det senare Turing -maskinen.Maskinen skulle bearbeta en rulle med tejp som kunde flytta tillbaka eller framåt och innehöll en rad symboler.När som helst kan maskinen bearbeta en symbol och vid behov ändra den.För 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 som den kan tillämpa dessa instruktioner 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 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, 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 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 samtalsområdet är begränsat, har ingen gjort det i obegränsad konversation.