I informatikk og logikk sies et formelt system å være komplett i betydningen Turing eller Turing-complete (etter lag av engelsk Turing-complete ) hvis det har en uttrykkskraft som minst tilsvarer den for Turing-maskiner . I et slikt system er det derfor mulig å programmere hvilken som helst Turing-maskin.
Denne forestillingen blir gjort relevant av Kirkens avhandling , som postulerer eksistensen av en naturlig forestilling om beregbarhet. Dermed sammenfaller den uttrykksfulle kraften til Turing-maskiner med den for rekursive funksjoner , lambdakalkulator eller til og med tellemaskiner .
Selv om visse beregningsmodeller, kalt hyperkomputere , er strengere uttrykksfulle enn Turing-maskiner, er disse modellene gjenstander for spekulasjoner (som for eksempel krever å utføre et uendelig antall operasjoner, eller å beregne på tallsettet. Reell ), og det er ikke kjent om de er fysisk gjennomførbare. Under disse forholdene antar Kirkens avhandling universaliteten til beregningsmodellen for Turing-maskinen: ethvert Turing-komplett system ville faktisk være ekvivalent med Turing-maskiner.
I likhet med en beregningsmodell sies det at et dataspråk er Turing-komplett hvis det tillater at alle beregningsfunksjoner blir representert i betydningen Turing og Church (til tross for endeligheten i dataminnet).
Noen forfattere tar denne egenskapen for definisjonen av et programmeringsspråk , men andre definisjoner kan velges.
De vanlige programmeringsspråkene ( C , Java ...) er Turing-komplette fordi de har alle ingrediensene som er nødvendige for simulering av en universell Turing-maskin (tell, sammenlign, les, skriv osv.). C ++ -språket er også Turing-komplett, og delsettet som tillater generell programmering ( maler ) er også .
SQL- språket , opprinnelig ufullstendig i Turings forstand, ble slik med SQL: 1999-standarden slik at det kunne skrive rekursive spørsmål .
LaTeX- språket (fra TeX ), ment for dokumentkomposisjon, er også Turing-komplett.
HTML- språket alene er ikke Turing-komplett, men det er bevist at CSS- språket (i versjon 3) gjør det mulig å bygge den elementære mobilautomaten til kode 110 (se regel 110 (en) ), kjent for å være universell. følelse av Turing. Disse to språkene er ofte uatskillelige, vi kan konkludere med at HTML + CSS er Turing-komplett, og denne tilknytningen gjør det derfor teoretisk til et programmeringsspråk.
Et Turing-komplett språk arver egenskapene til en Turing-maskin. For eksempel avslutningsproblemet er undecidable , så det er umulig å skrive et program som sier om et vilkårlig program gitt til det ender eller ikke.
Noen språk dedikert til å håndtere spesifikke problemer er ikke Turing-komplette. System F , en lambda calculus formalisme er et eksempel. Dessuten - etter design - er totale språk (en) , der alle beregninger nødvendigvis slutter (som Gallina- språket til Coq- bevis assistent ), heller ikke Turing-komplette. Imidlertid er sistnevnte i praksis i stand til å beregne alt som er av interesse, med andre ord de kan implementere alle funksjonene vi måtte trenge i det praktiske livet; beregningene som unnslipper dem, har enten en kompleksitet utover det man kan tenke seg og det som kan realiseres, eller slutter ikke. Sammensetningen må da demonstrere avslutningen av programmene, eller kreve interaksjon med programmereren for noen demonstrasjoner, men dette er prisen å betale for kodekvalitet som er riktig ved konstruksjon.
Noen spill og programvare er Turing-komplette ved et uhell, uten at forfatterne deres ønsker eller vurderer det:
" Det faktum at alle standard programmeringsspråk uttrykker nøyaktig klassen av delvis rekursive funksjoner, blir ofte oppsummert av utsagnet om at alle programmeringsspråk er fullstendig Turing. "
“ Et programmeringsspråk er et språk som er ment for uttrykk for dataprogrammer og som er i stand til å uttrykke ethvert dataprogram. Dette er ikke en vag forestilling. Det er en presis teoretisk måte å bestemme om et dataspråk kan brukes til å uttrykke et hvilket som helst program, nemlig ved å vise at det tilsvarer en universell Turing-maskin. "