Máquina Blum–Shub–Smale

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, cuyo objetivo es describir los cálculos sobre números reales. En esencia, una máquina BSS es una máquina de acceso aleatorio con registros que pueden almacenar cualquier número real y 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, ya que estas últimas, por definición, están restringidas a un conjunto finito de símbolos. Una máquina de Turing puede representar un conjunto numerable (como los números racionales) mediante cadenas de símbolos, pero esto no se extiende a los números reales incontables.

Una máquina BSS M se da por una lista ${\displaystyle I}$ de ${\displaystyle N+1}$ instrucciones (que se describen a continuación), indexadas ${\displaystyle 0,1,\dotsN}$. Una configuración de M es un tuple ${\displaystyle (k,r,w,x)}$, donde ${\displaystyle k}$ es el índice de la instrucción a ejecutar después, ${\displaystyle r}$ y ${\displaystyle w}$ son registros que contienen enteros no negativos, y ${\displaystyle x=(x_{0},x_{1},\ldots)}$ es una lista de números reales, con todos pero finitamente muchos siendo cero. La lista ${\displaystyle x}$ se piensa que contiene el contenido de todos los registros de M. El cálculo comienza con la configuración ${\displaystyle (0,0,0,x)}$ y termina cada vez ${\displaystyle K=N}$; el contenido final de ${\displaystyle x}$ se dice que es la salida de la máquina.

Las instrucciones de M pueden ser de los siguientes tipos:

• Computation: una sustitución ${\displaystyle x_{0}:=g_{k}(x)}$ se realiza, donde ${\displaystyle g_{k}$ es una función racional arbitraria (un cociente de dos funciones polinómicas con coeficientes reales arbitrarios); registros ${\displaystyle r}$ y ${\displaystyle w}$ puede ser cambiado, ya sea por ${\displaystyle r:=0}$ o ${\displaystyle r:=r+1}$ y de manera similar para ${\displaystyle w}$. La siguiente instrucción es ${\displaystyle k+1}$.
• Branch(Subdivisión)${\displaystyle l}$)Si ${\displaystyle x_{0}\gq 0}$ entonces Goto ${\displaystyle l}$; más Goto ${\displaystyle k+1}$.
• Copiado()${\displaystyle x_{r},x_{w}$): el contenido del registro "leer" ${\displaystyle x_{r}}$ es copiado en el registro "escrito" ${\displaystyle #$; la siguiente instrucción es ${\displaystyle k+1}$.

Blum, Shub y Smale definieron las clases de complejidad P (tiempo polinomial) y NP (tiempo polinomial no determinista) en el modelo BSS. En este caso, NP se define añadiendo una entrada cuantificada existencialmente a un problema. Presentan un problema NP-completo para la clase NP así definida: la existencia de raíces de polinomios de cuarto grado. Esto es análogo al Teorema de Cook-Levin para números reales.

• Complejidad y Computación Real
• Computación analógica de propósito general
• Hipercomputación
• Computación real
• autómata finita cuántica

• Blum, Lenore; Cucker, Felipe; Shub, Mike; Smale, Steve (1998). Complejidad y Computación Real. Springer New York. doi:10.1007/978-1-4612-0701-6. ISBN 978-0-387-98281-6. S2CID 12510680. Retrieved 23 de marzo 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 modelo finita y complejidad descriptiva". Teoría modelo finita y sus aplicaciones (PDF). Springer-Verlag. pp. 125–230. ZBL 1133.03001.