O que é o Turing Complete?

487

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

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

dlinsin
fonte
2
Alguns links muito legais para esta pergunta SO .
Lazer 27/05

Respostas:

325

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.

Mark Harrison
fonte
18
Para uma leitura mais detalhada, consulte The Annotated Turing. Muito acessível. amazon.com/Annotated-Turing-Through-Historic-Computability/dp/…
i_am_jorf
43
"muitas vezes não na prática" está incorreto. Nenhum sistema está completo em Turing na prática, porque nenhum sistema realizável possui uma fita infinita. O que realmente queremos dizer é que alguns sistemas têm a capacidade de aproximar a perfeição de Turing até os limites de sua memória disponível.
Shelby Moore III
22
Mas Vi é o motor só computacional sempre necessário no mundo ... ;-)
Joe Edgar
4
O Emacs também é uma máquina de tornear? XD
alem0lars
6
Alguém recentemente mostrou que o PowerPoint também é Turing Complete.
TAGC
193

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

Raja Rao
fonte
5
A ideia de que haveria um termo para esse tipo de máquina faz muito mais sentido quando me lembro de Turing e outros cientistas da computação construíram uma máquina específica cada vez que queriam resolver um problema específico. Estamos acostumados a uma máquina que pode ser reprogramada para sempre. Obrigado pelo contexto, Raja.
Jacob Ford
Como o JavaScript pode ser Turing Complete? Não possui sistema de arquivos, API multithreading adequada. Possui inúmeras limitações, principalmente devido à natureza da caixa de proteção de segurança do navegador. Dificilmente pode ser chamado de 'uma linguagem de programação'. Veja quantas variantes de abstração de script existem (reaja, datilografada ... o nome dela), tudo isso para compensar o que o JS não possui. (asm.js deve ser mencionado aqui). Java, Python ou C ++ são verdadeiros exemplos de 'Turing Complete'. Mas js? Acho que não.
Michael IV
2
@MichaelIV A máquina de turismo também não tinha um sistema de arquivos / threads. JS está absolutamente em turnê completa.
Bax
@MichaelIV Para adicionar à resposta de Bax, pode-se considerar que um computador moderno consiste em várias máquinas de Turing que trabalham juntas para permitir todas essas coisas legais que você menciona. Por exemplo, a CPU produz "fita" para a GPU ler, para que possa gravar "fita" para o monitor, para que o monitor possa gravar "fita" para o usuário. Da mesma forma, a CPU poderia produzir "fita" para os discos rígidos, placas de rede, placas de som, etc.
86

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'".

Ran Biron
fonte
4
Nesse contexto, o que é um "dispositivo de computação"?
22414 dopatraman
30
Como na maioria dos artigos da Wikipedia, embora essa citação seja tecnicamente correta, ela não fornece valor a uma pessoa que não tem conhecimento sobre o assunto e está tentando entendê-lo. Ser capaz de explicar as coisas corretamente é uma ciência de seu próprio :)
Lacho Tomov
76

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
Gordon Gustafson
fonte
11
Definitivamente, o SQL está completo. Possui recursos de script que permitem qualquer cálculo.
Nzifnab
53
Não, você está confundindo SQL com extensões como T-SQL / PL-SQL. O ANSI SQL não está completo. Mas TSQL / PLSQL - é.
Agnius Vasiliauskas
15
Aparentemente, o SQL está completo: stackoverflow.com/questions/900055/…
Newtang
2
De acordo com a integridade do turing - o sistema é Turing completo se puder ser usado para simular qualquer máquina de Turing com uma única fita. Mas no exemplo acima, como eu entendi, os desenvolvedores construíram particular cyclic tag systeme não universal cyclic tag system. Portanto, o artigo não comprova a integridade dos dados SQL. (Ou eu mal entendido alguma coisa)
Agnius Vasiliauskas
2
Não há implementação realizável de uma linguagem completa de Turing, porque não há fitas infinitas. O que realmente queremos dizer é que alguns idiomas têm a capacidade de aproximar a perfeição de Turing até os limites da memória disponível da máquina host.
Shelby Moore III
17

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.

Shelby Moore III
fonte
Autômatos de estados finitos podem ter recursão ilimitada. Caso em questão: a*.
3
Os FSMs Rhymoid têm memória limitada - o número finito de estados) -, mas a recursão ilimitada sem otimização de cauda deve ter memória ilimitada. Não restringi minha definição ao subconjunto de recursão ilimitada apenas com otimização de cauda. Por favor, remova o seu voto negativo.
Shelby Moore III
você manteve a definição de recursão ilimitada nebulosa. Você quer dizer 'recursão' no sentido de 'recursão primitiva' e 'ilimitado', tornando-o 'parcial' (ou 'geral' ou 'mu-')? Então você pode estar certo. Mas sua formulação atual está muito próxima das afirmações criticadas nos "On Folk Theorems" de David Harel. É importante ser rigoroso em matemática e, deixando de fora definições precisas, você está ignorando isso. A propósito: os FSMs podem ser generalizados para modelar a interação; o que os diferencia das TMs é que o ambiente deste último também é modelado (como a fita).
A enumeração Rhymoid é a antítese da precisão, por exemplo, enumere a precisão máxima das frações de uma polegada. Recursão ilimitada significa todas as formas possíveis de recursão, que são impossíveis sem uma fita infinita. A recursão totalmente generalizada (não apenas geral dentro do modelo) é sempre completa em Turing. Estou afirmando equivalência entre recursão generalizada e a capacidade de executar qualquer cálculo possível. Essa é uma equivalência importante a ser observada.
Shelby Moore III
"Recursão ilimitada significa todas as formas possíveis de recursão" Essa é a sua leitura. Para a maioria dos usuários de SO, 'recursão ilimitada' significa while (p) { /* ... */ }. "Estou afirmando equivalência entre recursão generalizada e a capacidade de executar qualquer cálculo possível." A tese da Igreja é uma questão muito diferente e deve realmente ser discutida separadamente.
13

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 ).

Waylon Flinn
fonte
3
Observe que tudo isso desconsidera o tempo da parede. Apenas diz "isso pode ser feito".
Thorbjørn Ravn Andersen
@ ThorbjørnRavnAndersen, na verdade, desconsidera completamente a computação física. Não apenas pode demorar mais que a idade do universo, mas também pode usar mais memória do que pode ser construída com todos os férmions e bósons do universo.
Waylon Flinn
Não há, quitte possivelmente, nenhum limite para a quantidade de bósons e férmions no universo. Não sabemos e provavelmente nunca saberemos, é o tamanho. Toda vez que você lê sobre o número de X no 'universo', as pessoas estão realmente falando sobre o universo observável . Embora interessante, não é um limite físico real.
Stijn de Witt
9

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.

Shelby Moore III
fonte
2

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.

Brian Leahy
fonte
2

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.

Shirish Singh
fonte
0

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

Allan Wrobel
fonte
1
Para uma pergunta tão antiga, seria interessante verificar se outras pessoas já fizeram contribuições semelhantes ou mais substanciais
alan ocallaghan 15/01
Não tenho certeza sobre a exatidão da resposta. Mas esta é realmente uma explicação simples que eu nunca vi antes. Engraçado: há muito tempo (depois que escrevi meu primeiro pedaço de código), também usei a mesma explicação para definir o processador mais simples possível.
Victor Yarema 15/01
É uma excelente primeira tentativa de uma definição operacional incisiva, concisa e precisa. No entanto, a ramificação deve permitir loop e não é o caso de a máquina também permitir chamadas de sub-rotina (ou seja: recursão)? Existe um programa achatado de loops aninhados para cada programa com recursão?
user3673 29/02
0

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".

Richard Riehle
fonte
-1

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 .

ChrisC
fonte
1
Acho que você está assumindo que a tese de Church-Turing é verdadeira para chegar a essa conclusão. Ainda não foi comprovado. A propriedade que você está descrevendo é chamada 'Turing Equivalent'.
Waylon Flinn
1
@WaylonFlinn Não, ele está certo. "Completude" significa tanto que é pelo menos tão forte quanto uma coisa, mas também não é mais forte. Compare com "NP-Complete".
Devin Jeanpierre
3
@DevinJeanpierre Eu não quero começar uma guerra de chamas aqui, mas estou quase certo de que a classe computacional que você está descrevendo é chamada "Turing Equivalent". O Turing Complete possui uma relação semelhante ao NP-Complete. NP-Complete é igual a NP se e somente se P = NP. Do mesmo modo, Turing Complete é igual a Turing Equivalente se e somente se a tese de Church-Turing estiver correta.
Waylon Flinn
@Waylon Source? Nada eu li concorda com isso (por exemplo en.wikipedia.org/wiki/Turing_completeness )
Devin Jeanpierre
4
@DevinJeanpierre Está escrito ali no artigo da wikipedia ao qual você está vinculado. Citando a seção Definições formais: "Um sistema computacional que pode calcular todas as funções computáveis ​​de Turing é chamado Turing complete", "Um sistema completo de Turing é chamado equivalente de Turing se todas as funções que ele pode calcular também são Turing computáveis"
Waylon Flinn
-2

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).

Keith Douglas
fonte
1
Um único loop while sem limites é suficiente para simular uma máquina de Turing.
Masterdilo # 17/17
-8

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

Akshay Jain
fonte
10
Ser capaz de calcular o caminho mais curto entre os pontos não é a definição de Turing completa. Há muito mais do que apenas um exemplo.
Eva
1
Vou colocar isso aqui ... hansolav.net/blog/ImplementingDijkstrasAlgorithmUsingTSQL.aspx
Matthew Whited