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