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 beskriven 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 Turings fullständighet kommer från Alan Turing, en brittisk datavetare vars arbete inkluderade att dechiffrera kodade meddelanden under andra världskriget. Bland hans arbete med datorer 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 fattar beslut som en person kan.
För att illustrera konceptet beskrev Turing en hypotetisk maskin som han kallade en ”a-maskin”, där ”a” står för automatisk; andra kallade den senare för Turing-maskinen. Maskinen skulle bearbeta en rulle med tejp som kunde röra sig bakåt eller framåt och innehöll en rad symboler. Maskinen kan när som helst behandla en symbol och vid behov ändra den. För konceptets syfte kan bandrullen vara oändligt lång, vilket innebär att datorns minne inte var begränsat i sig. Detta är en analogi för tanken att när en dator väl har en uppsättning instruktioner att följa, är mängden data som den kan tillämpa dessa instruktioner på endast föremål för fysiska begränsningar.
Ironiskt nog har de flesta datorer idag faktiskt inte Turing-fullständighet. Det beror på att de har begränsningar på tillgängligt lagringsutrymme och därmed vilken data de kan bearbeta. De har också fysiska begränsningar, framför allt att de så småningom kommer att slitas ut. 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 test. Detta var ett experiment designat av Turing för att se om datorer kan konversera på naturligt språk. Principen för testet är att om en människa inte kan se skillnad på en textkonversation med datorn och en annan människa, klarar datorn testet. Medan vissa datorer har klarat testet när utbudet av samtalsämnen är begränsat, har ingen gjort det i obegränsad konversation.