Wikipédia

Turing completude

 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.

Definições formais

editar

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

Turing-completude
Um sistema computacional que pode computar qualquer função Turing-computável é chamado Turing-completo (ou Turing-poderoso). Com outras palavras, tal sistema é aquele que pode simular uma máquina de Turing universal.
Turing-equivalência
Um sistema Turing-completo é chamado Turing-equivalente se toda função que ele puder computar for também Turing-computável; e.g., ele computa precisamente a mesma classe de funções que máquina de Turing. Com outras palavras, um sistema Turing-equivalente é aquele que pode simular, e ser simulado por, uma máquina de Turing-universal. (Todos os sistemas Turing-completo conhecidos são Turing-equivalentes, o que confirma a tese de Church-Turing.)
Universalidade (computacional)
Um sistema é dito universal com respeito a uma classe de sistemas se ele puder computar toda função computável pelos sistemas daquelas classe (ou pode simular cada um daqueles sistemas). Normalmente o termo universalidade é taticamente usado com respeito a uma classe de sistemas Turing-completos. O termo “fracamente universal” é às vezes usados para distinguir um sistema (e.g. a autómato celular) cuja universalidade é alcançada apenas pela modificação da definição padrão de máquina de Turing a fim de incluir entradas com uma quantidade infinita de 1s.

Visão geral

editar

A Turing-completude, assim denominada em memória a Alan Turing, é importante para que todo dispositivo de computador do mundo real possa 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 atribuido 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.

A máquina analítica de Charles Babbage (1830) teria sido a primeira máquina de Turing-completa se tivesse sido construída na época em que foi desenhada. Babbage admirava a forma como a máquina era capaz de realizar grandes cálculos, até mesmo raciocínios de lógica primitiva, mas ele não gostava do fato de que nenhuma outra máquina pudesse fazer melhor. De 1830 a 1940, máquinas mecânicas de calcular como somadores ou multiplicadores foram construidas e aprimoradas, mas elas não podiam realizar saltos como “if/goto” e dessa forma não podiam ser chamadas de computadores.

Em meados do século XIX Leopold Kronecker formulou noções de computação, definindo funções recursivas primitivas. Essas funções, porém, não são suficientes para a construção de um computador universal, pois as instruções que computam elas não permitem um laço infinito. No início do século XX David Hilbert fez um programa “axiomatizar” tudo da matemática com axiomas precisos e regras lógicas de dedução precisas, o que era possível de ser feito por uma máquina. Pouco tempo depois, ficou claro que um pequeno conjunto de regras de dedução era suficientes para produzir as consequencias de qualquer conjunto de axiomas. Essas regras foram provadas serem suficientes para produzir qualquer teorema, por Kurt Gödel em 1930. O teorema da completude de Gödel de 1930, implicitamente contem a definição de computador universal, pois as regras lógicas agindo em alguns axiomas da aritmética irá eventualmente provar, como um teorema, o resultado de qualquer computação.

A noção atual de computação foi isolada logo depois, começando com o teorema da incompletude de Gödel. Esse teorema mostrou que sistemas axiomáticos eram limitados quando lidavam com computações que deduziam seus próprios teoremas. Church e depois Turing identificaram o núcleo computacional do teorema da incompletude, e foram capazes de produzir problemas indecidíveis. Esse trabalho, junto com o trabalho de Gödel sobre funções recursivas gerais, estabeleceram que existem conjuntos simples de instruções, que, quando colocados juntos, são capazes de produzir qualquer computação. O trabalho de Gödel mostrou que a noção de computação é essencialmente única.

John von Neumann foi inspirado por esses resultados e desenhou as atuais máquinas de computação universais. As primeiras linguagens formais de programação, da década de 30, mostraram que tais computadores eram úteis. A verdadeira primeira implementação de uma máquina Turing-completa apareceu em 1941: o computador controlado por programas, mas a primeira máquina explicitamente desenhada para ser Turing-completa e ser apreciada como sendo universal foi o ENIAC, de 1946. Essa máquina era capaz de resolver uma grande variedade de problemas importantes na década de 40, muitos deles relacionados a construção de bombas atômicas.

Todas as leis da física têm consequencias que são computáveis através de uma série de aproximações em um computador digital. Uma hipótese chamada “física digital” diz que isso não é coincidência, que é porque o universo por si só é computável em uma máquina de Turing-universal. Isso implicaria que não é possível construir fisicamente um computador mais potente que uma máquina de Turing-universal.

Teoria da computação

editar

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 ira 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 vai analisar 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-completo 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.

Exemplos

editar

Os sistemas computacionais(algebra, 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:

Maioria das linguagem 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, usaria 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.

Turing-completude em SQL é implementado através de componentes padrões avançados, ilustrando uma razão pela qual linguagens não Turing-completas relativamente poderosas são raras: quanto mais poderosa a linguagem é inicialmente, mais complexos são os deveres aos quais é aplicado e mais cedo a sua falta de completudo é vista como uma barreira, encorajando sua extensão até que se torne Turing-completa.

Cálculo lambda sem tipo é Turing-completo, mas muitos lambda cálculos tipados, incluindo System F, não são. A importância de sistemas tipados é baseada na sua habilidade de apresentar o maiot número de programas de computador típicos na mesma medida em que detecta erros.

Regra 110 e o Jogo da Vida de Conway, ambos autômato celular, são turing-completos.

Linguagens não Turing-completas

editar

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 automato é 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.

Linguagem de dados

editar

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.

Ver também

editar

Referências

editar
Obtida de "https://pt.wiki.x.io/w/index.php?title=Turing_completude&oldid=63937889"