Реальные вычисления
В теории вычислимости теория реальных вычислений бесконечной точности имеет дело с гипотетическими вычислительными машинами, использующими действительные числа . Им дано это имя, потому что они оперируют множеством действительных чисел . В рамках этой теории можно доказать такие интересные утверждения, как «Дополнение к множеству Мандельброта разрешимо лишь частично».
Эти гипотетические вычислительные машины можно рассматривать как идеализированные аналоговые компьютеры , которые работают с действительными числами, тогда как цифровые компьютеры ограничены вычислимыми числами . Их можно далее подразделить на дифференциальные и алгебраические модели (цифровые компьютеры в этом контексте следует рассматривать как топологические , по крайней мере, в той мере, в какой их работы с вычислимыми вещественными числами) . это касается [1] ). В зависимости от выбранной модели это может позволить реальным компьютерам решать проблемы, которые неразрешимы для цифровых компьютеров (например, Хавы Зигельманн могут нейронные сети иметь невычислимые действительные веса, что позволяет им вычислять нерекурсивные языки) или наоборот. ( Идеализированный аналоговый компьютер Клода Шеннона может решать только алгебраические дифференциальные уравнения, в то время как цифровой компьютер также может решать некоторые трансцендентные уравнения. Однако это сравнение не совсем справедливо, поскольку в идеализированном аналоговом компьютере Клода Шеннона вычисления выполняются немедленно; т.е. вычисления делается в реальном времени, модель Шеннона можно адаптировать для решения этой проблемы.) [2]
Канонической моделью вычислений над действительными числами является машина Блюма – Шуба – Смейла (BSS).
Если бы реальные вычисления были физически осуществимы, их можно было бы использовать для решения NP-полных задач и даже #P -полных задач за полиномиальное время . Действительные числа неограниченной точности в физической вселенной запрещены голографическим принципом и границей Бекенштейна . [3]
См. также
[ редактировать ]- Гипервычисления для других таких же мощных машин.
- Квантовый конечный автомат для обобщения на произвольные геометрические пространства.
Ссылки
[ редактировать ]- ^ Клаус Вейраух (1995). Простое введение в вычислительный анализ .
- ^ О. Бурнес; М.Л. Кампаньоло; Д. С. Граса и Э. Хейнри (июнь 2007 г.). «Полиномиальные дифференциальные уравнения вычисляют все действительные вычислимые функции на вычислимых компактных интервалах» . Журнал сложности . 23 (3): 317–335. дои : 10.1016/j.jco.2006.12.005 . hdl : 10400.1/1011 .
- ^ Скотт Ааронсон , NP-полные проблемы и физическая реальность , ACM SIGACT News, Vol. 36, № 1. (март 2005 г.), стр. 30–52.
Дальнейшее чтение
[ редактировать ]- Ленор Блюм , Фелипе Какер, Майкл Шаб и Стивен Смейл (1998). Сложность и реальные вычисления . ISBN 0-387-98281-7 .
{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) - Кампаньоло, Мануэль Ламейрас (июль 2001 г.). Вычислительная сложность вещественнозначных рекурсивных функций и аналоговых схем . Технический университет Лиссабона, Высший технический институт.
- Натшлегер, Томас, Вольфганг Маасс, Генри Маркрам. «Жидкий компьютер». Новая стратегия вычислений на временных рядах в реальном времени (PDF) .
{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) - Сигельманн, Хава (декабрь 1998 г.). Нейронные сети и аналоговые вычисления: за пределом Тьюринга . ISBN 0-8176-3949-7 .
- Сигельманн, Хава Т .; Зонтаг, Эдуардо Д. (1995). «О вычислительной мощности нейронных сетей» (PDF) . Журнал компьютерных и системных наук . 50 (1): 132–150. дои : 10.1006/jcss.1995.1013 . МР 1322637 .
 | Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее . |