WikiDer > Реальные вычисления
В теория вычислимости, теория реальное вычисление имеет дело с гипотетическими вычислительными машинами, использующими бесконечную точность действительные числа. Им дано это название, потому что они работают на множестве действительные числа. В рамках этой теории можно доказать такие интересные утверждения, как «Дополнение Набор Мандельброта разрешима только частично ".
Эти гипотетические вычислительные машины можно рассматривать как идеализированные. аналоговые компьютеры которые работают с действительными числами, тогда как цифровые компьютеры ограничены вычислимые числа. В дальнейшем они могут быть подразделены на дифференциал и алгебраический модели (цифровые компьютеры в этом контексте следует рассматривать как топологический, по крайней мере, поскольку они работают на вычислимые вещественные числа обеспокоен[1]). В зависимости от выбранной модели это может позволить реальным компьютерам решать проблемы, неразрывно связанные с цифровыми компьютерами (например, Хава Зигельманнс нейронные сети могут иметь невычислимые действительные веса, что позволяет им вычислять нерекурсивные языки.) или наоборот. (Клод ШеннонИдеализированный аналоговый компьютер может решать только алгебраические дифференциальные уравнения, в то время как цифровой компьютер может также решать некоторые трансцендентные уравнения. Однако это сравнение не совсем справедливо, поскольку в Клод Шенноннемедленно выполняются идеализированные аналоговые компьютерные вычисления; т.е. вычисление выполняется в реальном времени. Модель Шеннона может быть адаптирована для решения этой проблемы.)[2]
Каноническая модель вычислений над вещественными числами: Машина Блюма – Шуба – Смейла. (BSS).
Если бы реальные вычисления были физически осуществимы, их можно было бы использовать для решения НП-полный проблемы, и даже #П-полные задачи, в полиномиальное время. Действительные числа неограниченной точности в физической вселенной запрещены голографический принцип и Бекенштейн связан.[3]
Смотрите также
- Гипервычисления, для других таких мощных машин.
использованная литература
- ^ Клаус Вейрах (1995). Простое введение в вычислимый анализ.
- ^ О. Борнез; М. Л. Кампаньоло; Д. С. Граса и Э. Хайнри (июнь 2007 г.). «Полиномиальные дифференциальные уравнения вычисляют все действительные вычислимые функции на вычислимых компактных интервалах». Журнал сложности. 23 (3): 317–335. Дои:10.1016 / j.jco.2006.12.005.
- ^ Скотт Ааронсон, NP-полные проблемы и физическая реальность, ACM SIGACT Новости, Vol. 36, № 1. (март 2005 г.), стр. 30–52.
дальнейшее чтение
- Ленор Блюм, Фелипе Кукер, Майкл Шуб и Стивен Смейл (1998). Сложность и реальные вычисления. ISBN 0-387-98281-7.CS1 maint: несколько имен: список авторов (ссылка на сайт)
- Кампаньоло, Мануэль Ламейрас (июль 2001 г.). Вычислительная сложность вещественнозначных рекурсивных функций и аналоговых схем. Universidade Técnica de Lisboa, Instituto Superior Técnico.
- Натшлегер, Томас, Вольфганг Маасс, Генри Маркрам. «Жидкий компьютер» Новая стратегия вычислений в реальном времени на временных рядах (PDF).CS1 maint: несколько имен: список авторов (ссылка на сайт)
- Зигельманн, Хава (Декабрь 1998 г.). Нейронные сети и аналоговые вычисления: за пределом Тьюринга. ISBN 0-8176-3949-7.
- Зигельманн, Хава и Зонтаг, Эдуардо Д. О вычислительной мощности нейронных сетей.[постоянная мертвая ссылка]
 | Этот Информатика статья - это заглушка. Вы можете помочь Википедии расширяя это. |