¿Cuál es el conjunto mínimo absoluto de instrucciones requeridas para construir un procesador completo de Turing?

19

Tengo una idea general de cómo el procesador maneja las instrucciones, pero paso mi tiempo trabajando principalmente en idiomas de alto nivel. Tal vez alguien que trabaje más cerca del hierro puede proporcionar alguna información valiosa.

Suponiendo que los lenguajes de programación son básicamente abstracciones de muy alto nivel del conjunto de instrucciones de un procesador, ¿cuál es el conjunto de instrucciones más básico necesario para crear una máquina completa?

Nota: No sé nada sobre la diversidad de arquitecturas de hardware pero, por simplicidad, supongamos que es un procesador típico con una ALU (si es necesario) y una pila de instrucciones. * *

Evan Plaice
fuente
Computer Science SE podría ser un mejor lugar para hacer preguntas similares. (No tiene sentido dirigirlo allí en este momento). Sin embargo, es una pregunta interesante.
Oskar Skog
A medida que disminuye el número de instrucciones que tiene un ISA, también lo hace la importancia del NÚMERO de instrucciones. Los ISA se vuelven más extraños cuando tienen menos instrucciones que un RISC "óptimo". Un ISA con una sola instrucción será extraño. // También se vuelven más extraños a medida que aumenta el número y el ISA se convierte en un CISC. // "extraño" es, por supuesto, más o menos subjetivo.
Oskar Skog

Respuestas:

35

Resulta que solo necesita una instrucción para construir una máquina capaz de calcular Turing. Esta clase de máquinas que tienen una sola instrucción y están completas en Turing se llama Computadoras de un conjunto de instrucciones o también, en cierto modo de broma, Ultimate RISC .

Jörg W Mittag
fuente
44
+1 para obtener la mejor respuesta posible, a menos que se encuentre una solución de instrucción cero (en realidad, las computadoras de una instrucción a veces se llaman computadoras de instrucción cero, porque no se encuentra información en la instrucción en sí)
Cort Ammon - Reinstala a Monica
44
Sí, pero esa única instrucción no es lo que hace que la máquina Turing sea completa: la magia está en todos los diferentes registros especializados que la instrucción puede abordar. Creo que su respuesta señala que el OP equipara "computadora" con "arquitectura de Von Neumann", cuando en realidad, la categoría "computadoras" es mucho más amplia que eso.
Solomon Slow
2
@jameslarge La magia no está necesariamente en registros especializados. BitBitJump, SBNZ, SUBLEQ y SUBNEG no necesitan registros en absoluto, solo una sola instrucción cada uno y memoria tonta.
8bittree
2
@ 8bittree, Hunh! Supongo que olvidé que diseñar arquitecturas extrañas pero completas de Turing es un deporte competitivo. Cuando leí la respuesta de Jörg, recordé a un amigo de mi época de pregrado (alrededor de 1980-algo) que planeaba construir una "computadora de una sola instrucción" a partir de chips de la serie 74LS, y luego programarla para emular un DecSystem 10. Solo miré en la página de Wikipedia, y ahora sé que su diseño se llamaría hoy "Arquitectura activada por el transporte". No sé si alguna vez lo siguió.
Solomon Slow
2
@jameslarge: Intel MMU también está completa de Turing (en particular, el mecanismo de trampa). De hecho, es muy extraño, sin embargo, es lo contrario de ser diseñado, es un puro accidente.
Jörg W Mittag
15

Hay muchas formas de implementar algo en lo que uno puede implementar una máquina de turing.

Mientras observa los procesadores, el que sea más aplicable probablemente sea el modelo de máquina de registro . El más simple de estos (en términos de símbolos) es el símbolo de mulit-tape two ( marky blank). Si usted va para algo no tan esotérica, la inc(r), dec(r)y jz(r,z)(salto si el registro res cero a la instrucción z) o la clr(r)(clara r), inc, je(i,j,z)(salto si se registra iyj son igual a z de instrucciones).

He visto mención de una máquina de registro que es:

  • inc (i, m): incremente el registro i y vaya a la línea m
  • jzdec (i, m1, m2): si el registro i es 0, vaya a la línea m, de lo contrario disminuya i, y vaya a la línea m2

que también está completo: es una máquina de registro Minsky, aunque tiene otras restricciones en los datos de la cinta (tiene que ser un número de Gödel que almacena el estado en lugar de registros individuales)

Eso es. Nada mas.


Entonces, ¿por qué no se utilizan estos procesadores ultra risc? Es un verdadero dolor escribir un compilador para ellos y renunciar a muchas otras cosas que el procesador puede hacer. Es realmente agradable tener un bit a bit and, y en addlugar de tratar de hacer todo con registros incrementales y bucles. Esa es la base de un lenguaje de programación favorito titulado Brainfuck que tiene 8 instrucciones.

  • > incrementar el puntero de datos
  • < disminuir el puntero de datos
  • + incrementar los datos en el puntero de datos
  • - disminuir los datos en el puntero de datos
  • . generar los datos en el puntero de datos
  • , leer entrada, almacenar los datos en el puntero de datos
  • [Si los datos en el puntero son cero, en lugar de mover el puntero de instrucción hacia adelante, avance hacia el comando después del ]comando correspondiente
  • ]Si los datos en el puntero no son cero, en lugar de mover el puntero de instrucciones hacia adelante, vuelva al comando después del ]comando correspondiente

Uno puede encontrar compiladores para Brainfuck, aunque realmente no es divertido hacer incluso cosas simples en él. A menos que disfrutes de la frustración, que es el propósito del lenguaje.

Lectura relacionada:

Comunidad
fuente
5

Sospecho que Post machine es la forma más simple de un dispositivo completo de Turing. Necesita un suministro de memoria direccionable en bits, un registro de dirección que apunte a la ubicación de datos actual y cinco instrucciones:

  • Establecer el bit en la ubicación actual;
  • Restablezca el bit en la ubicación actual;
  • Moverse a la siguiente dirección (incrementar el registro de la dirección de datos);
  • Moverse a la dirección anterior (disminuir el registro de la dirección de datos);
  • Verifique el bit en la ubicación de datos actual.

No creo que sea fácil inventar algo mucho más simple en cuanto a hardware, aunque probablemente exista algo aún más reducido.

9000
fuente
5

Implementaciones

Esta respuesta se centrará en implementaciones interesantes de CPU, compiladores y ensambladores de conjuntos de instrucciones individuales.

movfuscator

https://github.com/xoreaxeaxeax/movfuscator

Compila el código C usando solo movinstrucciones x86, mostrando de manera muy concreta que una sola instrucción es suficiente.

La integridad de Turing parece haberse demostrado en un artículo: https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

subleq

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

Ver también

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

Ciro Santilli 新疆 改造 中心 法轮功 六四 事件
fuente
3

¿Cuál es el conjunto mínimo absoluto de instrucciones requeridas para construir un procesador completo de Turing?

Jörg W Mittag dijo "uno", pero ¿qué tal cero?

¿Por qué supone que un "procesador" debe tener "instrucciones"?

Una máquina Turing es un procesador completo de Turing, y no funciona con "instrucciones" como tales. Tiene reglas , pero las reglas no son instrucciones que se obtienen de una memoria de acceso aleatorio.

Cuando Alan Turing pensó en su máquina homónima, estaba buscando el modelo más simple posible de "computación" para poder utilizar técnicas matemáticas para responder a la pregunta: "¿Qué es computable?"

Sería difícil diseñar una máquina equivalente a Turing que sea más simple que una máquina real de Turing.

FWIW, el tipo de procesador en el que está pensando --- uno que obtiene instrucciones de la memoria, las decodifica y las ejecuta, y que opera en los datos almacenados en el mismo sistema de memoria --- se conoce como Arquitectura de Von Neumann

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

Salomón lento
fuente