Turing completude

Na teoria da computação, a completude de Turing ou Turing-completude (do inglês: Turing-completeness; termo cunhado em memória de Alan Turing), também denominado por 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 (simular a lógica de qualquer algoritmo de computador). Um computador é dito completo ou universal se e somente se puder ser usado para controlar a máquina de Turing (a máquina digital primitiva e universal), assim podendo controlar qualquer computador. Um exemplo clássico é o cálculo lambda (um sistema formal que estuda funções recursivas computáveis). Um computador universal também pode ser 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 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, no qual dois computadores "P" e "Q" são chamados de equivalentes se "P" pode simular "Q" e "Q" pode simular "P". Assim, um sistema...