Em ciência da computação e lógica , um sistema formal é considerado completo no sentido de Turing ou Turing-complete (rastreando o inglês Turing-complete ) se tiver um poder expressivo pelo menos equivalente ao das máquinas de Turing . Nesse sistema, é possível programar qualquer máquina de Turing.
Essa noção é tornada relevante pela tese de Church , que postula a existência de uma noção natural de computabilidade. Assim, o poder expressivo das máquinas de Turing coincide com o das funções recursivas , cálculo lambda , ou mesmo máquinas de contagem .
Embora alguns modelos de cálculo, chamados hipercomputadores , sejam estritamente mais expressivos que as máquinas de Turing, esses modelos são objetos de especulação (exigindo, por exemplo, realizar um número infinito de operações, ou calcular sobre o conjunto de números. Reais) e não é saber se são fisicamente viáveis. Sob essas condições, a tese de Church conjectura a universalidade do modelo computacional da máquina de Turing: qualquer sistema completo de Turing seria de fato equivalente a máquinas de Turing.
Como um modelo computacional, uma linguagem de computador é considerada Turing-completa se permitir que todas as funções computáveis sejam representadas no sentido de Turing e Church (apesar da finitude da memória do computador).
Alguns autores consideram esta propriedade para a definição de uma linguagem de programação , mas outras definições podem ser escolhidas.
As linguagens de programação usuais ( C , Java …) são Turing-completas porque têm todos os ingredientes necessários para a simulação de uma máquina de Turing universal (contar, comparar, ler, escrever, etc.). A linguagem C ++ também é Turing-completa, e o subconjunto que permite a programação genérica ( modelos ) também é .
A linguagem SQL , originalmente incompleta no sentido de Turing, tornou-se assim com o padrão SQL: 1999, permitindo-lhe escrever consultas recursivas .
A linguagem LaTeX (do TeX ), destinada à composição de documentos, também é Turing-completa.
A linguagem HTML sozinha não é Turing-completa, embora tenha sido provado que a linguagem CSS (versão 3) permite construir o código de autômato celular elementar 110 (ver Regra 110 (em) ), conhecido por ser universal no sentido de Turing . Essas duas linguagens são freqüentemente inseparáveis, podemos concluir que HTML + CSS é Turing-completo, e essa associação, portanto, teoricamente a torna uma linguagem de programação.
Uma linguagem de Turing completa herda as características de uma máquina de Turing. Por exemplo, o problema de desligamento é indecidível , então é impossível escrever um programa que diga se um programa arbitrário dado a ele termina ou não.
Algumas linguagens dedicadas a lidar com problemas específicos não são Turing-completas. O sistema F , um formalismo de cálculo lambda, é um exemplo. Além disso - por design - linguagens totais (en) , onde todos os cálculos necessariamente terminam (como a linguagem Gallina do assistente de prova Coq ), também não são Turing-completas. No entanto, estes últimos são, na prática, capazes de calcular tudo o que interessa, ou seja, podem implementar todas as funções de que precisaremos na vida prática; os cálculos que lhes escapam ou têm uma complexidade além do imaginável e realizável, ou não têm fim. A compilação deve então demonstrar o término dos programas ou exigir interação com o programador para algumas demonstrações, mas este é o preço a pagar pela qualidade do código que é correta por construção.
Alguns jogos e softwares são Turing-completos por acidente, sem que seus autores queiram ou considerem isso:
" O fato de que todas as linguagens de programação padrão expressam precisamente a classe de funções recursivas parciais é freqüentemente resumido pela afirmação de que todas as linguagens de programação são Turing completas. "
“ Uma linguagem de programação é aquela que se destina à expressão de programas de computador e que é capaz de expressar qualquer programa de computador. Esta não é uma noção vaga. Existe uma maneira teórica precisa de determinar se uma linguagem de computador pode ser usada para expressar qualquer programa, a saber, mostrando que ela é equivalente a uma máquina de Turing universal. "