Turing completude

Na teoria da computação, alguns termos relacionados são usados para descrever o poder computacional de um sistema computacional (como uma máquina abstrata ou uma linguagem de programação):

A Turing-completude, assim denominada em memória a Alan Turing, permite afirmar que todo dispositivo de computador do mundo real pode ser simulado por uma máquina de turing universal. A tese de Church-Turing diz que é uma lei da natureza o fato de que uma máquina de Turing pode, a princípio, efetuar qualquer tipo de cálculo que qualquer outro computador programável efetue. Obviamente, isso não diz nada a respeito do esforço requerido para escrever o programa, ou o tempo que seria gasto pela máquina para efetuar o cálculo, ou quaisquer habilidades que a máquina possua que não tenham a ver com computação. Enquanto máquinas verdadeiramente Turing-completas precisam de quantidade ilimitada de memória, Turing-completude é normalmente atribuída a máquinas físicas ou linguagem de programação que seriam universais se tivessem capacidade de endereçamento e memória ilimitadas. Todos os computadores modernos são Turing-completos nesse sentido mais livre. Eles são autômato linearmente limitado ou autômatos linearmente limitados completos.

O primeiro resultado da teoria da computação foi a descoberta de que é impossível, no geral, prever o que um programa Turing-completo irá fazer em um tempo arbitrariamente longo. Por exemplo, é impossível determinar para qualquer par <entrada, programa> se o programa, operando sobre a entrada, irá parar ou entrará em laço infinito (veja problema da parada). É impossível determinar se o programa irá retornar “verdadeiro” ou “falso”. Para qualquer característica do programa sobre uma eventual saída, é impossível determinar se essa característica se confirmará. Isso pode causar problemas na prática, quando se analisa programas do mundo real. Uma forma de prevenir isso é fazer com que o programa pare depois de um certo período de tempo, ou limitar a quantidade de instruções de controle de fluxo. Tais sistemas não são Turing-completos pela sua construção. Outro teorema mostra que há problemas que podem ser resolvidos por linguagens Turing-completas e que não podem ser resolvidos por nenhuma linguagem com apenas a habilidade sobre laços infinitos. (e.g., qualquer linguagem que garantir que um programa irá sempre parar). Dada uma linguagem que garante parada, a função computável que é produzida pelo argumento de diagonalização de Cantor sobre todas as funções computáveis naquela linguagem não é computável naquela linguagem.

Os sistemas computacionais (álgebra, cálculo) que são discutidos como sistemas Turing-completos são aqueles com intuito de auxiliar no estudo da ciência da computação. Eles foram feitos com a intenção de ser os mais simples possíveis, de tal forma que seria mais fácil de entender os limites da computação. Exemplos de alguns: A maioria das linguagens de programação, convencionais e não convencionais, são Turing-completas. Isso inclui: As técnicas específicas de linguagem usadas para atingir a Turing-completude podem ser um pouco diferentes uma das outras. Sistemas Fortran usariam construtores de laço ou até mesmo goto (programação) para conseguir repetições; Haskell e Prolog, com sua falta de loop quase total, usariam recursão. Turing-completude é uma colocação abstrata de habilidade, mais que uma prescrição de técnicas específicas de uma linguagem utilizadas para implementar aquela habilidade.

Há muitas linguagens computacionais que não são Turing-completas. Um exemplo é o conjunto de linguagem regular, mais comumente expressão regular, que são geradas por máquina de estados finitos. Uma extensão mais poderosa, mas ainda não Turing-completa, de autômato é o autômato com pilha. Em algumas linguagens, todas as funções são totais e devem terminar, como em Charity e Epigram. Charity usa um sistema de tipos e construtores de controle baseado na teoria da categoria, enquanto Epigram usa tipos dependente.

Linguagens como XML, JSON, YAML e S-expression não são Turing-completas porque elas são usadas apenas para representar dados estruturados, e não descrever computação. Elas são normalmente referidas como linguagem de marcação, ou mais adquadamente como “linguagem de descrição de dados”. Linguagens não Turing-completas, especialmente linguagens de dados, são desejáveis no sentido em que permitem que sejam “manipuladas”, o que, contudo, às vezes também se aplica a linguagens Turing-completas, mais notavelmente Lisp (linguagem de programação) e muitos de seus dialetos como Scheme. Isso é codificado no princípio de “web design” conhecido como “Regra do Menor Poder”, que recomenda evitar o uso de linguagens Turing-completas, e usar linguagens menos poderosas que satisfazem uma tarefa, para que dessa forma os dados possam ser reutilizados e transformados mais facilmente.