Реальные вычисления - Real computation

Принципиальная электрическая схема из аналоговые вычисления элемент к интегрировать заданная функция. Теория реальных вычислений исследует свойства таких устройств под идеализирующий предположение о бесконечной точности.

В теория вычислимости, теория реальное вычисление имеет дело с гипотетическими вычислительными машинами, использующими бесконечную точность действительные числа. Им дано это название, потому что они работают на множестве действительные числа. В рамках этой теории можно доказать такие интересные утверждения, как «Дополнение Набор Мандельброта разрешима только частично ".

Эти гипотетические вычислительные машины можно рассматривать как идеализированные. аналоговые компьютеры которые работают с действительными числами, тогда как цифровые компьютеры ограничены вычислимые числа. В дальнейшем они могут быть подразделены на дифференциал и алгебраический модели (цифровые компьютеры в этом контексте следует рассматривать как топологический, по крайней мере, поскольку они работают на вычислимые вещественные числа обеспокоен^[1]). В зависимости от выбранной модели это может позволить реальным компьютерам решать проблемы, неразрывно связанные с цифровыми компьютерами (например, Хава Зигельманн с нейронные сети могут иметь невычислимые действительные веса, что позволяет им вычислять нерекурсивные языки.) или наоборот. (Клод Шеннон Идеализированный аналоговый компьютер может решать только алгебраические дифференциальные уравнения, в то время как цифровой компьютер может также решать некоторые трансцендентные уравнения. Однако это сравнение не совсем справедливо, поскольку в Клод Шеннон немедленно выполняются идеализированные аналоговые компьютерные вычисления; т.е. вычисление выполняется в реальном времени. Модель Шеннона может быть адаптирована для решения этой проблемы.)^[2]

Каноническая модель вычислений над вещественными числами: Машина Блюма – Шуба – Смейла. (BSS).

Если бы реальные вычисления были физически осуществимы, их можно было бы использовать для решения НП-полный проблемы, и даже #П -полные задачи, в полиномиальное время. Действительные числа неограниченной точности в физической вселенной запрещены голографический принцип и Бекенштейн связан.^[3]

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

• Гипервычисления, для других таких мощных машин.

использованная литература

1. Клаус Вейрах (1995). Простое введение в вычислимый анализ.
2. О. Борнез; М. Л. Кампаньоло; Д. С. Граса и Э. Хайнри (июнь 2007 г.). «Полиномиальные дифференциальные уравнения вычисляют все действительные вычислимые функции на вычислимых компактных интервалах». Журнал сложности. 23 (3): 317–335. Дои:10.1016 / j.jco.2006.12.005.
3. Скотт Ааронсон, NP-полные проблемы и физическая реальность, ACM SIGACT Новости, Vol. 36, № 1. (март 2005 г.), стр. 30–52.

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

• Ленор Блюм, Фелипе Кукер, Майкл Шуб и Стивен Смейл (1998). Сложность и реальные вычисления. ISBN  0-387-98281-7.
• Кампаньоло, Мануэль Ламейрас (июль 2001 г.). Вычислительная сложность вещественнозначных рекурсивных функций и аналоговых схем. Universidade Técnica de Lisboa, Instituto Superior Técnico.
• Натшлегер, Томас, Вольфганг Маасс, Генри Маркрам. «Жидкий компьютер» Новая стратегия вычислений в реальном времени на временных рядах (PDF).
• Зигельманн, Хава (Декабрь 1998 г.). Нейронные сети и аналоговые вычисления: за пределом Тьюринга. ISBN  0-8176-3949-7.
• Зигельманн, Хава и Зонтаг, Эдуардо Д. О вычислительной мощности нейронных сетей.^{[постоянная мертвая ссылка ]}