Turing-fuldstændighed er et kendetegn ved en eksekvering (et sæt computerelementer) i beregningsteori , hvilket betyder evnen til at implementere enhver beregnelig funktion på den . Med andre ord, for hver beregnelig funktion er der et element, der beregner den (for eksempel en Turing-maskine ) eller et program for en eksekvering, og alle funktioner beregnet af et sæt regnemaskiner er beregnelige funktioner (måske med en vis indkodning af input og outputdata).
Ejendommen er opkaldt efter Alan Turing , som udviklede den abstrakte lommeregner, Turing-maskinen, og definerede det sæt funktioner, der kunne beregnes af Turing-maskiner.
De mest udbredte programmeringssprog er Turing-komplet. Dette gælder både imperative sprog som Pascal , såvel som funktionelle ( Haskell ) og logiske programmeringssprog ( Prolog ). Nogle programmeringssprog (Haskell, C++ ) er kompilerings-tid Turing-komplet ud over run-time Turing fuldstændighed.
Turing-komplet normal Markov-algoritme , 2-tag-system , regel 110 cellulær automat , hæmmende Petri-net , lambda-regning med beta-reduktion . Ubegrænsede grammatikker er også Turing komplet .
Eksempler på Turing-ufuldstændige formalismer er endelige automater , primitive rekursive funktioner , kontekstfri og regulære grammatikker.
I hver Turing-komplet klasse af regnemaskiner er der en universel klasserepræsentant, der simulerer udførelsen af en vilkårlig given klasserepræsentant. Så f.eks. efterligner en universel Turing-maskine på et bånd, der indeholder chifferen af en vilkårlig given Turing-maskine M og dens inputstreng B udførelsen af M på B. I øjeblikket er der bygget universelle Turing-maskiner indeholdende mindre end 23 instruktioner [1 ] for kombinationer af antallet af symboltilstande 4x6, 5x5. Det universelle hæmmende Petri-net indeholder 56 hjørner [2] .