O que torna uma linguagem Turing completa?

A Turing tarpit é um tipo de linguagem de programação esotérica que se esforça para ser Turing-completa enquanto usa o mínimo de elementos possível. Brainfuck é talvez o tarpit mais conhecido, mas há muitos.

• Iota e Jot são linguagens funcionais com dois e três símbolos, respectivamente, com base no SK (I) cálculo combinatório .

• OISC ( Um computador de conjunto de instruções ) denota um tipo de cálculo imperativo que requer apenas uma instrução de um ou mais argumentos, geralmente “subtrair e ramificar se menor ou igual a zero”, ou “Reverter subtrair e pular se emprestar” O x86 MMU implementa a instrução anterior e é, portanto, Turing-completo.

Em geral, para um linguagem imperativa para ser Turing-completa, ela precisa de:

1. Uma forma de repetição condicional ou salto condicional (por exemplo, while, if + goto)

2. Uma maneira de ler e escrever alguma forma de armazenamento (por exemplo , variáveis, fita)

Para uma linguagem funcional baseada em lambda-cálculo para ser TC, isso necessidades:

1. A capacidade de abstrair funções sobre argumentos (por exemplo, abstração lambda, citação)

2. A capacidade de aplicar funções a argumentos (por exemplo, redução)

Existem, é claro, outras maneiras de ver a computação, mas esses são modelos comuns para tarpits de Turing. Observe que os computadores reais não máquinas de Turing universais porque não têm armazenamento ilimitado. A rigor, são “máquinas de armazenamento limitado”. Se você continuasse a adicionar memória a eles, eles se aproximariam assintoticamente das máquinas de Turing no poder. No entanto, mesmo as máquinas de armazenamento limitado e máquinas de estado finito são úteis para computação; eles simplesmente não são universais .

Estritamente falando, E / S não é necessária para completude de Turing; TC apenas afirma que uma linguagem pode computar a função que você deseja, não que pode mostrar o resultado. Na prática, toda linguagem útil tem uma maneira de interagir com o mundo de alguma forma.

Comentários

• Para linguagens imperativas, variáveis simples são suficientes? Tive a impressão de que algum tipo de coleção (por exemplo, matrizes ou listas vinculadas) seria necessário.
• @luiscubal você precisa ser capaz de especificar uma quantidade arbitrária de dados. Com variáveis simples, você pode representar a quantidade de dados que as próprias variáveis possuem. E se você precisar representar N + 1 dados diferentes. Alguém poderia argumentar que, com truques como o Fractran, você poderia fazer isso até mesmo em variáveis simples … mas que ‘ não é bem o que você ‘ está perguntando.
• Não ‘ t requer que o idioma suporte ENDLESS loops?
• Re, ” toda linguagem útil tem uma maneira de interagir com o mundo. ” Algol 60 não tinha nenhuma forma definida de interagir com o mundo. Toda a sua E / S em um programa Algol 60 foi feita chamando funções de biblioteca, e as funções de biblioteca podem ser completamente diferentes em diferentes implementações. Mas, por meio deste, recuso-me a qualquer discussão sobre se Algol 60 foi ou não ” útil. ”

De um ponto de vista mais prático: se você pode traduzir todos os programas em um idioma Turing-completo para o seu idioma, então (na medida em que Eu sei), sua linguagem deve ser completa de Turing.Portanto, se você quiser verificar se uma linguagem que você projetou é Turing-completa, você pode simplesmente escrever um Brainf *** para o compilador YourLanguage e provar / demonstrar que ele pode compilar todos os programas BF legais.

Para esclarecer, quero dizer que além de um interpretador para YourLanguage, você escreve um compilador (em qualquer idioma) que pode compilar qualquer programa BF para YourLanguage (mantendo a mesma semântica, é claro).

Comentários

• Sim, essa seria definitivamente a maneira mais prática de abordar isso. </sarcasm>
• @RobertHarvey tem razão, mas a ideia geral é vital. O Brainfuck é comprovadamente completo e muito simples no que diz respeito às linguagens de programação. Para linguagens de programação não esotéricas, implementar um intérprete brainfuck pode ser muito mais fácil e rápido do que fornecer uma prova rigorosa do nada (posso implementar BF em algumas linhas de Python, mas ‘ m não tenho certeza por onde começar com uma prova formal de que o Python está se tornando completo); e dezenas de linguagens esotéricas inspiradas na foda cerebral são conhecidas por serem completas porque ‘ sabe como elas mapeiam para a foda cerebral.
• @RobertHarvey: Por que não? Certamente alguém projetando sua própria linguagem seria capaz de escrever um compilador BF para ela (se for necessário, e encontrar uma outra linguagem adequada de outra forma).
• @delnan: Você irá tem que provar, no entanto, que seu interpretador BF implementa corretamente a especificação BF, IOW você terá que provar que seu interpretador BF é, de fato, um interpretador BF e não um intérprete para uma linguagem semelhante a BF que pode ou não ser Turing-complete.
• @ DarekNędza, que ‘ é apenas uma consequência natural de como a integridade de Turing é definida; qualquer extensão de uma linguagem Turing Complete ainda será Turing Complete.

Um sistema só pode ser considerado para ser Turing completo se puder fazer qualquer coisa que uma máquina de Turing universal pode. Visto que se diz que a máquina de Turing universal é capaz de resolver qualquer função computável com o tempo, os sistemas completos de Turing também podem, por extensão, fazê-lo.

Para verificar se algo está Turing completo, veja se você pode implementar uma máquina de Turing dentro dela. Em outras palavras, verifique se ele pode simular o seguinte:

1. A capacidade de ler e gravar “variáveis” (ou dados arbitrários) : Bastante autoexplicativo.
2. A capacidade de simular o movimento do cabeçote de leitura / gravação : Não é suficiente apenas ser capaz de recuperar e armazenar variáveis. Também deve ser possível simular a capacidade de mover a cabeça da fita para fazer referência a outras variáveis. Isso muitas vezes pode ser simulado em linguagens de programação com o uso de estruturas de dados de array (ou equivalente) ou, no caso de certas linguagens, como código de máquina, a capacidade de fazer referência a outras variáveis por meio do uso de “ponteiros” (ou equivalente).
3. A capacidade de simular uma máquina de estado finito : Embora não seja mencionado com frequência, as máquinas de Turing são na verdade um variação das máquinas de estado finito frequentemente usadas no desenvolvimento de IA. Alan Turing disse que o propósito dos estados é simular os vários modos de resolução de problemas de uma pessoa.
4. Um estado de “parada” : Embora seja frequentemente mencionado que um conjunto de regras deve ser capaz de se repetir a fim de ser considerado como sendo Turing completo, esse não é realmente um bom critério, visto que a definição formal do que algoritmo é estado algoritmos devem sempre eventualmente concluir. Se eles não podem concluir de alguma forma, ou não é Turing completo, ou dito algoritmo não é uma função computável. Sistemas completos de Turing que tecnicamente não podem “ser concluídos devido à maneira como funcionam (como consoles de jogos, por exemplo) contornam essa limitação sendo capazes de” simular “um estado de parada de alguma forma. Não deve ser confundido com o” problema da parada “, uma função indecidível que prova que é impossível construir um sistema que possa detectar com 100% de confiabilidade se uma determinada entrada fará com que outro sistema não seja concluído.

Estes são o mínimo verdadeiro requisitos para um sistema ser considerado Turing completo. Nada mais nada menos. Se não puder simular qualquer um desses de alguma forma, não é o Turing completo. Os métodos que outras pessoas propuseram são apenas meios para o fim, já que existem vários sistemas completos de Turing que não têm esses recursos.

Observe que não há maneira conhecida de realmente construir um sistema completo de Turing verdadeiro . Isso ocorre porque não há maneira conhecida de simular genuinamente a ilimitação da fita da máquina de Turing no espaço físico.

Uma linguagem de programação está se tornando completa se você puder fazer qualquer cálculo com ela.Não existe apenas um conjunto de recursos que torna uma linguagem completa, portanto, as respostas dizendo que você precisa de loops ou que você precisa de variáveis estão erradas, pois há linguagens que não tem mas estão completos.

Alan Turing fez a máquina universal de rotação e se você pode traduzir qualquer programa projetado para funcionar na máquina universal para rodar em sua linguagem, ele também é Turing completo. Isso também funciona indiretamente para que você possa dizer que a linguagem X está se tornando completa se todos os programas para a linguagem Y completa puderem ser traduzidos para X, uma vez que todos os programas de máquina de controle universal podem ser traduzidos para um programa Y.

A complexidade do tempo , complexidade de espaço, facilidade de formato de entrada / saída e fácil de escrever qualquer programa não está incluído na equação, então tal máquina pode teoricamente fazer todos os cálculos se os cálculos não forem interrompidos por perda de energia ou a Terra sendo engolida pelo sol.

Normalmente, para provar a integridade, eles fazem um intérprete para qualquer linguagem comprovadamente completa, mas para que funcione você precisa de meios de entrada e saída, duas coisas que realmente não são necessárias para uma linguagem ser completa. É suficiente que seu programa possa alterar seu estado na inicialização e que você possa inspecionar a memória depois que o programa for interrompido.

Para fazer uma linguagem bem-sucedida, ela precisa mais do que alterar a integridade e isso é verdade mesmo para tarpits turing. Não acho que BrainFuck teria sido popular sem , e ..

Comentários

• ” Uma linguagem de programação está se tornando completa se você puder fazer qualquer cálculo com ele. ” Isso ‘ é a tese de Church-Turing, não o que torna uma linguagem Turing completa.
• @Rhymoid Então você quer dizer que nada está completo a menos que você possa fazer um intérprete? Ou seja, o cálculo lambda não está completo mesmo que ‘ seja igual?
• Eu ‘ ainda estou procurando uma definição oficial dos termos Turing-equivalente e Turing-complete (e Turing-poderoso). I ‘ já vi muitos casos, de pessoas em painéis de mensagens a pesquisadores em seus próprios ‘ artigos, que interpretam esses termos de maneira diferente.
• De qualquer forma, Eu interpreto ‘ Turing-complete ‘ como sendo uma simulação equivalente a uma Máquina de Turing Universal (UTM; que, por sua vez, é capaz de simular qualquer máquina de Turing – portanto, ‘ universal ‘). No artigo de Turing ‘ de 1936, onde ele apresentou suas máquinas, ele definiu a noção de um UTM e deu um esboço de uma prova de que UTMs são simulações equivalentes a Church ‘ s cálculo lambda. Ao fazer isso, ele provou que eles tinham o mesmo poder computacional. A tese de Church-Turing afirma, de forma simples, que ” que ‘ é todo o poder computacional que você ‘ sempre obteremos “.
• Ele tem duas definições formais para Página de completude de Turing da Wikipedia . Um requer E / S e o outro não ‘ t. Aquele que não ‘ diz que uma máquina está se tornando completa se puder calcular todas as funções computáveis de Turing. Isso faz com que o cálculo lambda volte a ser completo, pois você pode facilmente fazer um programa igual em cálculo lambda que calcule o mesmo que qualquer programa de máquina de rotação.

Não é possível saber se ele fará um loop infinito ou se parará.

————-

Explicação: Dada alguma entrada, é impossível dizer em todos os casos (usando outra máquina de Turing) se a coisa vai fazer um loop infinito ou, eventualmente, vai parar, exceto por executá-la (o que lhe dá uma resposta se isso acontecer pare, mas não se ele fizer um loop!).

Isso significa que você deve ser capaz de armazenar uma quantidade de dados potencialmente ilimitada de alguma forma – deve haver um equivalente à fita infinita, não importa como complicado! (Caso contrário, há apenas um número finito de estados e então você pode verificar se já passou por esse estado anteriormente e, eventualmente, parar). Geralmente, as máquinas de Turing podem aumentar ou diminuir o tamanho de seu estado por alguns meios controláveis.

Visto que a máquina de Turing universal original de Turing tem um problema de parada insolúvel, sua própria máquina completa de Turing também deve ter uma parada insolúvel problema.

Os sistemas completos de Turing podem emular qualquer outro sistema completo de Turing, então se você puder construir um emulador para algum sistema completo de Turing bem conhecido em seu sistema, isso prova que seu sistema também é Turing completo.

Por exemplo, suponha que você queira provar que Snakes & Ladders é Turing completo, dado um tabuleiro com um padrão de grade repetido infinitamente (com uma versão diferente no topo e lado esquerdo). Sabendo que a máquina Minsky de 2 contadores é Turing completa (que tem 2 contadores ilimitados e 1 estado de um número finito), você pode construir um tabuleiro equivalente onde a posição X e Y na grade é o valor atual dos 2 contadores e o caminho atual é o estado atual. Bang! Você acabou de provar que Snakes & Escadas estão Turing completas.

Comentários

• Eu não ‘ para aceitar esse argumento. Só porque o problema da parada é indecidível para máquinas de Turing não implica diretamente que toda notação que permite a você especificar um programa para o qual o problema da parada é indecidível seja Turing completa. Apenas o inverso é obviamente verdadeiro: se a notação for Turing completa, então é claro que é possível escrever programas para os quais o problema da parada é indecidível.
• It ‘ uma condição necessária. Se você puder decidir para cada programa se ele deve parar, a linguagem não está ‘ t Turing completa.

Uma condição necessária é um loop com uma contagem máxima de iteração que não é determinada antes da iteração, ou recursão em que a profundidade máxima de recursão não é determinada antes. Como um exemplo, os loops for … in … como você os encontra em muitos idiomas mais novos não são suficientes para tornar o controle do idioma completo (mas eles terão outros meios). Observe que isso não significa número limitado de iterações ou profundidade de recursão limitada, mas que as iterações máximas e a profundidade de recursão devem ser calculadas com antecedência.

Por exemplo, a função de Ackermann não pode ser calculada em uma linguagem sem esses recursos. Por outro lado, muitos softwares altamente complexos e úteis podem ser escritos sem exigir esses recursos.

Por outro lado, com cada contagem de iteração e cada profundidade de recursão calculada antecipadamente, não apenas pode ser decidido se um programa será interrompido ou não, mas ele irá parar.

eu sei que esta não é a resposta formalmente correta, mas uma vez que você retire o “mínimo” de “Turing-complete” e coloque “prático” de volta ao seu devido lugar, você verá os recursos mais importantes que distinguem uma linguagem de programação de uma linguagem de marcação são

• variáveis
• condicionais (if / then …)
• loopage (loop / break, while …)

próximo com e

• funções anônimas e nomeadas

para testar essas asserções, comece com uma linguagem de marcação, digamos, HTML. poderíamos inventar um HTML + apenas com variáveis ou apenas condicionais (o MS fez isso com comentários condicionais) ou algum tipo de construção de loop (que, na ausência de condicionais, provavelmente terminaria em algo como <repeat n="4">...</repeat>). fazer qualquer um desses tornará o HTML + significativamente (?) mais poderoso do que o HTML simples, mas ainda seria mais uma marcação do que uma linguagem de programação; com cada novo recurso, você o torna menos declarativo e mais imperativo.

a busca pela minimalidade na lógica e na programação com certeza é importante e interessante, mas se eu tivesse que ensinar a n00bies, jovens ou velhos “o que é programação” e “como aprender a programar”, dificilmente começaria com toda a amplitude e amplitude dos fundamentos teóricos da completude de Turing. toda a essência de cozinhar e programar é fazer as coisas, na ordem certa, repetir até estar pronto, como sua mãe fez. Isso resume tudo para mim.

então, novamente, nunca terminei meu CS.

Comentários

• Se você não tem certeza, deve pesquisar primeiro. fractran está turing completo , assim como brainf * ck . Observe também que html 5 + CSS 3 é Turing completo porque pode implementar regra 110 .
• sim sim sim eu sei. mas todos os exemplos dados são mais ou menos esotéricos (embora talvez interessantes ou surpreendentes), m Minha resposta foi pragmática e, muito provavelmente, nem um pouco mínima. acho ‘ importante apontar isso — esta página foi a nº 1 ao pesquisar Turing-completude no google, as respostas aqui são IMHO de pouca utilidade para, digamos, um n00bie quem quer saber o que distingue HTML de PHP ou Python. quero dizer, brainf ck não é chamado brainf ck sem motivo.