A máquina de Turing é um conceito matemático teórico criado por Alan Turing que consiste em um modelo abstrato de uma máquina de estado capaz de executar tarefas genéricas.

A máquina de Turing é formada por quatro partes:

1. Uma fita dividida em células, cada uma representando uma instrução a ser executada. O tamanho da fita é o suficiente para representar a tarefa pretendida.
2. Um registro de estados de tamanho suficiente para executar a tarefa pretendida.
3. Um cabeçote que lê as instruções da fita e as executa de acordo com um alfabeto conhecido.
4. Um alfabeto conhecido com instruções que define ações como mover a fita ou alterar estados do registro.

Podemos traçar um paralelo com o computador moderno: a fita são as instruções dadas ao processador, o registro de estados é a memória, o cabeçote é o processador e o alfabeto é o microprograma do processador.

Brainfuck é uma linguagem de programação esotérica criada em 1993 para o AmigaOS. Brainfuck é interessante porque implementa a máquina de Turing de forma restrita e minimalista.

Recomendo o artigo na Wikipédia, que explica muito bem.

Vamos usar Prolog pra implementar o interpretador.

Lista de conteúdo

• Parte 1: A fita
• Parte 2: A memória
• Parte 3: Cabeçote e microprograma
• Parte 4: Finalização

• tape.pl
• test.tape
• utils.pl
• memory.pl
• parser.pl
• brainfuck.pl
• hello.bf