Turing completude

Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. Ajude a melhorar este artigo inserindo citações no corpo do artigo. (Fevereiro de 2014)

 Nota: Para o uso desse termo na teoria da computação relativa por máquinas oráculo, veja redução de Turing.

Na teoria da computação, a completude de Turing ou Turing-completo (do inglês: Turing-completeness; batizado em memória de Alan Turing), também chamado computacionalmente universal, é um conjunto de regras para manipulação de dados (semelhante a uma linguagem de programação, um autómato celular, um conjunto de instruções) que pode ser usado para resolver qualquer problema de computação (simula a lógica de qualquer algoritmo de computador). este é completo ou universal se e somente se puder ser usado para controlar a máquina de Turing (a máquina digital primitiva e universal), e assim podendo controlar qualquer computador. Um exemplo clássico é o cálculo lambda (um sistema formal que estuda funções recursivas computáveis).

Na prática, completude de Turing significa que, regras seguidas em sequência sobre dados arbitrários podem produzir o resultado de qualquer cálculo. Em linguagens procedurais isso poder ser satisfeito tendo-se, no mínimo, saltos condicionais (usando "if" ou "goto") e a habilidade de modificar arbitrariamente locais da memória RAM (como as variáveis). Para mostrar que algo é Turing-completo, é suficiente mostrar que ele pode ser usado para simular o computador mais primitivo, pois mesmo o tipo mais simples de computador pode ser usado para simular os tipos mais complexos. Todas as linguagens de programação de uso geral e todos os conjuntos de instruções de máquina modernos são Turing-completos, não obstante limitações de memória finita.

Um conceito relacionado a completude é, a equivalência de Turing, onde dois computadores "P" e "Q" são chamados de equivalentes se "P" pode simular "Q" e "Q" pode simular "P".

Um computador universal é definido como um dispositivo com um conjunto de instruções Turing-completo, memória infinita, e um tempo de vida infinito. Todos os sistemas do mundo real necessariamente possuem memória finita, fazendo do verdadeiro computador universal apenas uma construção teórica.

Na teoria da computação, há um conceito bastante relacionado chamado de Turing-equivalência. Dois computadores P e Q são ditos Turing-equivalentes se P puder simular Q e Q puder simular P. Assim, um sistema Turing-completo é aquele que pode simular uma máquina de Turing. Porém, o termo é normalmente usado com o significado de Turing-equivalente a uma máquina de Turing. A razão é que qualquer máquina do mundo real pode ser simulada por uma máquina de Turing, observação esta codificada como a Tese de Church-Turing.

Um computador com acesso a uma fita infinita de dados é às vezes mais poderoso que uma máquina de Turing, pois a fita, a princípio, pode conter a solução para o problema da parada, ou para algum outro problema indecidível. Uma fita infinita de dados é chamada de Turing-oráculo. Até mesmo um Turing-oráculo com dados aleatórios não é computável (com probabilidade 1), pois há um número contável de computações, mas um número incontável de oráculos. Então, um computador com um Turing-oráculo aleatório pode computar coisas que uma máquina de Turing não pode. Uma máquina que é universal, exceto que não possui um Turing-oráculo, é chamada de máquina fracamente universal.