Na teoria da computação, a máquina de Blum-Shub-Smale, ou máquina BSS, é um modelo de computação introduzido por Lenore Blum, Michael Shub e Stephen Smale, destinado a descrever computações sobre os números reais. Essencialmente, uma máquina BSS é uma Máquina de acesso aleatório (RAM) com registradores que podem armazenar números reais arbitrários e que pode calcular funções racionais sobre os reais num único passo de tempo. Está intimamente relacionada com o modelo Real RAM.
As máquinas BSS são mais poderosas do que as máquinas de Turing, porque estas últimas estão, por definição, restritas a um conjunto finito de símbolos. Uma máquina de Turing pode representar um conjunto enumerável (como os números racionais) por cadeias de símbolos, mas isto não se estende aos números reais, que formam um conjunto não enumerável.
Definição Uma máquina BSS M é dada por uma lista de instruções (a serem descritas abaixo), indexadas por . Uma configuração de M é um tuplo , onde é o índice da instrução a ser executada a seguir, e são registradores que contêm números inteiros não negativos, e é uma lista de números reais, onde quase todos os elementos (com um número finito de exceções) são zero. Pensa-se na lista como contendo os conteúdos de todos os registradores de M. A computação começa com a configuração e termina sempre que ; diz-se que o conteúdo final de é a saída da máquina.
As instruções de M podem ser dos seguintes tipos: Computação: uma substituição é executada, onde é uma função racional arbitrária (um quociente de duas funções polinomiais com coeficientes reais arbitrários); os registradores e podem ser alterados, seja por ou , e de forma análoga para . A instrução seguinte é . Ramificação (): se então vá para ; caso contrário, vá para . Cópia (): o conteúdo do registrador de "leitura" é copiado para o registrador de "escrita" ; a instrução seguinte é .
Teoria Blum, Shub e Smale definiram as classes de complexidade P (tempo polinomial) e NP (tempo polinomial não determinístico) no modelo BSS. Aqui, NP é definido adicionando uma entrada quantificada existencialmente a um problema. Eles apresentam um problema que é NP-completo para a classe NP assim definida: a existência de raízes de polinómios quárticos. Isto é um análogo do Teorema de Cook-Levin para os números reais.
Ver também Computador analógico de uso geral Hipercomputação Computador real Autómato finito quântico
Referências
Leitura adicional
Categoria:Modelos de computação