Qual é o conjunto mínimo absoluto de instruções necessárias para construir um processador completo Turing

19

Tenho uma ideia geral de como o processador lida com instruções, mas passo meu tempo trabalhando em idiomas de alto nível. Talvez alguém que trabalhe mais perto do ferro possa fornecer informações valiosas.

Supondo que as linguagens de programação sejam basicamente abstrações de nível muito alto do conjunto de instruções de um processador, qual é o conjunto mais básico de instruções necessárias para criar uma máquina completa de turing?

Nota: Não sei nada sobre a diversidade de arquiteturas de hardware, mas - por uma questão de simplicidade - vamos supor que seja um processador típico com uma ALU (se necessário) e pilha de instruções. *

Evan Plaice
fonte
O Computer Science SE pode ser um lugar melhor para fazer perguntas semelhantes. (Não faz sentido direcioná-lo para lá no momento.) Porém, pergunta interessante.
Oskar Skog
À medida que o número de instruções que um ISA diminui, o mesmo acontece com a plenitude de significado do NÚMERO de instruções. Os ISAs ficam mais estranhos quando têm menos instruções do que um RISC "ideal". Um ISA com apenas uma instrução será estranho. // Eles também ficam mais estranhos à medida que o número aumenta e o ISA se torna um CISC. // "estranho" é obviamente mais ou menos subjetivo.
Oskar Skog

Respostas:

35

Acontece que você só precisa de uma instrução para construir uma máquina capaz de calcular Turing. Essa classe de máquinas que possuem apenas uma instrução e são completas de Turing é chamada de Computadores com um conjunto de instruções ou também, um tanto brincando, Ultimate RISC .

Jörg W Mittag
fonte
4
+1 para bater a melhor resposta possível, a menos que uma solução instrução zero é encontrado (na verdade, um computadores de instrução às vezes são chamados computadores de instrução de zero, porque não há nenhuma informação encontrada na própria instrução)
Cort Ammon - Reintegrar Monica
4
Sim, mas essa instrução não é o que torna a máquina Turing completa: a mágica está em todos os diferentes registros especializados que a instrução pode abordar. Acho que sua resposta aponta que o OP equipara "computador" a "arquitetura Von Neumann"; quando, na verdade, a categoria "computadores" é muito mais ampla que isso.
Solomon Slow
2
@jameslarge A mágica não está necessariamente em registros especializados. BitBitJump, SBNZ, SUBLEQ e SUBNEG não precisam de registros, apenas uma única instrução cada e memória estúpida.
precisa saber é o seguinte
2
@ 8bittree, Hunh! Acho que esqueci que projetar arquiteturas estranhas, mas completas de Turing, é um esporte competitivo. Quando li a resposta de Jörg, lembrei-me de um amigo de meus tempos de graduação (por volta de 1980) que planejava construir um "computador de uma instrução" a partir dos chips da série 74LS e depois programá-lo para emular um DecSystem 10. Eu apenas olhei na página da Wikipedia, e agora eu sei que seu design seria hoje chamado de "Arquitetura Acionada por Transporte". Não sei se ele alguma vez o seguiu.
Solomon Slow
2
@ jameslarge: o Intel MMU também é Turing-complete (em particular, o mecanismo de interceptação). É realmente muito estranho, no entanto, é o oposto de ser projetado, é um acidente puro.
Jörg W Mittag
15

Existem muitas maneiras de implementar algo em que se pode implementar uma máquina de turing.

Enquanto você olha para os processadores, o mais aplicável é provavelmente o modelo da máquina de registro . O mais simples deles (em termos de símbolos) é o símbolo mulit-tape two ( marke blank). Se você ir para algo não tão esotérico, a inc(r), dec(r)e jz(r,z)(salto se o registrador ré zero a instrução z) ou a clr(r)(claro r), inc, je(i,j,z)(salto se registar i e j são iguais a instrução z).

Eu já vi menção de uma máquina de registro que é:

  • inc (i, m) - incremente o registro ie vá para a linha m
  • jzdec (i, m1, m2) - se o registro i for 0, vá para a linha m, então diminua i e vá para a linha m2

que também está completo - é uma máquina de registro Minsky, embora tenha outras restrições nos dados da fita (deve ser um número de Gödel que armazena o estado em vez de registros individuais)

É isso aí. Nada mais.


Então, por que esses processadores ultra-risc não são usados? É realmente difícil escrever um compilador para eles e você desiste de muitas outras coisas que o processador pode fazer. É realmente bom ter um pouco de detalhes and, e um addpouco do que tentar fazer tudo com incrementos de registros e loop. Essa é a base de uma linguagem de programação favorita, chamada Brainfuck, que possui 8 instruções.

  • > incrementar o ponteiro de dados
  • < diminuir o ponteiro de dados
  • + incrementar os dados no ponteiro de dados
  • - diminuir os dados no ponteiro de dados
  • . emitir os dados no ponteiro de dados
  • , entrada de leitura, armazenando os dados no ponteiro de dados
  • [se os dados no ponteiro forem zero, em vez de mover o ponteiro de instrução para frente, pule-o para o comando após o ]comando correspondente
  • ]se os dados no ponteiro forem diferentes de zero, em vez de avançar o ponteiro de instruções, volte para o comando após o ]comando correspondente

Pode-se encontrar compiladores para o Brainfuck, embora não seja realmente divertido fazer coisas simples nele. A menos que você goste da frustração, que é o objetivo do idioma.

Leitura relacionada:

Comunidade
fonte
5

Suspeito que a máquina Post seja a forma mais simples de um dispositivo completo de Turing. Você precisa de um suprimento de memória endereçável por bits, um registro de endereço que aponte para o local de dados atual e cinco instruções:

  • Defina o bit no local atual;
  • Redefina o bit no local atual;
  • Mover para o próximo endereço (incremento de registro de endereço de dados);
  • Mover para o endereço anterior (diminuir o registro do endereço de dados);
  • Verifique o bit no local de dados atual.

Não acho fácil inventar algo muito mais simples em termos de hardware, embora exista algo ainda mais reduzido.

9000
fonte
5

Implementações

Esta resposta se concentrará em implementações interessantes de CPUs, compiladores e montadores de conjunto de instruções único.

movfuscator

https://github.com/xoreaxeaxeax/movfuscator

Compila o código C usando apenas movinstruções x86, mostrando de uma maneira muito concreta que uma única instrução é suficiente.

A integridade de Turing parece ter sido comprovada em um artigo: https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

subleq

https://esolangs.org/wiki/Subleq :

Veja também

/programming/3711443/minimal-instruction-set-to-solve-any-problem-with-a-computer-program/38523869#38523869

Ciro Santilli adicionou uma nova foto
fonte
3

Qual é o conjunto mínimo absoluto de instruções necessárias para construir um processador completo Turing?

Jörg W Mittag disse "um", mas que tal zero?

Por que você supõe que um "processador" precisa ter "instruções"?

Uma máquina de Turing é um processador completo de Turing e não opera com "instruções" como tal. Possui regras , mas as regras não são instruções que são buscadas a partir de uma memória de acesso aleatório.

Quando Alan Turing pensou em sua máquina homônima, estava procurando o modelo mais simples possível de "computação" para poder usar técnicas matemáticas para responder à pergunta "O que é computável?"

Você teria dificuldade em projetar uma máquina equivalente a Turing mais simples que uma máquina de Turing real.

O FWIW, o tipo de processador em que você está pensando - aquele que busca instruções na memória, decodifica e executa - e que opera com dados armazenados no mesmo sistema de memória - é conhecido como Arquitetura de Von Neumann

https://en.wikipedia.org/wiki/Von_Neumann_architecture

Salomão Lento
fonte