Computadora con un conjunto de instrucciones

Las máquinas que manipulan bits son la clase más simple.

La arquitectura activada por transporte (TTA) es un diseño en el que el cálculo es un efecto secundario del transporte de datos. Generalmente, algunos registros de memoria (puertos de activación) dentro del espacio de direcciones común realizan una operación asignada cuando la instrucción los referencia. Por ejemplo, en una instrucción OISC que utiliza una sola instrucción de copia de memoria a memoria, esto se logra mediante puertos de activación que realizan saltos aritméticos y de punteros de instrucción al escribir en ellos.

Las máquinas Turing-completas basadas en aritmética utilizan una operación aritmética y un salto condicional. Al igual que las dos computadoras universales anteriores, esta clase también es Turing-completa. La instrucción opera sobre números enteros, que también pueden ser direcciones de memoria.

Actualmente se conocen varios OISC de esta clase, basados ​​en diferentes operaciones aritméticas:

• suma (addleq, suma y bifurca si es menor o igual a cero) ^{[ 6 ]}
• decremento (DJN, Decremento y bifurcación ( Salto ) si es distinto de cero) ^{[ 7 ]}
• incremento (P1eq, más 1 y bifurcación si es igual a otro valor) ^{[ 8 ]}
• resta (subleq, resta y bifurca si es menor o igual a cero) ^{[ 9 ] [ 10 ]}
• resta positiva cuando sea posible, de lo contrario bifurcación (máquina aritmética) ^{[ 11 ]}

La SBNZ a, b, c, d instrucción (" restar y saltar si no es igual a cero ") resta el contenido de la dirección a del contenido de la dirección b , almacena el resultado en la dirección c y, si el resultado no es 0 , transfiere el control a la dirección d (si el resultado es igual a cero, la ejecución continúa con la siguiente instrucción en la secuencia). ^{[ 3 ]}

La instrucción subleq (" restar y saltar si es menor o igual que cero ") resta el contenido de la dirección a del contenido de la dirección b , almacena el resultado en la dirección b y, si el resultado no es positivo , transfiere el control a la dirección c (si el resultado es positivo, la ejecución continúa con la siguiente instrucción en la secuencia). ^{[ 3 ] : 4–7} Pseudocódigo :

Instrucciónsubleqa,b,c Mem[b] = Mem[b] - Mem[a] si (Mem[b] ≤ 0) ir a c

La bifurcación condicional se puede suprimir asignando al tercer operando la dirección de la siguiente instrucción en la secuencia. Si no se especifica el tercer operando, esta supresión se da por supuesta.

También es posible una variante con dos operandos y un acumulador interno , donde el acumulador se resta de la ubicación de memoria especificada por el primer operando. El resultado se almacena tanto en el acumulador como en la ubicación de memoria, y el segundo operando especifica la dirección de bifurcación:

Instrucciónsubleq2a,b Mem[a] = Mem[a] - ACUMULADO ACUMULACIÓN = Mem[a] si (Mem[a] ≤ 0) ir a b

Aunque esto utiliza solo dos (en lugar de tres) operandos por instrucción, en consecuencia se necesitan más instrucciones para llevar a cabo diversas operaciones lógicas.

int memoria [], contador_programa , a , b , c contador_programa = 0 mientras ( contador_programa >= 0 ) : a = memoria [ contador_programa ] b = memoria [ contador_programa + 1 ] c = memoria [ contador_programa + 2 ] si ( a < 0 o b < 0 ) : contador_programa = -1 sino : memoria [ b ] = memoria [ b ] - memoria [ a ] si ( memoria [ b ] > 0 ) : contador_programa += 3 sino : contador_programa = c

La instrucción subneg (" restar y bifurcar si es negativo "), también llamada SBN , se define de forma similar a subleq : ^{[ 2 ] : 41, 51–52}

Instrucciónsubnega,b,c Mem[b] = Mem[b] - Mem[a] si (Mem[b] < 0) ir a c

La bifurcación condicional se puede suprimir asignando al tercer operando la dirección de la siguiente instrucción en la secuencia. Si no se especifica el tercer operando, esta supresión se da por supuesta.

Instrucción (* direcciones de sustraendo, minuendo, resultado y salto *)subnegs,m,r,j Mem[r] = Mem[m] - Mem[s] si (Mem[r] < 0) ir a j

En un intento por hacer que la máquina de Turing sea más intuitiva, Z.A. Melzak considera la tarea de calcular con números positivos. La máquina tiene un ábaco infinito, un número infinito de contadores (piedras, palitos de conteo) inicialmente en una ubicación especial S. La máquina es capaz de realizar una operación:

Toma de la ubicación X tantos contadores como haya en la ubicación Y y transfiérelos a la ubicación Z y procede con la instrucción y.

Si esta operación no es posible porque no hay suficientes contadores en X, entonces deje el ábaco como está y proceda con la instrucción n. ^{[ 19 ]}

Para mantener todos los números positivos e imitar a un operador humano calculando en un ábaco real, la prueba se realiza antes de cualquier resta. Pseudocódigo:

Instrucción si (Mem[X] < Mem[Y]) ir a nmelzakX,Y,Z,n,y Mem[X] -= Mem[Y] Mem[Z] += Mem[Y] ir a y

Tras presentar algunos programas (multiplicación, máximo común divisor, cálculo del enésimo número primo, representación en base b de un número arbitrario, ordenación por magnitud), Melzak muestra explícitamente cómo simular una máquina de Turing arbitraria en su máquina aritmética.

MUL p, q

multiplicar: melzak P , ONE , S , stop ; Mueve 1 contador de P a S. Si no es posible, muévelo a stop. melzak S , Q , ANS , multiplicar , multiplicar ; Mueve q contadores de S a ANS. Muévete a la primera instrucción. stop:

donde la ubicación de memoria P es p , Q es q , ONE es 1, ANS es inicialmente 0 y al final pq , y S es un número grande.

Menciona que se puede demostrar fácilmente, utilizando los elementos de las funciones recursivas, que todo número calculable en la máquina aritmética es computable. Lambek ^{[ 20 ]} dio una prueba de ello en una máquina equivalente de dos instrucciones  : X+ (incrementar X) y X− si no, T (decrementar X si no está vacío, si no, saltar a T).

En una instrucción de resta inversa y salto si hay préstamo (RSSB), el acumulador se resta de la ubicación de memoria y la siguiente instrucción se omite si hubo un préstamo (la ubicación de memoria era menor que el acumulador). El resultado se almacena tanto en el acumulador como en la ubicación de memoria. El contador de programa se asigna a la ubicación de memoria 0. El acumulador se asigna a la ubicación de memoria 1. ^{[ 2 ]}

Instrucciónrssbx ACUM = Mem[x] - ACUM Mem[x] = ACUMULACIÓN Si (ACCUM < 0) ir a PC + 2

# Primero, mueve z a la ubicación de destino x. RSSB temp # Se requieren tres instrucciones para borrar acc, temp [Ver Nota 1] RSSB temp RSSB temp RSSB x # Dos instrucciones borran acc, x, ya que acc ya está borrado RSSB x RSSB y # Carga y en acc: no se presta RSSB temp # Almacena -y en acc, temp: siempre se presta y se omite RSSB temp # Omitido RSSB x # Almacena y en x, acc # Segundo, realiza la operación. RSSB temp # Se requieren tres instrucciones para borrar acc, temp RSSB temp RSSB temp RSSB z # Carga z RSSB x # x = y - z [Ver Nota 2]

Una arquitectura activada por transporte utiliza únicamente la instrucción move , por lo que originalmente se la denominó "máquina move". Esta instrucción mueve el contenido de una ubicación de memoria a otra ubicación de memoria combinándolo con el contenido actual de la nueva ubicación: ^{[ 2 ] : 42 [ 21 ]}

Instrucción (también escrita a -> b )movxa,b OP = ObtenerOperación(Mem[ b ]) Memoria[ b ] := OP(Mem[ a ], Memoria[ b ])

La operación que se realiza viene definida por la celda de memoria de destino. Algunas celdas están especializadas en sumas, otras en multiplicaciones, etc. Por lo tanto, las celdas de memoria no son simples almacenes, sino que están acopladas a una unidad aritmético-lógica (ALU) configurada para realizar un único tipo de operación con el valor actual de la celda. Algunas celdas contienen instrucciones de control de flujo para modificar la ejecución del programa mediante saltos, ejecución condicional , subrutinas , estructuras if-then-else , bucles for , etc.

Se ha producido un microcontrolador comercial con arquitectura de activación por transporte llamado MAXQ, que oculta el aparente inconveniente de un OISC mediante el uso de un "mapa de transferencia" que representa todos los posibles destinos para las instrucciones de movimiento . ^{[ 22 ]}

Cryptoleq ^{[ 23 ]} es un lenguaje similar a Subleq. Consta de una instrucción homónima y es capaz de realizar cálculos de propósito general en programas cifrados. Cryptoleq funciona en celdas de memoria contiguas utilizando direccionamiento directo e indirecto, y realiza dos operaciones O ₁ y O ₂ en tres valores A, B y C:

Instrucción Mem[b] = O 1 (Mem[a], Mem[b]) si O 2 (Mem[b]) ≤ 0cryptoleqa,b,c IP = c de lo contrario IP = IP + 3

donde a, b y c son direccionados por el puntero de instrucción, IP, con el valor de IP direccionando a, IP + 1 apuntando a b e IP + 2 a c.

En las operaciones de Cryptoleq, O ₁ y O ₂ se definen de la siguiente manera:

${\displaystyle {\begin{array}{lcl}O_{1}(x,y)&=&x^{-1}y\,{\bmod {\,}}N^{2}\end{array}}}$

${\displaystyle {\begin{array}{lcl}O_{2}(x)&=&\left\lfloor {\frac {x-1}{N}}\right\rfloor \end{array}}}$

La principal diferencia con Subleq es que en Subleq, O ₁ ( x,y ) simplemente resta y de x y O ₂ ( x ) es igual a x . Cryptoleq también es homomórfico a Subleq; la inversión modular y la multiplicación son homomórficas a la resta, y la operación O ₂ corresponde a la prueba de Subleq si los valores no estuvieran cifrados. Un programa escrito en Subleq puede ejecutarse en una máquina Cryptoleq, lo que significa retrocompatibilidad. Sin embargo, Cryptoleq implementa cálculos totalmente homomórficos y es capaz de realizar multiplicaciones. La multiplicación en un dominio cifrado se realiza mediante una función única G que se supone difícil de descifrar y permite volver a cifrar un valor basándose en la operación O _{2 .}

${\displaystyle G(x,y)={\begin{cases}{\tilde {0}},&{\text{if }}O_{2}({\bar {x}}){\text{ }}\leq 0\\{\tilde {y}},&{\text{otherwise}}\end{cases}}}$

dónde${\displaystyle {\tilde {y}}}$es el valor reencriptado de y y${\displaystyle {\tilde {0}}}$es cero cifrado. x es el valor cifrado de una variable, sea m , y${\displaystyle {\bar {x}}}$igual a${\displaystyle Nm+1}$.​

El algoritmo de multiplicación se basa en la suma y la resta, utiliza la función G y no tiene saltos ni bifurcaciones condicionales. El cifrado Cryptoleq se basa en el criptosistema Paillier .