O que torna uma linguagem completa de Turing?

79

Qual é o conjunto mínimo de recursos / estruturas de linguagem que o tornam completo em Turing?

Gato curioso
fonte
21
Não será melhor apenas pesquisar no google? en.wikipedia.org/wiki/Turing_completeness
aml90 29/01
2
Olá gato curioso, bem-vindo aos programadores! As chamadas para listas não estão no tópico aqui: removi essa parte da sua pergunta. Dito isto, essa busca é extremamente ampla: existe um problema específico em que você está trabalhando e que pensa na integridade de Turing?
3
@ amalantony: Assim como uma nota de rodapé .
Bobby
Para uma perspectiva da ciência da computação, veja aqui .
Raphael

Respostas:

73

Um tarpit de Turing é um tipo de linguagem de programação esotérica que se esforça para ser completa em Turing enquanto utiliza o mínimo de elementos possível. Brainfuck é talvez o tarpit mais conhecido, mas existem muitos.

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

  • OISC ( One Instruction Set Computer ) indica um tipo de computação imperativa que requer apenas uma instrução de um ou mais argumentos, geralmente "subtraia e ramifique se for menor ou igual a zero" ou "subtraia e pule se pedir emprestado". O x86 MMU implementa a instrução anterior e, portanto, é Turing-completo.

Em geral, para que uma linguagem imperativa seja completa em Turing, ela precisa:

  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 que uma linguagem funcional baseada no cálculo lambda seja TC, ela precisa:

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

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

É claro que existem outras maneiras de ver a computação, mas esses são modelos comuns para tarpits de Turing. Observe que computadores reais não são máquinas de Turing universais porque não possuem armazenamento ilimitado. A rigor, eles são "máquinas de armazenamento limitado". Se você continuasse adicionando memória a eles, eles abordariam assintoticamente as máquinas de Turing no poder. No entanto, mesmo 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, a E / S não é necessária para a integridade de Turing; O TC apenas afirma que um idioma pode calcular a função desejada, não que ele possa mostrar o resultado. Na prática, toda linguagem útil tem uma maneira de interagir com o mundo de alguma forma.

Jon Purdy
fonte
Para linguagens imperativas, variáveis ​​simples são suficientes? Fiquei com a impressão de que seria necessário algum tipo de coleção (por exemplo, matrizes ou listas vinculadas).
luiscubal
1
@luiscubal, você precisa 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 partes diferentes de dados. Pode-se argumentar que, com truques como o Fractran, você pode fazer isso mesmo em variáveis ​​simples ... mas não é exatamente isso que você está perguntando.
Não é necessário que o idioma deva suportar loops ENDLESS ?
sergiol 23/02
Re, "toda linguagem útil tem uma maneira de interagir com o mundo". Algol 60 não tinha nenhuma maneira definida de interagir com o mundo. Todas as suas E / S em um programa Algol 60 foram feitas chamando funções da biblioteca, e as funções da biblioteca podem ser completamente diferentes em diferentes implementações. Mas, por meio deste, me recuso a discutir se Algol 60 foi ou não "útil".
Solomon Slow
15

De um ponto de vista mais prático: se você pode traduzir todos os programas em um idioma completo de Turing para o seu idioma, então (tanto quanto eu sei), seu idioma deve estar completo de Turing. Portanto, se você quiser verificar se um idioma que você criou é completo em Turing, basta escrever um Brainf *** no compilador YourLanguage e provar / demonstrar que ele pode compilar todos os programas legais de BF.

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

Anton Golov
fonte
11
Sim, essa seria definitivamente a maneira mais prática de abordá-lo. </sarcasm>
Robert Harvey
13
@RobertHarvey tem razão, mas a ideia geral é bastante vital. O Brainfuck é comprovadamente completo e muito simples conforme as linguagens de programação. Para linguagens de programação não esotéricas, a implementação de um intérprete cerebral pode ser muito mais fácil e rápida do que fornecer uma prova rigorosa do nada (eu posso implementar o BF em algumas linhas do Python, mas não sei por onde começar com um prova de que o Python está completo); e dezenas de linguagens esotéricas inspiradas no cérebro são conhecidas por estarem completas porque é conhecido como elas são mapeadas para o cérebro.
7
@RobertHarvey: Por que não? Certamente alguém projetando sua própria linguagem seria capaz de escrever um compilador BF para ela (se fosse imperativo e encontrar outra linguagem adequada).
Anton Golov
5
@ delnan: Você terá que provar, no entanto, que seu intérprete de BF implementa corretamente a especificação de BF, IOW você terá que provar que seu intérprete de BF é, de fato, um intérprete de BF e não um intérprete para uma linguagem semelhante a BF que pode ou não estar completo em Turing.
Jörg W Mittag
2
@ DarekNędza, isso é apenas uma consequência natural de como Turing Completeness é definido; qualquer extensão de um idioma do Turing Complete ainda será o Turing Complete.
Anton Golov 9/10/2015
8

Um sistema só pode ser considerado como Turing completo se puder fazer qualquer coisa que uma máquina universal de Turing possa. Como se diz que a máquina universal de Turing é capaz de resolver qualquer função computável em um determinado período de tempo, os sistemas completos de Turing também podem, por extensão, fazê-lo.

Para verificar se algo está completo de Turing, 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 escrever "variáveis" (ou dados arbitrários) : Praticamente auto-explicativo.
  2. A capacidade de simular o movimento da cabeça de leitura / gravação : não basta apenas 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. Geralmente, isso pode ser simulado nas linguagens de programação com o uso de estruturas de dados da matriz (ou equivalente) ou, no caso de certas linguagens, como código de máquina, a capacidade de referenciar outras variáveis ​​através 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 uma variação das máquinas de estado finito frequentemente usadas no desenvolvimento da IA. Alan Turing disse que o objetivo dos estados é simular os "vários modos de solução de problemas" de uma pessoa.
  4. Um estado de "parada" : embora muitas vezes seja mencionado que um conjunto de regras deve ser capaz de se repetir para ser considerado como completo de Turing, esse não é realmente um bom critério, pois a definição formal do que é um algoritmo é sempre necessário. eventualmente concluir. Se eles não conseguem concluir de alguma forma, ou não é Turing completo ou o referido algoritmo não é uma função computável. Sistemas completos de Turing que tecnicamente não podem ser concluídos devido à maneira como eles funcionam (como consoles de jogos, por exemplo) contornam essa limitação ao serem capazes de "simular" um estado de parada de alguma maneira. Não deve ser confundido com o "problema da parada", uma função indecidível que prova isso '

Estes são os verdadeiros requisitos mínimos para que um sistema seja considerado completo como Turing. Nada mais nada menos. Se ele não pode simular nada disso de alguma forma, não é Turing completo. Os métodos propostos por outras pessoas são apenas meios para o fim, pois existem vários sistemas completos de Turing que não possuem esses recursos.

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

user3067516
fonte
4

Uma linguagem de programação está completa se você puder fazer qualquer cálculo com ela. Não há apenas um conjunto de recursos que faz com que um idioma fique completo, então as respostas dizendo que você precisa de loops ou que você precisa de variáveis ​​estão erradas, pois há idiomas que não têm mas estão completos.

Alan Turing criou a máquina de turing universal e, se você pode traduzir qualquer programa projetado para funcionar na máquina universal para rodar no seu idioma, também é Turing completo. Isso também funciona indiretamente, para que você possa dizer que o idioma X está completo, se todos os programas para o idioma completo Y puderem ser traduzidos para o X, pois todos os programas universais de máquinas de turismo podem ser traduzidos para um programa Y.

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

Geralmente, para provar a integridade do turing, eles fazem um intérprete para qualquer idioma comprovadamente completo, mas para que ele funcione, você precisa de meios de entrada e saída, duas coisas que realmente não são necessárias para que um idioma fique completo. É suficiente que seu programa possa alterar seu estado na inicialização e que você possa inspecionar a memória após a interrupção do programa.

Para criar uma linguagem bem-sucedida, é necessário mais do que completar a completude, e isso é verdade até mesmo para aumentar o tarpits. Eu não acho que BrainFuck teria sido popular sem ,e ..

Sylwester
fonte
2
"Uma linguagem de programação está completa se você puder fazer qualquer cálculo com ela." Essa é a tese de Church-Turing, não o que torna uma linguagem completa de Turing.
Rhymoid
@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 esteja igual?
194 Sylwester
1
Ainda estou procurando uma definição autorizada dos termos equivalente a Turing e completo em Turing (e poderoso em Turing). Eu já vi muitos casos, de pessoas em quadros de mensagens a pesquisadores em seus próprios jornais, que interpretam esses termos de maneira diferente.
Rhymoid
Enfim, interpreto 'Turing-complete' como sendo uma simulação equivalente a uma Universal Turing Machine (UTM; que, por sua vez, é capaz de simular qualquer máquina de Turing - daí 'universal'). No artigo de Turing de 1936, onde ele introduziu suas máquinas, ele definiu a noção de UTM e esboçou uma prova de que UTMs são simulações equivalentes ao cálculo lambda de Church. Ao fazer isso, ele provou que eles tinham o mesmo poder computacional. A tese de Church-Turing afirma, de maneira simples, que "esse é todo o poder computacional que você obterá".
Rhymoid
Possui duas definições formais para a página de abrangência de Turing da Wikipedia . Um requer E / S e o outro não. Aquele que não diz que uma máquina está completa se pode calcular todas as funções computáveis ​​em Turing. Isso faz com que o cálculo lambda volte a ser o turing completo, pois você pode facilmente criar um programa igual no cálculo lambda que calcula o mesmo que qualquer programa de máquina de turing.
Sylwester
4

Você não pode dizer se o loop será infinito ou parado.

-------------

Explicação: Dadas algumas entradas, é impossível dizer em todos os casos (usando outra máquina de Turing) se a coisa vai repetir-se infinitamente ou eventualmente parar, exceto executando-a (o que dá uma resposta se ela parar, mas não se loops!).

Isso significa que você precisa poder armazenar uma quantidade potencialmente ilimitada de dados de alguma forma - deve haver um equivalente à fita infinita, não importa quão complicada! (Caso contrário, há apenas um número finito de estados e você poderá 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.

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

Os sistemas completos de Turing podem emular qualquer outro sistema completo de Turing, portanto, se você pode criar um emulador para algum sistema completo de Turing bem conhecido em seu sistema, isso prova que seu sistema também está completo.

Por exemplo, suponha que você queira provar que Snakes & Ladders está completo em Turing, considerando um quadro com um padrão de grade repetidamente infinito (com uma versão diferente no lado superior e esquerdo). Sabendo que a máquina Minsky de 2 contadores está completa em Turing (que possui 2 contadores ilimitados e 1 estado de um número finito), você pode construir uma placa equivalente em que as posições X e Y na grade sejam o valor atual dos 2 contadores e o caminho atual é o estado atual. Bang! Você acabou de provar que Snakes & Ladders está completo em Turing.

Hubert Lamontagne
fonte
1
Eu não compro esse argumento. Só porque o problema de parada é indecidível para máquinas de Turing não implica diretamente que toda notação que permite especificar um programa para o qual o problema de parada é indecidível é Turing completo. Somente o inverso é obviamente verdadeiro: se a notação é Turing completa, é claro que é possível escrever programas para os quais o problema de parada é indecidível.
5gon12eder
É uma condição necessária. Se você pode decidir para cada programa se ele pára, o idioma não está completo.
gnasher729
4

Uma condição necessária é um loop com uma contagem de iteração máxima que não é determinada antes da iteração ou recursão em que a profundidade máxima de recursão não é determinada com antecedência. Como exemplo, para ... nos ... loops, pois você os encontra em muitos idiomas mais novos, não é suficiente para tornar o 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 e a profundidade de recursão máximas devem ser calculadas com antecedência.

Por exemplo, a função Ackermann não pode ser calculada em um idioma sem esses recursos. Por outro lado, muitos softwares altamente complexos e úteis podem ser gravados sem a necessidade desses recursos.

Por outro lado, com todas as contagens de iterações e todas as profundidades de recursão calculadas adiante, não só pode ser decidido se um programa será interrompido ou não, mas também será interrompido.

gnasher729
fonte
-1

Eu sei que essa não é a resposta formalmente correta, mas depois que você tirar o 'mínimo' de 'Turing-complete' e colocar 'prático' de volta onde ele pertence, você verá os recursos mais importantes que distinguem uma linguagem de programação de uma linguagem de marcação são

  • variáveis
  • condicionais (se / então ...)
  • loopage (loop / break, enquanto ...)

próximo vem

  • funções anônimas e nomeadas

Para testar essas afirmações, comece com uma linguagem de marcação, por exemplo, 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 acabaria como algo parecido <repeat n='4'>...</repeat>). fazer qualquer uma dessas opções tornará o HTML + significativamente (?) mais poderoso que o HTML comum, mas ainda assim seria mais uma marcação do que uma linguagem de programação; com cada novo recurso, você o torna menos uma linguagem declarativa e mais imperativa.

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 largura dos fundamentos teóricos da integralidade de Turing. toda a essência da culinária e da programação é fazer as coisas, na ordem certa, repetindo até ficar pronta, como sua mãe fez. isso resume tudo para mim.

então, novamente, eu nunca terminei meu CS.

fluxo
fonte
2
Se você não tiver certeza, pesquise primeiro. o fractran está completo , assim como o brainf * ck . Observe também que o html 5 + CSS 3 é Turing completo porque pode implementar a regra 110 .
1
sim, sim, eu sei. mas todos os exemplos dados são mais ou menos esotéricos (embora talvez interessantes ou surpreendentes), minha resposta foi pragmática e, provavelmente, nem um pouco mínima. Eu acho importante salientar isso - esta página foi a número 1 ao pesquisar a integridade de Turing no google, as respostas aqui são de pouca utilidade para, digamos, um n00bie que queira saber o que distingue HTML de PHP ou Python. Quero dizer, brainf ck não é chamado brainf ck sem motivo.
flow