Completude de Turing - Turing completeness

Na teoria da computabilidade , um sistema de regras de manipulação de dados (como um conjunto de instruções de computador , uma linguagem de programação ou um autômato celular ) é considerado Turing-completo ou computacionalmente universal se puder ser usado para simular qualquer máquina de Turing . Isso significa que este sistema é capaz de reconhecer ou decidir outros conjuntos de regras de manipulação de dados. A integridade de Turing é usada como uma forma de expressar o poder desse conjunto de regras de manipulação de dados. Praticamente todas as linguagens de programação hoje são Turing-completas. O conceito foi batizado em homenagem ao matemático e cientista da computação inglês Alan Turing .

Um conceito relacionado é o da equivalência de Turing  - dois computadores P e Q são chamados de equivalentes se P pode simular Q e Q pode simular P. A tese de Church-Turing conjectura que qualquer função cujos valores podem ser calculados por um algoritmo pode ser calculada por um Máquina de Turing e, portanto, se qualquer computador do mundo real pode simular uma máquina de Turing, é Turing equivalente a uma máquina de Turing. Uma máquina de Turing universal pode ser usada para simular qualquer máquina de Turing e, por extensão, os aspectos computacionais de qualquer computador do mundo real possível.

Para mostrar que algo é Turing-completo, basta mostrar que pode ser usado para simular algum sistema de Turing-completo. Por exemplo, uma linguagem imperativa é Turing-completa se tiver ramificação condicional (por exemplo, instruções "if" e "goto" ou uma instrução "branch if zero"; consulte o computador de conjunto de uma instrução ) e a capacidade de alterar uma instrução arbitrária quantidade de memória (por exemplo, a capacidade de manter um número arbitrário de itens de dados). Claro, nenhum sistema físico pode ter memória infinita; mas se a limitação da memória finita for ignorada, a maioria das linguagens de programação são, de outra forma, Turing-completas.

Uso não matemático

No uso coloquial , os termos "Turing-completo" e "equivalente de Turing" são usados ​​para significar que qualquer computador de uso geral do mundo real ou linguagem de computador pode simular aproximadamente os aspectos computacionais de qualquer outro computador de uso geral do mundo real ou linguagem de computador.

Computadores reais construídos até agora podem ser analisados ​​funcionalmente como uma máquina de Turing de fita única (a "fita" correspondente à sua memória); assim, a matemática associada pode ser aplicada abstraindo sua operação suficientemente longe. No entanto, os computadores reais têm recursos físicos limitados, então eles são apenas autômatos lineares completos. Em contraste, um computador universal é definido como um dispositivo com um conjunto de instruções completo de Turing, memória infinita e tempo infinito disponível.

Definições formais

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

Completude de Turing
Um sistema computacional que pode computar todas as funções Turing- computáveis é chamado de Turing-completo (ou Turing-poderoso). Alternativamente, tal sistema pode simular uma máquina de Turing universal .
Equivalência de Turing
Um sistema Turing-completo é chamado de Turing-equivalente se todas as funções que ele pode computar também são Turing-computáveis; isto é, ele calcula precisamente a mesma classe de funções que as máquinas de Turing . Alternativamente, um sistema equivalente de Turing é aquele que pode simular e ser simulado por uma máquina de Turing universal. (Todos os sistemas Turing-completos fisicamente implementáveis ​​conhecidos são Turing-equivalentes, o que adiciona suporte à tese de Church-Turing .)
Universalidade (computacional)
Um sistema é denominado universal em relação a uma classe de sistemas se puder computar todas as funções computáveis ​​pelos sistemas dessa classe (ou pode simular cada um desses sistemas). Normalmente, o termo universalidade é usado tacitamente com respeito a uma classe de sistemas Turing-completa. O termo "fracamente universal" é algumas vezes usado para distinguir um sistema (por exemplo, um autômato celular ) cuja universalidade é alcançada apenas pela modificação da definição padrão da máquina de Turing de modo a incluir fluxos de entrada com infinitos 1s.

História

A integridade de Turing é significativa porque todo projeto do mundo real para um dispositivo de computação pode ser simulado por uma máquina de Turing universal . A tese de Church-Turing afirma que esta é uma lei da matemática - que uma máquina de Turing universal pode, em princípio, realizar qualquer cálculo que qualquer outro computador programável pode. Isso não diz nada sobre o esforço necessário para escrever o programa , ou o tempo que a máquina pode levar para realizar o cálculo, ou quaisquer habilidades que a máquina possa possuir que não tenham nada a ver com computação.

O motor analítico de Charles Babbage (1830) teria sido a primeira máquina de Turing-completa se tivesse sido construída na época em que foi projetada. Babbage percebeu que a máquina era capaz de grandes feitos de cálculo, incluindo raciocínio lógico primitivo, mas não percebeu que nenhuma outra máquina poderia fazer melhor. De 1830 a 1940, máquinas de calcular mecânicas, como somadores e multiplicadores, foram construídas e aprimoradas, mas não podiam realizar um desvio condicional e, portanto, não eram Turing-completas.

No final do século 19, Leopold Kronecker formulou noções de computabilidade, definindo funções recursivas primitivas . Essas funções podem ser calculadas por computação mecânica, mas não são suficientes para fazer um computador universal, porque as instruções que as calculam não permitem um loop infinito. No início do século 20, David Hilbert liderou um programa para axiomatizar toda a matemática com axiomas precisos e regras lógicas de dedução precisas que poderiam ser executadas por uma máquina. Logo ficou claro que um pequeno conjunto de regras de dedução é suficiente para produzir as consequências de qualquer conjunto de axiomas. Essas regras foram provadas por Kurt Gödel em 1930 como sendo suficientes para produzir todos os teoremas.

A noção real de computação foi isolada logo depois, começando com o teorema da incompletude de Gödel . Este teorema mostrou que os sistemas de axiomas eram limitados ao raciocinar sobre a computação que deduz seus teoremas. Church e Turing demonstraram independentemente que o Entscheidungsproblem (problema de decisão) de Hilbert era insolúvel, identificando assim o núcleo computacional do teorema da incompletude. Este trabalho, juntamente com o trabalho de Gödel sobre funções recursivas gerais , estabeleceu que existem conjuntos de instruções simples que, quando colocadas juntas, são capazes de produzir qualquer cálculo. O trabalho de Gödel mostrou que a noção de computação é essencialmente única.

Em 1941, Konrad Zuse completou o computador Z3 . Zuse não estava familiarizado com o trabalho de Turing sobre computabilidade na época. Em particular, o Z3 carecia de recursos dedicados para um salto condicional, impedindo-o de ser Turing completo. No entanto, em 1998, foi mostrado por Rojas que o Z3 é capaz de saltos condicionais e, portanto, Turing completo, usando alguns de seus recursos de maneira não intencional.

Teoria da computabilidade

A teoria da computabilidade usa modelos de computação para analisar problemas e determinar se eles são computáveis e em que circunstâncias. O primeiro resultado da teoria da computabilidade é que existem problemas para os quais é impossível prever o que um sistema (Turing-completo) fará ao longo de um tempo arbitrariamente longo.

O exemplo clássico é o problema de parada : crie um algoritmo que recebe como entrada um programa em alguma linguagem Turing-completa e alguns dados a serem fornecidos a esse programa e determina se o programa, operando na entrada, irá eventualmente parar ou continuar para sempre. É trivial criar um algoritmo que pode fazer isso para algumas entradas, mas impossível fazer isso em geral. Para qualquer característica da saída eventual do programa, é impossível determinar se essa característica será mantida.

Essa impossibilidade apresenta problemas ao analisar programas de computador do mundo real. Por exemplo, não se pode escrever uma ferramenta que proteja inteiramente os programadores de escreverem loops infinitos ou que proteja os usuários de fornecer dados que causariam loops infinitos.

Em vez disso, pode-se limitar a execução de um programa apenas por um período fixo de tempo ( tempo limite ) ou limitar o poder das instruções de controle de fluxo (por exemplo, fornecendo apenas loops que iteram sobre os itens de uma matriz existente). No entanto, outro teorema mostra que há problemas solucionáveis ​​por linguagens de Turing-completas que não podem ser resolvidos por nenhuma linguagem com apenas habilidades de looping finito (ou seja, qualquer linguagem garantindo que todo programa acabará parando). Portanto, tal linguagem não é Turing-completa. Por exemplo, uma linguagem na qual os programas têm garantia de conclusão e parada não pode computar a função computável produzida pelo argumento diagonal de Cantor em todas as funções computáveis ​​nessa linguagem.

Oráculos de Turing

Um computador com acesso a uma fita infinita de dados pode ser mais poderoso do que uma máquina de Turing: por exemplo, a fita pode conter a solução para o problema da parada ou algum outro problema indecidível de Turing. Essa fita infinita de dados é chamada de oráculo de Turing . Mesmo um oráculo de Turing com dados aleatórios não é computável ( com probabilidade 1 ), uma vez que existem apenas muitos cálculos contáveis, mas muitos oráculos incontáveis. Portanto, um computador com um oráculo de Turing aleatório pode computar coisas que uma máquina de Turing não pode.

Física digital

Todas as leis conhecidas da física têm consequências que são computáveis ​​por uma série de aproximações em um computador digital. Uma hipótese chamada física digital afirma que isso não é acidente porque o próprio universo é computável em uma máquina de Turing universal. Isso implicaria que nenhum computador mais poderoso do que uma máquina de Turing universal pode ser construído fisicamente.

Exemplos

Os sistemas computacionais (álgebras, cálculos) que são discutidos como sistemas Turing-completos são aqueles destinados ao estudo da ciência da computação teórica . Eles devem ser o mais simples possível, de modo que seja mais fácil entender os limites da computação. Aqui estão alguns:

A maioria das linguagens de programação (seus modelos abstratos, talvez com algumas construções particulares que pressupõem memória finita omitida), convencionais e não convencionais, são Turing-completas. Isso inclui:

Alguns sistemas de reescrita são Turing-completos.

Completude de Turing é uma declaração abstrata de habilidade, ao invés de uma prescrição de recursos de linguagem específicos usados ​​para implementar essa habilidade. Os recursos usados ​​para atingir a integridade de Turing podem ser bem diferentes; Os sistemas Fortran usariam construções de loop ou possivelmente até mesmo instruções goto para obter a repetição; Haskell e Prolog, sem looping quase inteiramente, usariam recursão . A maioria das linguagens de programação descreve cálculos nas arquiteturas de von Neumann , que possuem memória (RAM e registro) e uma unidade de controle. Esses dois elementos tornam essa arquitetura Turing-completa. Mesmo as linguagens funcionais puras são Turing-completas.

A integridade de Turing em SQL declarativa é implementada por meio de expressões de tabela comuns recursivas . Sem surpresa, extensões procedurais para SQL ( PLSQL , etc.) também são Turing-completas. Isso ilustra uma razão pela qual linguagens não-Turing-completas relativamente poderosas são raras: quanto mais poderosa a linguagem é inicialmente, mais complexas são as tarefas às quais ela é aplicada e mais cedo sua falta de completude é percebida como uma desvantagem, encorajando sua extensão até que esteja Turing-completo.

O cálculo lambda não digitado é Turing-completo, mas muitos cálculos lambda digitados, incluindo o Sistema F , não são. O valor dos sistemas digitados é baseado em sua capacidade de representar a maioria dos programas de computador típicos enquanto detecta mais erros.

A Regra 110 e o Jogo da Vida de Conway , ambos autômatos celulares , são Turing-completos.

Completude de Turing não intencional

Alguns jogos e outros softwares são Turing-completos por acidente, ou seja, não por design.

Programas:

Jogos de vídeo:

Mídia social:

Jogos de cartas:

Jogos de pessoa zero (simulações):

Linguagens computacionais:

Hardware do computador:

  • Instrução MOV x86

Biologia:

Linguagens não completas de Turing

Existem muitas linguagens computacionais que não são Turing-completas. Um exemplo é o conjunto de linguagens regulares , que são geradas por expressões regulares e que são reconhecidas por autômatos finitos . Uma extensão mais poderosa, mas ainda não completa de Turing, dos autômatos finitos é a categoria de autômatos empilháveis e gramáticas livres de contexto , que são comumente usados ​​para gerar árvores de análise em um estágio inicial de compilação do programa . Outros exemplos incluem algumas das primeiras versões das linguagens de sombreador de pixel incorporadas nas extensões Direct3D e OpenGL .

Em linguagens de programação totalmente funcionais , como Charity e Epigram , todas as funções são totais e devem ser encerradas. Charity usa um sistema de tipos e construções de controle com base na teoria das categorias , enquanto o Epigram usa tipos dependentes . A linguagem LOOP é projetada para computar apenas as funções recursivas primitivas . Todos esses computam subconjuntos apropriados das funções computáveis ​​totais, uma vez que o conjunto completo de funções computáveis ​​totais não é computável enumerável . Além disso, como todas as funções nessas linguagens são totais, algoritmos para conjuntos recursivamente enumeráveis não podem ser escritos nessas linguagens, em contraste com as máquinas de Turing.

Embora o cálculo lambda (não digitado ) seja Turing-completo, o cálculo lambda simplesmente digitado não é.

Linguagens de dados

A noção de completude de Turing não se aplica a linguagens como XML , HTML , JSON e YAML , porque eles são normalmente usados ​​para representar dados estruturados, não para descrever computação. Às vezes, são chamadas de linguagens de marcação ou, mais apropriadamente, de "linguagens de contêiner" ou "linguagens de descrição de dados".

Veja também

Notas

Referências

Leitura adicional

links externos