Turing fullständighet är en egenskap hos en executor (en uppsättning beräkningselement) i beräkningsbarhetsteori , vilket betyder förmågan att implementera vilken beräkningsbar funktion som helst på den . Med andra ord, för varje beräkningsbar funktion finns det ett element som beräknar den (till exempel en Turing-maskin ) eller ett program för en exekutor, och alla funktioner som beräknas av en uppsättning räknare är beräkningsbara funktioner (kanske med viss kodning av indata och utdata).
Fastigheten är uppkallad efter Alan Turing , som utvecklade den abstrakta räknaren, Turing-maskinen, och definierade uppsättningen funktioner som kan beräknas av Turing-maskiner.
De mest använda programmeringsspråken är Turing-komplett. Detta gäller både imperativa språk som Pascal , såväl som funktionella ( Haskell ) och logiska programmeringsspråk ( Prolog ). Vissa programmeringsspråk (Haskell, C++ ) är kompilerings-tid Turing-kompletta förutom körtid Turing fullständighet.
Turing-komplett normal Markov-algoritm , 2-taggsystem , regel 110 cellulär automat , hämmande Petri-net , lambda-kalkyl med beta-reduktion . Obegränsad grammatik är också Turing komplett .
Exempel på Turing-ofullständiga formalismer är finita automater , primitiva rekursiva funktioner , sammanhangsfria och vanliga grammatiker.
I varje Turing-komplett klass av miniräknare finns det en universell klassrepresentant som simulerar exekveringen av en godtycklig given klassrepresentant. Så, till exempel, en universell Turing-maskin på ett band som innehåller chiffer för en godtycklig given Turing-maskin M och dess inmatningssträng B imiterar exekveringen av M på B. För närvarande har universella Turing-maskiner byggts innehållande mindre än 23 instruktioner [1 ] för kombinationer av antalet symboltillstånd 4x6, 5x5. Det universella hämmande Petri-nätet innehåller 56 hörn [2] .