Prova clara e completa de que um idioma é Turing Compete?

Vi sites que pretendem "provar" que o HTML5 + CSS é Turing Complete.

Eu já vi sites que pretendem "provar" que o SQL é Turing Complete.

Eu já vi vários sites que pretendem "explicar" o que significa ser Turing Complete.

O suficiente!

Onde posso encontrar um livro (escrito por um especialista em teoria da computabilidade) ou um artigo revisado por pares (em um periódico respeitável) que mostre uma prova de: "Essa linguagem XYZ é capaz de descrever uma máquina computacional com o mesmo poder computacional como uma máquina de Turing "?

computability turing-machines automata turing-completeness church-turing-thesis Roger Costello
fonte

Nenhum especialista escreverá esse artigo porque seria inútil.

Andrej Bauer

Mas existem papéis que fazem isso. Considere que os circuitos quase insensíveis ao atraso são completos em Turing, que têm uma prova de construção.

Dan D.

Vou comer meu chapéu se você puder encontrar um artigo revisado por pares que tenha uma prova detalhada de que HTML5 + CSS, SQL ou PHP são Turing completos.

Andrej Bauer

@andrej tente este. perto o suficiente? XSLT versão 2.0 é Turing-Complete: uma prova puramente baseada em transformação . talvez apenas coma seus vegetais: p

vzn

ver também o que faz uma linguagem Turing completa , programmers.se

vzn

Respostas:

Toda linguagem que pode implementar dois contadores (ou seja, dois registradores que podem armazenar dois inteiros arbitrariamente grandes) e um programa feito com uma sequência rotulada dessas duas instruções elementares é Turing completo: $C_1, C_2$

ADICIONAR para contrariar , GOTO instrução $1$ $C_i$ $I_j$
SUBTRATO do contador se e instrução GOTO ; caso contrário (se ) instrução GOTO $1$ $C_i$ $C_i > 0$ $I_j$ $C_i = 0$ $I_k$

O resultado é comprovado em:

Marvin L. Minsky, "Insolubilidade Recursiva do Problema de Tag de Post e outros Tópicos na Teoria das Máquinas de Turing" (1961)

Não se esqueça de que um modelo computacional (no seu caso, uma linguagem de programação + um dispositivo que executa programas escritos nessa linguagem ) pode ser considerado completo apenas se suportar o acesso a uma quantidade ilimitada de memória (ou seja, espaço) ou pode armazenar ( de alguma forma) números inteiros arbitrariamente grandes. Uma implementação de linguagem de programação em um computador real é equivalente a um autômato com limite linear .

Você também pode encontrar muitas referências nas páginas da Wikipedia sobre o modelo RAM e o modelo RASP .

Finalmente, um bom livro focado na equivalência de diferentes modelos de computação é:

"Modelos de computação: uma introdução à teoria da computabilidade", de Maribel Fernandez

Vor
fonte

"Não se esqueça que uma linguagem de programação pode ser considerada completa como Turing se suportar o acesso à memória infinita" Portanto, não pode existir uma implementação de uma linguagem completa de Turing? Esta é a sua conclusão? Ou você gostaria de dizer que todos (a maioria) dos idiomas que usamos são Turing Complete porque esse requisito é fácil de alcançar? Ambas as conclusões são válidas para a sua resposta, como está agora.

Bakuriu

bakuriu ver TM completa e computacional poder

vzn

@Bakuriu: na verdade, a frase é um pouco ambígua; Quero apenas dizer que um modelo computacional pode ser considerado completo como Turing se - de alguma forma - permitir o uso de um armazenamento ilimitado. A maioria das linguagens de programação é Turing completa porque em suas especificações (sintaxe) elas não têm limites para o tamanho de variáveis ou ponteiros, mas suas implementações são limitadas; veja, por exemplo, C's <limits.h>. Portanto, mesmo se você tiver um computador com memória ilimitada que execute uma implementação C, não poderá usar essa memória a menos que forneça um "mecanismo extra" que não faça parte do idioma.

Vor

{w . w ∣ w \in {0, 1}}

$\{w.w \mid w \in \{0, 1\}\}$

Os dois livros de texto mais usados sobre teoria da computabilidade e da complexidade são:

Michael Sipser: Introdução à Teoria da Computação , 2 / e, Cengage, 2005.

John E Hopcroft; Jeffrey D Ullman: Introdução à Teoria dos Autômatos, Idiomas e Computação , Addison-Wesley, 1979.

Há também uma bela monografia de filosofia para leigos que trabalha com os detalhes técnicos da teoria da computabilidade sem as provas formais.

Douglas Hoftstadter: Gödel, Escher, Bach , Basic Books, 1979.

Finalmente, a melhor introdução à computabilidade pode ser um livro de quebra-cabeças de um famoso lógico:

Raymond Smullyan: A Dama ou o Tigre e outros quebra-cabeças lógicos , Penguin, 1983. (Agora em uma edição barata de Dover, 2009.)

(Ele começa com um monte de quebra-cabeças baseados no paradoxo do mentiroso e, em seguida, trabalha na construção de uma declaração auto-referencial sob o disfarce de um quebra-cabeça ao estilo de Sherlock Holmes sobre uma misteriosa caixa trancada.)

Lógica Errante
fonte