O que é o Turing Complete?

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

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

Aqui está a explicação mais breve:

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

Portanto, se alguém disser "minha coisa nova é Turing Complete", isso significa que, em princípio (embora muitas vezes não seja na prática), 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 necessário no mundo.

Aqui está a explicação mais simples

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

As linguagens de programação são semelhantes àquelas máquinas (embora virtuais). Eles pegam programas e os executam. Agora, uma linguagem de programação é chamada "Turing complete", se for possível 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 adicione. A máquina de Turing pode executar facilmente este programa. Mas agora imagine que, por algum motivo, sua linguagem de programação não possa executar a mesma adição. Isso tornaria "Turing incompleto" (por assim dizer). Por outro lado, se ele pode executar qualquer programa que a máquina universal de Turing possa executar, então está completo.

A maioria das linguagens de programação modernas (por exemplo, Java, JavaScript, Perl, etc.) está completa no Turing porque cada uma implementa 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.

Atualização: Você pode aprender mais no meu blog: "JavaScript Is Turing Complete" - Explained

Da wikipedia :

A completude de Turing, nomeada em homenagem a Alan Turing, é significativa, pois todo projeto plausível para um dispositivo de computação até agora avançado pode ser imitado por uma máquina universal de Turing - uma observação que ficou conhecida como tese de Church-Turing. Assim, uma máquina que pode atuar como uma máquina universal de Turing pode, em princípio, executar qualquer cálculo 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 leva para a máquina executar o cálculo ou quaisquer habilidades que a máquina possua que não estejam relacionadas à computação.

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

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

Definição informal

Uma linguagem completa de Turing é aquela que pode executar qualquer cálculo. A tese de Church-Turing afirma que qualquer computação performable pode ser feita por uma máquina de Turing. Uma máquina de Turing é uma máquina com memória infinita de acesso aleatório e um 'programa' finito que determina quando deve ler, gravar e mover-se através dessa memória, quando deve terminar com um determinado resultado e o que deve fazer em seguida. A entrada para uma máquina de Turing é armazenada em sua memória antes de ser iniciada.

Coisas que podem tornar um idioma NÃO Turing completo

Uma máquina de Turing pode tomar decisões com base no que ele vê na memória - O 'linguagem' que só suporta +, -, *, e /em números inteiros não é Turing completa porque não pode fazer uma escolha com base na 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 executar qualquer tipo de loop, GOTO ou chamada de função, não seria Turing completo porque não pode executar um cálculo arbitrário que nunca termina. Coq é um provador de teoremas que não pode expressar programas que não terminam, por isso não é Turing completo.

Uma máquina de Turing pode usar memória infinita - Uma linguagem que era 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 o Java ainda é uma linguagem completa de Turing porque a linguagem Java não possui restrições que o impedem de usar memória infinita. Esse é um dos motivos pelos quais expressões regulares não são completas de Turing.

Uma máquina de Turing possui memória de acesso aleatório - Uma linguagem que apenas permite trabalhar com a memória pushe as popoperações em uma pilha não seria a conclusão de Turing. Se eu tiver um 'idioma' que lê uma string uma vez e só pode usar a memória pressionando e pulando de uma pilha, ele pode me dizer se cada uma delas (possui a sua )depois, pressionando quando vê (e pulando quando vê ). No entanto, ele não pode me dizer se todos (têm seus próprios )mais tarde e todos [têm seus próprios ]posteriormente (observe que ([)]atende a esse critério, mas ([]]não). Uma máquina de Turing pode usar sua memória de acesso aleatório para rastrear ()e[]separadamente, mas esse idioma 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 em entradas arbitrárias. Se você tivesse uma linguagem proibida de implementar um intérprete Python, não seria Turing completo.

Exemplos de idiomas completos de Turing

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

• Cálculo lambda não tipado
• Jogo da vida de Conway
• Modelos C ++
• Prolog

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

Nem mesmo limitado pela memória.

Pensei nisso de forma independente, mas aqui está uma discussão sobre a afirmação. Minha definição de LSP fornece mais contexto.

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

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

Ninguém ainda encontrou um sistema mais poderoso que uma máquina de Turing. Portanto, 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 (consulte a Tese de Church-Turing ).

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

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

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

Em vez disso, alguns sistemas aproximam a integridade de Turing modelando a memória ilimitada e realizando qualquer computação possível que possa caber na memória do sistema.

Eu 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 possa ter seus processos desconstruídos em instruções "simples", compostas de mais simples e mais simples instruções, que uma máquina Universal possa interpretar e depois executar.

Eu recomendo The Annotated Turing

@ Mark, eu acho que o que você está explicando é uma mistura entre a descrição da Universal Turing Machine e da Turing Complete.

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

O que eu entendo em palavras simples:

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

Por exemplo :

1. Você pode adicionar dois números usando apenas HTML . (Ans é ' Não ', você deve usar o javascript para executar a adição.) Portanto, o HTML não é o Turing Complete.

2. Idiomas como Java, C ++, Python, Javascript, Solidity para Ethereum etc. são Turing Complete porque você pode fazer cálculos como adicionar dois números usando essas linguagens.

Espero que isto ajude.

Está completo se puder testar e ramificar (possui um 'se')

Uma máquina de Turing exige que qualquer programa possa executar testes de condição. Isso é fundamental.

Considere um rolo de piano de jogador. O piano do tocador pode tocar uma peça de música altamente complicada, mas nunca há lógica condicional na música. É Turing completo.

A lógica condicional é o poder e o perigo de uma máquina que é Turing Complete.

O rolo de piano é garantido para parar o tempo todo. Não existe essa garantia para uma TM. Isso é chamado de "problema de parada".

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 para a maioria dos programadores, a maneira usual de detectar a integridade de Turing é se a linguagem permite ou permite a simulação de instruções while aninhadas e ilimitadas (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. Esse é um problema que mostra que o SQL não está completo de Turing.

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