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

Модель вычисления действительных чисел

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

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

Определение

Машина BSS M задается списком инструкций (будет описана ниже), индексированных . Конфигурация M представляет собой кортеж , где — индекс инструкции, которая должна быть выполнена следующей, и — регистры, содержащие неотрицательные целые числа, и — список действительных чисел, все из которых, кроме конечного числа, равны нулю. Считается, что список содержит содержимое всех регистров M . Вычисление начинается с конфигурации и заканчивается, когда ; окончательное содержимое называется выходом машины. ${\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}$

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

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

Теория

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

Смотрите также

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

Ссылки

1. Блюм, Ленор ; Шуб, Майк ; Смейл, Стив (1989). «О теории вычислений и сложности над действительными числами: NP-полнота, рекурсивные функции и универсальные машины» (PDF) . Бюллетень Американского математического общества . 21 (1): 1–46. doi : 10.1090/S0273-0979-1989-15750-9 . Zbl  0681.03020.
2. Минский, Марвин (1967). Вычисление: Конечные и бесконечные машины . Нью-Джерси: Prentice–Hall, Inc.

Дальнейшее чтение

• 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.