Máquina Blum–Shub–Smale

Modelo de cálculo sobre números reales

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 los cálculos sobre los números reales . ^[1] 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 números reales en un solo paso de tiempo. Está estrechamente relacionada con el modelo de RAM real .

Las máquinas BSS son más potentes que las máquinas de Turing , porque estas últimas están restringidas por definición a un conjunto finito de símbolos. ^[2] Una máquina de Turing puede representar un conjunto contable (como los números racionales) mediante cadenas de símbolos, pero esto no se extiende a los números reales incontables .

Definición

Una máquina BSS M está dada por una lista de instrucciones (que se describirán a continuación), indexada . Una configuración de M es una tupla , donde es el índice de la instrucción que se ejecutará a continuación, y son registros que contienen números enteros no negativos, y es una lista de números reales, donde todos, excepto un número finito, son cero. Se piensa que la lista contiene el contenido de todos los registros de M . El cálculo comienza con la configuración y termina cuando ; se dice que el contenido final de es la salida de la máquina. ${\displaystyle I}$ ${\displaystyle N+1}$ ${\displaystyle 0,1,\dots ,N}$ ${\displaystyle (k,r,w,x)}$ ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle w}$ ${\displaystyle x=(x_{0},x_{1},\ldots )}$ ${\displaystyle x}$ ${\displaystyle (0,0,0,x)}$ ${\displaystyle k=N}$ ${\displaystyle x}$

Las instrucciones de M pueden ser de los siguientes tipos:

• Cálculo : se realiza una sustitución , donde es una función racional arbitraria (un cociente de dos funciones polinómicas con coeficientes reales arbitrarios); los registros y pueden cambiarse por o y de manera similar para . La siguiente instrucción es . ${\displaystyle x_{0}:=g_{k}(x)}$ ${\displaystyle g_{k}}$ ${\displaystyle r}$ ${\displaystyle w}$ ${\displaystyle r:=0}$ ${\displaystyle r:=r+1}$ ${\displaystyle w}$ ${\displaystyle k+1}$
• Branch( ) ${\displaystyle l}$ : si entonces goto ; de lo contrario goto . ${\displaystyle x_{0}\geq 0}$ ${\displaystyle l}$ ${\displaystyle k+1}$
• Copiar ( ): el contenido del registro "leído" se copia en el registro "escrito" ; la siguiente instrucción es . ${\displaystyle x_{r},x_{w}}$ ${\displaystyle x_{r}}$ ${\displaystyle x_{w}}$ ${\displaystyle k+1}$

Teoría

Blum, Shub y Smale definieron las clases de complejidad P (tiempo polinomial) y NP (tiempo polinomial no determinista) en el modelo BSS. Aquí, NP se define añadiendo una entrada cuantificada existencialmente a un problema. Proporcionan un problema que es NP-completo para la clase NP así definida: existencia de raíces de polinomios cuárticos. Esto es un análogo del teorema de Cook-Levin para números reales.

Véase también

• Complejidad y computación real
• Computadora analógica de propósito general
• Hipercomputación
• Computadora real
• Autómata cuántico finito

Referencias

1. Blum, Lenore ; Shub, Mike ; Smale, Steve (1989). "Sobre una teoría de computación y complejidad sobre los números reales: NP-completitud, funciones recursivas y máquinas universales" (PDF) . Boletín de la Sociedad Matemática Americana . 21 (1): 1–46. doi : 10.1090/S0273-0979-1989-15750-9 . Zbl  0681.03020.
2. Minsky, Marvin (1967). Computación: máquinas finitas e infinitas . Nueva Jersey: Prentice–Hall, Inc.

Lectura adicional

• Blum, Lenore ; Cucker, Felipe ; Shub, Mike ; Smale, Steve (1998). Complejidad y computación real. Springer Nueva York. doi :10.1007/978-1-4612-0701-6. ISBN 978-0-387-98281-6. S2CID  12510680 . Consultado el 23 de marzo de 2022 .
• Bürgisser, Peter (2000). Completitud y reducción en la teoría de la complejidad algebraica . Algoritmos y computación en matemáticas. Vol. 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. pp. 125–230. Zbl  1133.03001.