Машина Блюма–Шуба–Смейла

В теории вычислений машина Блюма–Шуба–Смейла , или машина BSS , — это модель вычислений, введенная Ленор Блюм , Майклом Шубом и Стивеном Смейлом , предназначенная для описания вычислений над действительными числами . ^[1] По сути, машина BSS — это машина произвольного доступа с регистрами, которые могут хранить произвольные действительные числа и которые могут вычислять рациональные функции над действительными числами за один временной шаг. Она тесно связана с моделью Real RAM .

Машины BSS более мощны, чем машины Тьюринга , поскольку последние по определению ограничены конечным набором символов. ^[2] Машина Тьюринга может представлять счетное множество (например, рациональные числа) строками символов, но это не распространяется на несчетные действительные числа.

Машина BSS M задается списком инструкций (будет описана ниже), индексированных . Конфигурация M представляет собой кортеж , где — индекс инструкции, которая должна быть выполнена следующей, и — регистры, содержащие неотрицательные целые числа, и — список действительных чисел, все из которых, кроме конечного числа, равны нулю. Считается, что список содержит содержимое всех регистров M . Вычисление начинается с конфигурации и заканчивается, когда ; окончательное содержимое называется выходом машины.${\displaystyle Я}$${\displaystyle N+1}$${\displaystyle 0,1,\точки ,N}$${\displaystyle (к,р,ш,х)}$${\displaystyle к}$${\displaystyle r}$${\displaystyle w}$${\displaystyle x=(x_{0},x_{1},\ldots )}$${\displaystyle x}$${\displaystyle (0,0,0,x)}$${\displaystyle к=Н}$${\displaystyle x}$

Инструкции M могут быть следующих типов:

• Вычисление : выполняется подстановка , где — произвольная рациональная функция (частное двух полиномиальных функций с произвольными действительными коэффициентами); регистры и могут быть изменены либо с помощью, либо и аналогично для . Следующая инструкция — .${\displaystyle x_{0}:=g_{k}(x)}$${\displaystyle g_{k}}$${\displaystyle r}$${\displaystyle w}$${\displaystyle r:=0}$${\displaystyle r:=r+1}$${\displaystyle w}$${\displaystyle к+1}$
• Ветвь ( )${\displaystyle л}$ : если то перейти ; иначе перейти .${\displaystyle x_{0}\geq 0}$${\displaystyle л}$${\displaystyle к+1}$
• Копировать ( ): содержимое регистра «чтения» копируется в регистр «записи» ; следующая инструкция — .${\displaystyle x_{r},x_{w}}$${\displaystyle x_{r}}$${\displaystyle x_{w}}$${\displaystyle к+1}$

Блюм, Шуб и Смейл определили классы сложности P (полиномиальное время) и NP (недетерминированное полиномиальное время) в модели BSS. Здесь NP определяется путем добавления к проблеме экзистенциально-квантифицированного входа. Они дают задачу, которая является NP-полной для класса NP, определенного таким образом: существование корней полиномов четвертой степени. Это аналог теоремы Кука-Левина для действительных чисел.

• Сложность и реальные вычисления
• Аналоговый компьютер общего назначения
• Гиперкомпьютер
• Настоящий компьютер
• Квантовый конечный автомат

• Blum, Lenore ; Cucker, Felipe ; Shub, Mike ; Smale, Steve (1998). Сложность и реальные вычисления. Springer New York. doi :10.1007/978-1-4612-0701-6. ISBN 978-0-387-98281-6. S2CID  12510680 . Получено 23 марта 2022 г. .
• Бюргиссер, Петер (2000). Полнота и редукция в теории алгебраической сложности . Алгоритмы и вычисления в математике. Том 7. Берлин: Springer-Verlag . ISBN 3-540-66752-0. Збл  0948.68082.
• Грэдель, Э. (2007). «Теория конечных моделей и описательная сложность». Теория конечных моделей и ее приложения (PDF) . Springer-Verlag. стр. 125–230. Zbl  1133.03001.