Uma pequena linguagem C que as máquinas de turing podem simular

Estou procurando uma linguagem pequena que ajude a "convencer" os alunos de que máquinas de turing são um modelo de computação suficientemente geral. Ou seja, um idioma que se parece com os idiomas aos quais está acostumado, mas também é fácil de simular em uma máquina de turing.

Papadimitriou usa máquinas RAM para este trabalho, mas temo que comparar algo estranho (como uma máquina de tortura) com outra coisa estranha (basicamente, uma linguagem assembly) não seja convincente para muitos estudantes.

Todas as sugestões serão bem-vindas (especialmente se vierem com alguma literatura recomendada)

• $smn$$utm$

  Duvido que essa seja a abordagem mais simples possível, mas gosto de como ela se baseia em alguns dos teoremas mais fundamentais da computabilidade (que você pode querer abordar por outras razões).

  Parece que Andrej Bauer respondeu a uma pergunta semelhante no Mathoverflow alguns meses atrás.

• Se você estiver definido em uma linguagem C, seu caminho será muito mais difícil, pois eles têm uma semântica bastante complicada - você precisará

  1. Mostre que as máquinas de Turing podem simular uma pilha e uma pilha ao mesmo tempo, e
  2. Mostre como as variáveis ​​podem ser implementadas com uma pilha e
  3. Mostre que as chamadas de procedimento podem ser implementadas com uma pilha.

  Isso é muito do conteúdo de uma classe de compiladores, honestamente.

Meu professor de Teoria da Comp na graduação começou provando que uma máquina de Turing de fita única pode implementar uma máquina de Turing de fita múltipla. Ele lida com declaração de variável: se um programa possui seis declarações de variável, ele pode ser facilmente implementado em uma máquina Turing de sete fitas (uma fita para cada variável e uma fita "registradora" para ajudar a executar tarefas como aritmética e verificação de igualdade entre fitas). Ele então mostrou como implementar loops básicos FOR e WHILE, e nesse ponto tínhamos uma linguagem básica semelhante a C de Turing. Eu achei satisfatório, de qualquer maneira.

Estou pensando agora em como me convencer de que as máquinas de Turing são um modelo geral de computação. Concordo que o tratamento padrão da tese de Church-Turing em alguns livros-texto padrão, por exemplo, Sipser, não é muito completo. Aqui está um esboço de como eu poderia passar das máquinas de Turing para uma linguagem de programação mais reconhecível.

Considere uma linguagem de programação estruturada em bloco com ife whileinstruções, com sub-rotinas e funções definidas não recursivas , com variáveis ​​aleatórias booleanas nomeadas e expressões booleanas gerais e com uma única matriz booleana ilimitada tape[n]com um ponteiro de matriz inteira nque possa ser incrementado ou decrementado n++ou n--. O ponteiro né inicialmente zero e a matriz tapeé inicialmente zero. Portanto, essa linguagem de computador pode ser do tipo C ou Python, mas é muito limitada em seus tipos de dados. Na verdade, eles são tão limitados que nem sequer temos uma maneira de usar o ponteiro nem uma expressão booleana. Assumindo quetapeé infinito apenas para a direita, podemos declarar um "underflow" de ponteiro como "erro do sistema", se nalgum dia for negativo. Além disso, nossa linguagem possui uma exitdeclaração com um argumento para gerar uma resposta booleana.

O primeiro ponto é que essa linguagem de programação é uma boa linguagem de especificação para uma máquina de Turing. Você pode ver facilmente que, exceto para a matriz de fitas, o código possui apenas muitos estados possíveis: O estado de todas as suas variáveis ​​declaradas, a linha de execução atual e a pilha de sub-rotinas. Este último possui apenas uma quantidade finita de estado porque funções recursivas não são permitidas. Você pode imaginar um "compilador" que cria uma máquina de Turing "real" a partir de um código desse tipo, mas os detalhes não são importantes. O ponto é que temos uma linguagem de programação com uma sintaxe muito boa, mas com tipos de dados muito primitivos.

O restante da construção é convertê-lo em uma linguagem de programação mais habitável, com uma lista finita de funções da biblioteca e estágios de pré-compilação. Podemos proceder da seguinte forma:

1. Com um pré-compilador, podemos expandir o tipo de dados booleanos para um alfabeto de símbolos maior, porém finito, como ASCII. Podemos assumir que tapeassume valores neste alfabeto maior. Podemos deixar um marcador no início da fita para impedir o fluxo insuficiente do ponteiro e um marcador móvel no final da fita para impedir que a TM patine acidentalmente no infinito da fita. Podemos implementar operações binárias arbitrárias entre símbolos e conversões em instruções ife whileinstruções booleanas . (Na verdade, também ifpode ser implementado while, se não estiver disponível.)

2. $k$$k$$i$$i$$k$

3. Designamos uma fita como "memória" com valor de símbolo e as outras como "registradores" ou "variáveis" não assinadas e com valor inteiro. Armazenamos os números inteiros no binário little-endian com marcadores de terminação. Primeiro, implementamos a cópia de um registro e o decremento binário de um registro. Combinando isso com incremento e decremento do ponteiro de memória, podemos implementar a busca de acesso aleatório da memória de símbolo. Também podemos escrever funções para calcular a adição binária e a multiplicação de números inteiros. Não é difícil escrever uma função de adição binária com operações bit a bit e uma função para multiplicar por 2 com o deslocamento à esquerda. (Ou mudança para a direita, uma vez que é pouco endian.) Com essas primitivas, podemos escrever uma função para multiplicar dois registradores usando o algoritmo de multiplicação longa.

4. Podemos reorganizar a fita de memória de uma matriz de símbolos unidimensional symbol[n]para uma matriz de símbolos bidimensional symbol[x,y]usando a fórmula n = (x+y)*(x+y) + y. Agora podemos usar cada linha da memória para expressar um número inteiro não assinado em binário com um símbolo de terminação, para obter uma memória unidimensional, de acesso aleatório e com valor inteiro memory[x]. Podemos implementar a leitura da memória em um registro inteiro e a gravação de um registro na memória. Muitos recursos agora podem ser implementados com funções: aritmética de ponto flutuante e assinado, sequências de símbolos, etc.

5. Apenas mais uma instalação básica exige estritamente um pré-compilador, ou seja, funções recursivas. Isso pode ser feito com uma técnica amplamente usada para implementar linguagens interpretadas. Atribuímos a cada função recursiva de alto nível uma string de nome e organizamos o código de baixo nível em um whileloop grande que mantém uma pilha de chamadas com os parâmetros usuais: o ponto de chamada, a função chamada e uma lista de argumentos.

Neste ponto, a construção possui recursos suficientes de uma linguagem de programação de alto nível que funcionalidade adicional é mais o tópico de linguagens de programação e compiladores do que a teoria de CS. Também já é fácil escrever um simulador de máquina de Turing nessa linguagem desenvolvida. Não é exatamente fácil, mas certamente padrão, escrever um auto-compilador para o idioma. Obviamente, você precisa de um compilador externo para criar a TM externa a partir de um código nessa linguagem C ou Python, mas isso pode ser feito em qualquer linguagem de computador.

Observe que essa implementação esboçada não apenas suporta a tese de Church-Turing dos lógicos para a classe de função recursiva, mas também a tese de Church-Turing estendida (isto é, polinomial), conforme se aplica à computação determinística. Em outras palavras, possui sobrecarga polinomial. De fato, se recebermos uma máquina de RAM ou (meu favorito) uma TM de fita em árvore, isso pode ser reduzido a sobrecarga polilogarítmica para computação serial com memória RAM.

O compilador LLVM permite "conectar" de maneira bastante direta uma nova arquitetura. Eles chamam isso de redação de um novo backend e fornecem instruções e exemplos detalhados de como fazê-lo. Eu suspeito que você terá que passar por alguns obstáculos em relação à memória de acesso aleatório, se você não deseja direcionar uma máquina RAM Turing, mas isso é definitivamente possível, pois eu já vi vários projetos que causam a geração de LLVM VHDL ou outras linguagens de máquina muito diferentes.

Isso teria o efeito interessante de ter um compilador otimizador de última geração (de várias maneiras o LLVM é mais avançado que o GCC) gerando código para uma máquina de Turing.

Não estou na teoria cs, mas tenho algo que pode ser útil. Eu tomei outra abordagem. Eu projetei um processador simples diretamente programável com um pequeno subconjunto de C. Não há código de montagem, apenas código semelhante a C. Você pode usar a mesma ferramenta que eu usei e modificar esse processador para projetar seu simulador de máquina de Turing. Levei 4 dias para projetar, simular e testar este processador, bem, algumas instruções! As ferramentas que usei até me permitiram gerar código sintetizável VHDL real. É um verdadeiro processador de trabalho.

Aqui está a aparência de um programa:

Aqui está uma imagem do processador usando essas ferramentas:

As ferramentas "Novakod Studio" usam um idioma de descrição de hardware de idioma de alto nível. Como exemplo, aqui está o código do contador do programa: Chega de conversa, se alguém estiver interessado, aqui estão as informações públicas para entrar em contato comigo: https://repertoire.uqac.ca/Fiche.aspx?id=JjstNzsH0&link=1

Luc

Que tal levar a idéia representada pelo usuário GMB aqui (a máquina de Turing com uma fita pode simular uma máquina de Turing com fitas N entrelaçando as fitas N em uma única fita e lendo qualquer uma dessas fitas saltando N locais de cada vez, um Turing uma máquina com N fitas pode implementar ...) e escrever um programa de máquina de Turing que implementa uma máquina RAM simplista. A máquina de RAM pode realmente ser uma CPU simplista e real com back-end LLVM ou GCC disponível. Em seguida, o GCC / LLVM pode ser usado para compilar um programa C para essa CPU e o programa da máquina de Turing que simula a máquina RAM, executa a simulação da máquina RAM fazendo com que a máquina RAM simulada execute a saída GCC / LLVM. A implementação da máquina de Turing pode ser um código C muito simples que se ajusta a um pequeno arquivo C.

No que diz respeito à máquina RAM, existe um projeto de demonstração, em que uma CPU de 32 bits é simulada por um microcontrolador de 8 bits e a CPU de 32 bits simulada inicializa no Linux. Lento como o inferno, mas de acordo com o autor , Dmitry Grinberg, funcionou. Talvez a CPU Zylin (zylin do usuário do GitHub) possa ser uma opção viável para a máquina RAM simulável. Outro candidato à máquina RAМ pode ser o ProjectOberon dot com de Niklaus Wirth .

(O "ponto" e "com" no meu texto devem-se ao fato de eu apenas, 2015_10_21, registrar minha conta na cstheory.stackexchange e o aplicativo da web não permitir mais de dois links para usuários iniciantes, apesar do fato que eles podem ver automaticamente em minhas outras contas de troca de pilhas que eu posso ser estúpido, mas não sou um troll.)