En teoría de la computación , la máquina Blum-Shub-Smale , o máquina BSS , es un modelo de computación introducido por Lenore Blum , Michael Shub y Stephen Smale , destinado a describir cálculos sobre los números reales . Esencialmente, una máquina BSS es una máquina de acceso aleatorio con registros que pueden almacenar números reales arbitrarios y que pueden calcular funciones racionales sobre reales en un solo paso de tiempo. A menudo se lo conoce como modelo de RAM real. Las máquinas BSS son más potentes que las máquinas de Turing, porque estos últimos están por definición restringidos a un alfabeto finito. Una máquina de Turing puede tener el poder de almacenar números racionales arbitrarios en un solo símbolo de cinta haciendo que ese alfabeto finito sea arbitrariamente grande (en términos de una máquina física que usa memoria basada en transistores , construyendo sus ubicaciones de memoria de suficientes transistores para almacenar el número deseado), pero esto no se extiende a los incontables números reales (por ejemplo, ningún número de transistores puede representar Pi con precisión ).
Definición
Una máquina BSS M viene dada por una lista de instrucciones (que se describirán a continuación), indexadas . Una configuración de M es una tupla, donde k es el índice de la instrucción que se ejecutará a continuación, r y w son registros de copia que contienen números enteros no negativos, yes una lista de números reales, con todos menos un número finito de cero. La lista se piensa que contiene el contenido de todos los registros de M. El cálculo comienza con la configuración y termina cuando sea ; se dice que el contenido final de x es la salida de la máquina.
Las instrucciones de M pueden ser de los siguientes tipos:
- Cálculo: una sustitución se realiza, donde es una función racional arbitraria (un cociente de dos funciones polinomiales con coeficientes reales arbitrarios); copiar registros r y w puede cambiarse, ya sea por o y de manera similar para w. La siguiente instrucción es k +1.
- Rama: Si luego ve a ; de lo contrario, vaya a k +1.
- Dupdo(): el contenido del registro "leído" se copia en el registro de "escritura" ; la siguiente instrucción es k +1
Ver también
Otras lecturas
- Bürgisser, Peter (2000). Completitud y reducción en la teoría de la complejidad algebraica . Algoritmos y Computación en Matemáticas. 7 . Berlín: Springer-Verlag . ISBN 3-540-66752-0. Zbl 0948.68082 .
- Grädel, E. (2007). "Teoría de modelos finitos y complejidad descriptiva". Teoría de modelos finitos y sus aplicaciones (PDF) . Springer-Verlag. págs. 125–230. Zbl 1133.03001 .
- Blum, Lenore ; Shub, Mike ; Smale, Steve (1989). "Sobre una teoría de la computación y la complejidad sobre los números reales: NP-completitud, funciones recursivas y máquinas universales" (PDF) . Boletín de la American Mathematical Society . 21 (1): 1–46. doi : 10.1090 / S0273-0979-1989-15750-9 . Zbl 0681.03020 .