Màquina de registres

En lògica matemàtica i informàtica teòrica, una màquina de registres és una classe genèrica de màquines abstractes utilitzades d'una manera similar a una màquina de Turing. Tots els models són equivalents a Turing.

Visió general

La màquina de registre rep el seu nom de l'ús d'un o més "registres". A diferència de la cinta i el capçal utilitzats per una màquina de Turing, el model utilitza múltiples registres amb adreça única, cadascun dels quals conté un únic nombre enter positiu.^[1]

Hi ha almenys quatre subclasses que es troben a la literatura, aquí enumerades de les més primitives a les més semblants a un ordinador: ^[2]

• Counter machine: el model teòric més primitiu i reduït d'un maquinari informàtic. Falta adreçament indirecte. Les instruccions es troben a la màquina d'estats finits a la manera de l'arquitectura de Harvard.
• Màquina de punter: una combinació de models de màquina de comptador i RAM. Menys comú i més abstracte que qualsevol dels dos models. Les instruccions es troben a la màquina d'estats finits a la manera de l'arquitectura de Harvard.
• Màquina d'accés aleatori (RAM): una màquina comptadora amb adreçament indirecte i, generalment, un conjunt d'instruccions augmentat. Les instruccions es troben a la màquina d'estats finits a la manera de l'arquitectura de Harvard.
• Model de màquina de programa emmagatzemat d'accés aleatori (RASP): una memòria RAM amb instruccions en els seus registres anàlogues a la màquina Universal de Turing; així és un exemple de l'arquitectura de von Neumann. Però a diferència d'un ordinador, el model està idealitzat amb registres efectivament infinits (i, si s'utilitza, registres especials efectivament infinits, com ara un acumulador). En comparació amb un ordinador, el conjunt d'instruccions és molt reduït en nombre i complexitat.

Qualsevol model de màquina de registre ben definit és equivalent a Turing. La velocitat de càlcul depèn molt de les especificitats del model.

A la informàtica pràctica, de vegades s'utilitza un concepte similar conegut com a màquina virtual per minimitzar les dependències de les arquitectures de màquines subjacents. Aquestes màquines també s'utilitzen per a l'ensenyament. El terme "màquina de registre" s'utilitza de vegades per referir-se a una màquina virtual als llibres de text.^[3]

Definició formal

Una màquina de registre consta de: ^[4]

1. Un nombre il·limitat de registres etiquetats, discrets i il·limitats sense límits en extensió (capacitat) : un conjunt finit (o infinit en alguns models) de registres cadascun es considera d'extensió infinita i cadascun dels quals conté un sol enter no negatiu (0, 1, 2,...). Els registres poden fer la seva pròpia aritmètica, o pot haver-hi un o més registres especials que facin l'aritmètica, per exemple, un "acumulador" i/o un "registre d'adreces". Vegeu també Màquina d'accés aleatori.
2. Comptadors o marques : objectes discrets, indistinguibles o marques d'un sol tipus adequats per al model. En el model de comptador més reduït, per cada operació aritmètica només s'afegeix un objecte/marca o s'elimina de la seva ubicació/cinta. En alguns models de màquina comptadora (per exemple, Melzak, Minsky ) i la majoria dels models RAM i RASP es pot afegir o eliminar més d'un objecte/marca en una operació amb "suma" i normalment "resta"; de vegades amb "multiplicació" i/o "divisió". Alguns models tenen operacions de control com ara "copiar" (diversament: "moure", "carregar", "emmagatzemar") que mouen "grups" d'objectes/marques d'un registre a un altre en una acció.
3. Un conjunt (molt) limitat d'instruccions : les instruccions tendeixen a dividir-se en dues classes: aritmètica i control. Les instruccions s'extreuen de les dues classes per formar "conjunts d'instruccions", de manera que un conjunt d'instruccions ha de permetre que el model sigui equivalent a Turing (ha de ser capaç de calcular qualsevol funció recursiva parcial).
   1. Aritmètica : les instruccions aritmètiques poden funcionar en tots els registres o només en un registre especial (per exemple, acumulador). Normalment es trien entre els següents conjunts (però hi ha excepcions):
      • Comptador: {Increment (r), Decrement (r), Clear-to-zero (r)}
      • RAM reduïda, RASP: { Increment (r), Decrement (r), Clear-to-zero (r), Load-immediata-constant k, Add (r ₁ ,r ₂ ), Prop-Restaure (r ₁ ,r _{2 )}, ), Increment de l'acumulador, Decrement de l'acumulador, Neteja de l'acumulador, Afegeix al contingut de l'acumulador del registre r, propi-Resta del contingut de l'acumulador del registre r, }
      • RAM augmentada, RASP: totes les instruccions reduïdes més: { Multiplicar, Dividir, diversos bits booleans (desplaçament a l'esquerra, prova de bits, etc.)}
   2. Control :
      • Models de màquines de comptador: opcional { Còpia (r ₁ ,r ₂ ) }
      • Models RAM i RASP: la majoria tenen { Còpia (r ₁ ,r ₂ ) }, o { Carregar acumulador des de r, Emmagatzemar acumulador a r, Carregar acumulador amb constant immediata}
      • Tots els models: almenys un "salt" condicional (branca, goto) després de la prova d'un registre, p. ex. { Salt-si-zero, Jump-si-not-zero (és a dir, Salt-si-positiu), Jump-si-igual, Saltar si no és igual}
      • Tots els models són opcionals: { incondicional program jump (goto)}
   3. Mètode d'adreça del registre :
      • Màquina de comptador: sense adreçament indirecte, operands immediats possibles en models altament atomitzats
      • RAM i RASP: adreçament indirecte disponible, operands immediats típics
   4. Entrada-sortida : opcional en tots els models
4. Registre estatal : Un registre d'instruccions especial "IR", finit i separat dels registres anteriors, emmagatzema la instrucció actual a executar i la seva adreça a la TAULA d'instruccions; aquest registre i la seva TAULA es troben a la màquina d'estats finits.
   • L'IR està fora de límit per a tots els models. En el cas de la RAM i el RASP, a efectes de determinar l'"adreça" d'un registre, el model pot seleccionar (i) en el cas de l'adreçament directe: l'adreça especificada per la TAULA i situada temporalment a l'IR o bé (ii) en el cas d'adreçament indirecte: el contingut del registre especificat per la instrucció de l'IR.
   • L'IR no és el "comptador de programes" (PC) del RASP (o ordinador convencional). El PC és només un altre registre similar a un acumulador, però dedicat a mantenir el número de la instrucció actual basada en el registre del RASP. Així, un RASP té dos registres d'"instrucció/programa": (i) l'IR (Registre d'instruccions de la màquina d'estats finits) i (ii) un PC (Comptador de programes) per al programa situat als registres. (A més d'un registre dedicat a "el PC", un RASP pot dedicar un altre registre al "Registre d'instruccions del programa" (amb qualsevol nombre de noms com "PIR, "IR", "PR", etc.)
5. Llista d'instruccions etiquetades, generalment en ordre seqüencial : una llista finita d'instruccions. En el cas de la màquina comptadora, la màquina d'accés aleatori (RAM) i la màquina punter, el magatzem d'instruccions es troba a la "TAULA" de la màquina d'estats finits; per tant, aquests models són exemple de l'arquitectura de Harvard. En el cas del RASP, el magatzem de programes es troba als registres; per tant, aquest és un exemple de l'arquitectura de von Neumann. Vegeu també Màquina d'accés aleatori i Màquina de programes emmagatzemats d'accés aleatori. Normalment, com els programes informàtics, les instruccions es mostren en ordre seqüencial; tret que un salt tingui èxit, la seqüència per defecte continua en ordre numèric. Una excepció a això són els models de màquina comptadora àbac : cada instrucció té almenys un identificador d'instrucció "següent" "z", i la branca condicional en té dos.
   • Observeu també que el model d'àbac combina dues instruccions, JZ després DEC: per exemple { INC (r, z ), JZDEC (r, z _true, z _false ) }. </br> Vegeu el formalisme de McCarthy per obtenir més informació sobre l' expressió condicional "SI r=0 LLAVORS z _cert ELSE z _fals "

Referències

1. «Register Machine - an overview | ScienceDirect Topics» (en anglès). [Consulta: 28 novembre 2023].
2. «5.2: A Register-Machine Simulator» (en anglès), 07-06-2021. [Consulta: 28 novembre 2023].
3. Weisstein, Eric W. «Register Machine» (en anglès). [Consulta: 28 novembre 2023].
4. «5: Computing with Register Machines» (en anglès), 07-06-2021. [Consulta: 28 novembre 2023].