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. *
hardware
low-level
turing-completeness
Evan Plaice
fonte
fonte
Respostas:
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 .
fonte
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 (
mark
eblank
). Se você ir para algo não tão esotérico, ainc(r)
,dec(r)
ejz(r,z)
(salto se o registradorr
é zero a instruçãoz
) ou aclr(r)
(claror
),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 é:
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 umadd
pouco 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 correspondentePode-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:
fonte
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:
Não acho fácil inventar algo muito mais simples em termos de hardware, embora exista algo ainda mais reduzido.
fonte
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
mov
instruçõ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
fonte
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
fonte