O que é Turing completo?

https://stackoverflow.com/questions/7284

08-06-2019
|

Pergunta

O que significa a expressão "Turing Complete"?

Você pode dar uma explicação simples, sem entrar em muitos detalhes teóricos?

Solução

Aqui está a mais breve explicação:

Um sistema Turing Complete significa um sistema no qual pode ser escrito um programa que encontrará uma resposta (embora sem garantias quanto ao tempo de execução ou memória).

Então, se alguém disser "minha novidade é Turing Complete", isso significa, em princípio (embora muitas vezes não na prática), que poderia ser usado para resolver qualquer problema de computação.

Às vezes é uma piada...um cara escreveu um simulador de Máquina de Turing no vi, então é possível dizer que o vi é o único mecanismo computacional já necessário no mundo.

Outras dicas

Aqui está a explicação mais simples

Alan Turing criou uma máquina que pode pegar um programa e executá-lo e mostrar algum resultado.Mas então ele teve que criar máquinas diferentes para programas diferentes.Então ele criou a "Máquina Universal de Turing" que pode pegar QUALQUER programa e executá-lo.

As linguagens de programação são semelhantes a essas máquinas (embora virtuais).Eles pegam programas e os executam.Agora, uma linguagem de programação é chamada de "Turing completa", se ela puder executar qualquer programa (independentemente da linguagem) que uma máquina de Turing possa executar com tempo e memória suficientes.

Por exemplo:Digamos que exista um programa que pegue 10 números e os some.A máquina de Turing pode executar este programa facilmente.Mas agora imagine que, por algum motivo, sua linguagem de programação não pode fazer a mesma adição, então a máquina de Turing está incompleta.Por outro lado, se ele puder executar qualquer programa como a máquina de Turing universal, então é Turing completo.

A maioria das linguagens de programação modernas, como Java, JavaScript, Perl, etc., são completas porque todas implementam todos os recursos necessários para executar programas como adição, multiplicação, condição if-else, instruções de retorno, maneiras de armazenar/recuperar/apagar dados e assim por diante. .

Atualizar:Você pode aprender mais na postagem do meu blog: "JavaScript Is Turing Complete" — Explicado

De Wikipédia:

A integridade de Turing, nomeada após Alan Turing, é significativa, pois todo design plausível para um dispositivo de computação até agora avançado pode ser emulado por uma máquina universal de Turing-uma observação que se tornou conhecida como tese de ator de igreja.Assim, uma máquina que pode atuar como uma máquina de Turing universal pode, em princípio, executar qualquer cálculo de que qualquer outro computador programável seja capaz.No entanto, isso não tem nada a ver com o esforço necessário para escrever um programa para a máquina, o tempo que pode levar para a máquina executar o cálculo ou quaisquer habilidades que a máquina possa possuir que não esteja relacionada à computação.

Embora as máquinas realmente-completas de Turing sejam muito provavelmente impossíveis, pois exigem armazenamento ilimitado, a integridade de Turing é frequentemente atribuída frouxamente a máquinas físicas ou linguagens de programação que seriam universais se tivessem armazenamento ilimitado.Todos os computadores modernos são completos nesse sentido.

Não sei como você pode ser mais não técnico do que isso, exceto dizendo "turing complete significa 'capaz de responder a problemas computáveis com tempo e espaço suficientes'".

Definição Informal

Uma linguagem Turing completa é aquela que pode realizar qualquer cálculo.O Tese de Church-Turing afirma que qualquer cálculo executável pode ser feito por uma máquina de Turing.A Máquina de Turing é uma máquina com memória de acesso aleatório infinita e um 'programa' finito que determina quando deve ler, escrever e mover-se através dessa memória, quando deve terminar com um determinado resultado e o que deve fazer a seguir.A entrada para uma máquina de Turing é colocada em sua memória antes de ser iniciada.

Coisas que podem tornar uma linguagem NÃO Turing completa

Uma máquina de Turing pode tomar decisões com base no que vê na memória - A 'linguagem' que só suporta +, -, *, e / em números inteiros não é Turing completo porque não pode fazer uma escolha com base em sua entrada, mas uma máquina de Turing pode.

Uma máquina de Turing pode funcionar para sempre - Se pegássemos Java, Javascript ou Python e removêssemos a capacidade de fazer qualquer tipo de loop, GOTO ou chamada de função, não seria Turing completo porque não pode realizar um cálculo arbitrário que nunca termina. Coq é um provador de teoremas que não pode expressar programas que não terminam, portanto não é Turing completo.

Uma máquina de Turing pode usar memória infinita - Uma linguagem que fosse exatamente como Java, mas terminaria quando usasse mais de 4 Gigabytes de memória, não seria Turing completa, porque uma máquina de Turing pode usar memória infinita.É por isso que não podemos realmente construir uma máquina de Turing, mas Java ainda é uma linguagem Turing completa porque o Java linguagem não tem nenhuma restrição que o impeça de usar memória infinita.Esta é uma das razões pelas quais as expressões regulares não são Turing completas.

Uma máquina de Turing possui memória de acesso aleatório - Uma linguagem que só permite trabalhar com memória através push e pop operações para uma pilha não seriam Turing completas.Se eu tiver uma 'linguagem' que leia uma string uma vez e só pode usar a memória empurrando e retirando de uma pilha, ele pode me dizer se cada ( na string tem seu próprio ) mais tarde empurrando quando vê ( e estalando quando vê ).No entanto, não pode me dizer se cada ( tem o seu próprio ) mais tarde e todo [ tem o seu próprio ] mais tarde (observe que ([)] atende a esses critérios, mas ([]] não).Uma máquina de Turing pode usar sua memória de acesso aleatório para rastrear ()'areia []está separadamente, mas esta linguagem com apenas uma pilha não pode.

Uma máquina de Turing pode simular qualquer outra máquina de Turing - Uma máquina de Turing, quando recebe um 'programa' apropriado, pode pegar o 'programa' de outra máquina de Turing e simulá-lo com entrada arbitrária.Se você tivesse uma linguagem proibida de implementar um interpretador Python, não seria Turing completo.

Exemplos de linguagens completas de Turing

Se a sua linguagem tiver memória de acesso aleatório infinita, execução condicional e alguma forma de execução repetida, provavelmente é Turing completa.Existem sistemas mais exóticos que ainda podem alcançar tudo o que uma máquina de Turing pode, o que os torna Turing completos também:

Cálculo lambda não digitado
O jogo da vida de Conway
Modelos C++
Prólogo

Fundamentalmente, a completude de Turing é um requisito conciso, recursão ilimitada.

Nem mesmo limitado pela memória.

Eu pensei nisso de forma independente, mas aqui está alguma discussão da afirmação. Minha definição de LSP fornece mais contexto.

As outras respostas aqui não definem diretamente a essência fundamental da completude de Turing.

Turing Complete significa que é pelo menos tão poderoso quanto um Máquina de Turing.Isso significa que qualquer coisa que possa ser computada por uma Máquina de Turing pode ser computada por um sistema Turing Complete.

Ninguém ainda encontrou um sistema mais poderoso que uma Máquina de Turing.Então, por enquanto, dizer que um sistema é Turing Complete é o mesmo que dizer que o sistema é tão poderoso quanto qualquer sistema de computação conhecido (veja Tese de Church-Turing).

Em termos mais simples, um sistema Turing completo pode resolver qualquer problema computacional possível.

Um dos principais requisitos é que o tamanho do scratchpad seja ilimitado e que seja possível retroceder para acessar gravações anteriores no scratchpad.

Assim, na prática, nenhum sistema é Turing-completo.

Em vez disso, alguns sistemas se aproximam da completude de Turing modelando memória ilimitada e executando qualquer cálculo possível que caiba na memória do sistema.

Acho que a importância do conceito "Turing Complete" está na capacidade de identificar uma máquina de computação (não necessariamente um "computador" mecânico/elétrico) que pode ter seus processos desconstruídos em instruções "simples", compostas de instruções cada vez mais simples. instruções, que uma máquina Universal poderia interpretar e então executar.

Eu recomendo fortemente The Annotated Turing

@Mark, acho que o que você está explicando é uma mistura entre a descrição da Máquina de Turing Universal e do Turing Completo.

Algo que é Turing Complete, no sentido prático, seria uma máquina/processo/computação capaz de ser escrita e representada como um programa, para ser executada por uma Máquina Universal (um computador desktop).Embora não leve em consideração o tempo ou o armazenamento, conforme mencionado por outros.

O que eu entendo em palavras simples:

Turing completo: Uma linguagem/programa de programação que pode fazer cálculos é Turing completo.

Por exemplo :

Você pode adicionar dois números usando Just HTML.(Resposta é 'Não', você deve usar javascript para realizar a adição.), Portanto, HTML não é Turing Complete.
Linguagens como Java, C++, Python, Javascript, Solidity for Ethereum etc são Turing Complete porque você pode fazer cálculos como adicionar dois números usando essas linguagens.

Espero que isto ajude.

Como Waylon Flinn disse:

Turing Complete significa que é pelo menos tão poderoso quanto uma Máquina de Turing.

Acredito que isso esteja incorreto, um sistema é Turing completo se for exatamente tão poderoso quanto a Máquina de Turing, ou seja,todo cálculo feito pela máquina pode ser feito pelo sistema, mas também todo cálculo feito pelo sistema pode ser feito pela máquina de Turing.

Em termos práticos de linguagem familiares à maioria dos programadores, a maneira usual de detectar a completude de Turing é se a linguagem permite ou permite a simulação de instruções while ilimitadas aninhadas (em oposição ao estilo Pascal para instruções, com limites superiores fixos).

Um banco de dados relacional pode inserir latitudes e longitudes de lugares e estradas e calcular o caminho mais curto entre eles - não.Este é um problema que mostra que o SQL não é Turing completo.

Mas C++ pode fazer isso e resolver qualquer problema.Assim é.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow