В теории вычислимости , теория реального вычисления сделок с гипотетическими вычислительными машинами , использующих бесконечномерной точностью действительных чисел . Им дано это название, потому что они работают с множеством действительных чисел . В рамках этой теории можно доказать такие интересные утверждения, как «Дополнение множества Мандельброта разрешимо только частично».
Эти гипотетические вычислительные машины можно рассматривать как идеализированные аналоговые компьютеры, которые работают с действительными числами, тогда как цифровые компьютеры ограничены вычислимыми числами . Они могут быть разделены на дифференциальные и алгебраических модели (цифровые вычислительные машины, в этом контексте следует рассматривать как топологические , по крайней мере постольку , поскольку их действие на вычислимых реалах касаются [1] ). В зависимости от выбранной модели, это может позволить реальных компьютеров для решения проблем , которые являются неразрывной на цифровых компьютерах (например, Хава Сиегелманн «s нейронных сетеймогут иметь невычислимые действительные веса, что позволяет им вычислять нерекурсивные языки.) или наоборот. ( Идеализированный аналоговый компьютер Клода Шеннона может решать только алгебраические дифференциальные уравнения, в то время как цифровой компьютер может также решать некоторые трансцендентные уравнения. Однако это сравнение не совсем справедливо, поскольку в идеализированном аналоговом компьютере Клода Шеннона вычисления выполняются немедленно, т.е. выполняется в режиме реального времени. Модель Шеннона может быть адаптирована для решения этой проблемы.) [2]
Канонической моделью вычислений над вещественными числами является машина Блюма – Шуба – Смейла (BSS).
Если бы реальные вычисления были физически осуществимы, их можно было бы использовать для решения NP-полных задач и даже # P -полных задач за полиномиальное время . Действительные числа неограниченной точности в физической вселенной запрещены голографическим принципом и границей Бекенштейна . [3]
См. Также [ править ]
- Гипервычисления для других таких мощных машин.
Ссылки [ править ]
- ^ Клаус Weihrauch (1995). Простое введение в вычислимый анализ .
- ^ О. Bournez; ML Campagnolo; DS Graça и E. Hainry (июнь 2007 г.). «Полиномиальные дифференциальные уравнения вычисляют все действительные вычислимые функции на вычислимых компактных интервалах» . Журнал сложности . 23 (3): 317–335. DOI : 10.1016 / j.jco.2006.12.005 .
- ^ Скотт Ааронсон , NP-полные проблемы и физическая реальность , ACM SIGACT News, Vol. 36, № 1. (март 2005 г.), стр. 30–52.
Дальнейшее чтение [ править ]
- Ленор Блюм , Фелипе Кукер, Майкл Шуб и Стивен Смейл (1998). Сложность и реальные вычисления . ISBN 0-387-98281-7.CS1 maint: несколько имен: список авторов ( ссылка )
- Кампаньоло, Мануэль Ламейрас (июль 2001 г.). Вычислительная сложность вещественнозначных рекурсивных функций и аналоговых схем . Технический университет Лиссабона, Высший технический институт.
- Натшлегер, Томас, Вольфганг Маасс, Генри Маркрам. «Жидкий компьютер» Новая стратегия вычислений в реальном времени для временных рядов (PDF) .CS1 maint: несколько имен: список авторов ( ссылка )
- Зигельманн, Хава (декабрь 1998 г.). Нейронные сети и аналоговые вычисления: за пределом Тьюринга . ISBN 0-8176-3949-7. CS1 maint: обескураженный параметр ( ссылка )
- Зигельманн, Хава и Зонтаг, Эдуардо Д. Вычислительная мощность нейронных сетей .[ постоянная мертвая ссылка ]
