O que faz uma linguagem Turing-completa?

Um Turing tarpit é um tipo de linguagem de programação esotérica que se esforça para ser Turing-completa, usando apenas alguns elementos como possível. Brainfuck é talvez o mais conhecido tarpit, mas existem muitos.

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

• OISC ( Um conjunto de instruções de computador ) indica 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" inverter subtrair e pular se pedir emprestado " " O x86 MMU implementa a instrução anterior e é, portanto, Turing-completo.

Em geral, para que uma linguagem imperativa seja Turing-complete, 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 uma linguagem funcional baseada em lambda-cálculo ser TC, é necessário:

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

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

Existem, é claro, outras maneiras de olhar para a computação, mas esses são modelos comuns para os tarts de Turing. Observe que os computadores reais não são máquinas de Turing universais porque não têm armazenamento ilimitado. Estritamente falando, eles são “máquinas de armazenamento limitadas”. Se você continuasse adicionando memória a eles, eles assintoticamente aproximariam as máquinas de Turing do poder. No entanto, até máquinas de armazenamento limitadas e máquinas de estados finitas são úteis para computação; eles simplesmente não são universais .

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

De um ponto de vista mais prático: se você puder traduzir todos os programas em um idioma Turing-completo para o seu idioma, então (até onde eu sei), seu idioma deve ser Turing-complete. Portanto, se você quiser verificar se um idioma que você projetou é Turing-completo, você poderia 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 o YourLanguage, você escreve um compilador (em qualquer idioma) que possa compilar qualquer programa do BF para o YourLanguage (mantendo a mesma semântica, é claro).

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

Para verificar se algo está Turing completo, veja se você pode implementar uma máquina de Turing dentro dele. 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-explicativas.
2. A capacidade de simular a movimentação da cabeça de leitura / gravação : não é suficiente 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. Isso 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 referenciar outras variáveis através do uso de "ponteiros" (ou equivalente).
3. A capacidade de simular uma máquina de estados finita : Embora não seja mencionada com frequência, as máquinas de Turing são na verdade uma variação das máquinas de estados finitas frequentemente usadas no desenvolvimento da IA. Alan Turing disse que o objetivo dos estados é simular os "vários modos de resolução de problemas" de uma pessoa.
4. Um estado "halt" : Embora seja frequentemente mencionado, um conjunto de regras deve ser capaz de se repetir para ser considerado Turing completo, o que não é um bom critério desde a definição formal do que um algoritmo é um algoritmo de estado que deve sempre terminar. Se eles não podem concluir de alguma forma, ou não é Turing completo, ou dito algoritmo não é uma função computável. Turing sistemas completos que tecnicamente não podem concluir devido à maneira como eles funcionam (como consoles de jogos, por exemplo) contornar essa limitação, sendo capaz 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 os requisitos mínimos verdadeiros para um sistema ser considerado Turing completo. Nada mais nada menos. Se não puder simular nada disso de alguma forma, não é Turing completo. Os métodos que outras pessoas propuseram são apenas meios para o fim, pois há vários sistemas completos de Turing que não possuem esses recursos.

Note que não existe uma maneira conhecida de realmente construir um verdadeiro sistema completo de Turing. Isto é porque não há maneira conhecida de simular genuinamente a infinidade da fita da máquina de Turing no espaço físico.

Uma linguagem de programação é completa se você puder fazer qualquer cálculo com ela. Não há apenas um conjunto de recursos que torna um aprendizado de idioma completo, de modo que as respostas dizendo que você precisa de loops ou que você precisa de variáveis estão erradas, pois existem idiomas que não tem , mas estão completos.

Alan Turing fez a máquina universal e se você pode traduzir qualquer programa projetado para trabalhar na máquina universal para rodar em sua linguagem, também é Turing completo. Isso também funciona indiretamente, então você pode dizer que a linguagem X está completa se todos os programas para turing a linguagem completa Y podem ser traduzidos para X, já que todos os programas da máquina universal podem ser traduzidos para um programa em Y.

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

Normalmente, para comprovar a inteireza, eles fazem um intérprete para qualquer linguagem comprovada, mas para que isso funcione, você precisa de meios de entrada e saída, duas coisas que não são realmente necessárias para que uma linguagem seja 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 criar uma linguagem bem-sucedida, ela precisa de mais do que inteireza e, no entanto, isso vale também para os tarpits. Eu não acho que o BrainFuck teria sido popular sem , e . .

Você não pode dizer se vai repetir infinitamente ou 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 infinitamente ou eventualmente parar, exceto ao executá-lo (o que lhe dá uma resposta se ele parar , mas não se for loops!).

Isto significa que você tem que ser capaz de armazenar uma quantidade potencialmente ilimitada de dados de alguma forma - tem que haver um equivalente à fita infinita, não importa quão complicado seja! (Caso contrário, há apenas um número finito de estados e, em seguida, 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.

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

Sistemas completos de Turing podem emular qualquer outro sistema completo de Turing, então se você pode construir um emulador para algum sistema Turing completo 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 infinitamente repetido (com uma versão diferente no lado superior e no lado esquerdo). Sabendo que a máquina Minsky de 2 contadores é Turing completa (que tem 2 contadores ilimitados e 1 estado fora de um número finito), você pode construir uma placa 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 & As escadas são Turing completas.

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 à frente. Por exemplo, para ... in ... loops como você os encontra em muitas linguagens mais recentes, não são suficientes para completar o idioma (mas eles terão outros meios). Observe que isso não significa um 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 Ackermann não pode ser computada em um idioma sem esses recursos. Por outro lado, muitos softwares altamente complexos e altamente úteis podem ser gravados sem a necessidade desses recursos.

Por outro lado, a cada contagem de iteração e a cada profundidade de recursão calculada adiante, não só pode ser decidido se um programa será interrompido ou não, mas será interrompido .

Eu sei que esta não é a resposta formalmente correta, mas uma vez que você tire o 'mínimo' de 'Turing-complete' e coloque 'prático' de volta onde ele pertence, você verá as características mais importantes que distinguem uma programação. idioma de uma linguagem de marcação são

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

em seguida

• 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 somente condicionais (MS fez isso com comentários condicionais), ou algum tipo de construção de loop (que na ausência de condicionais provavelmente acabaria sendo algo como <repeat n='4'>...</repeat> ). fazer qualquer um deles tornará o HTML + significativamente (?) mais poderoso que o HTML simples, mas ainda seria mais uma marcação do que uma linguagem de programação; Com cada novo recurso, você torna menos uma linguagem declarativa e mais imperativa.

a busca da minimalidade na lógica e na programação certamente é importante e interessante, mas se eu tivesse que ensinar aos jovens jovens ou velhos 'o que é programação' e 'como aprender a programar', eu dificilmente começaria com a total amplitude e largura dos fundamentos teóricos da completude 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.