Гипервычисления - Hypercomputation

Гипервычисления или вычисление супер-Тьюринга относится к модели вычислений которые могут обеспечить выходы, которые не Вычислимый по Тьюрингу. Например, машина, которая может решить проблема остановки был бы гиперкомпьютером; и тот, кто может правильно оценивать каждое утверждение в Арифметика Пеано.

В Тезис Черча – Тьюринга утверждает, что любая «вычислимая» функция, которую математик может вычислить с помощью ручки и бумаги, используя конечный набор простых алгоритмов, может быть вычислена машиной Тьюринга. Гиперкомпьютеры вычисляют функции, которые машина Тьюринга не может вычислить и которые, следовательно, не вычислимы в смысле Чёрча – Тьюринга.

Технически выход случайная машина Тьюринга невычислимо; однако большая часть литературы по гиперкомпьютерам сосредоточена на вычислении детерминированных, а не случайных невычислимых функций.

История

Вычислительная модель, выходящая за рамки машин Тьюринга, была представлена Алан Тьюринг в его докторской диссертации 1938 г. Системы логики на основе порядковых чисел.[1] В этой статье исследуются математические системы, в которых оракул был доступен, который мог вычислить одну произвольную (нерекурсивную) функцию из натуралы к натуралам. Он использовал это устройство, чтобы доказать, что даже в более мощных системах неразрешимость все еще присутствует. Машины-оракулы Тьюринга - это математические абстракции, которые физически нереализуемы.[2]

Государственное пространство

В каком-то смысле большинство функций невычислимы: есть вычислимые функции, но есть бесчисленный номер () возможных функций Супер-Тьюринга.[3]

Модели гиперкомпьютеров

Гиперкомпьютерные модели варьируются от полезных, но, вероятно, неосуществимых (таких как оригинальные машины-оракулы Тьюринга) до менее полезных генераторов случайных функций, которые более правдоподобно «реализуемы» (например, случайная машина Тьюринга ).

Гиперкомпьютеры с невычислимыми входами или компонентами черного ящика

Система даровала знание невычислимого, оракульного Постоянная Чайтина (число с бесконечной последовательностью цифр, которые кодируют решение проблемы остановки) в качестве входных данных может решить большое количество полезных неразрешимых проблем; система, предоставившая невычислимый генератор случайных чисел в качестве входных данных, может создавать случайные невычислимые функции, но обычно считается, что она не способна осмысленно решать «полезные» невычислимые функции, такие как проблема остановки. Существует неограниченное количество возможных гиперкомпьютеров различных типов, в том числе:

  • Оригинальные машины-оракулы Тьюринга, определенные Тьюрингом в 1939 году.
  • А настоящий компьютер (своего рода идеализированный аналоговый компьютер ) может выполнять гипервычисления[4] если физика допускает общие настоящий переменные (не только вычислимые вещественные числа ), и их можно использовать в некотором роде для полезных (а не случайных) вычислений. Для этого могут потребоваться довольно странные законы физики (например, измеримая физическая постоянная с пророческим значением, например Постоянная Чайтина ), и для этого потребуется способность измерять действительные физические величины с произвольной точностью, хотя стандартная физика делает такие измерения с произвольной точностью теоретически невозможными.[5]
    • Точно так же нейронная сеть, которая каким-то образом имела постоянную Чейтина, точно встроенную в ее весовую функцию, могла бы решить проблему остановки,[6] но подвержен тем же физическим трудностям, что и другие модели гипервычислений, основанные на реальных вычислениях.
  • Определенный нечеткая логика -основанные "нечеткие машины Тьюринга" могут, по определению, случайно решить проблему остановки, но только потому, что их способность решать проблему остановки косвенно предполагается в спецификации машины; это обычно рассматривается как «ошибка» в исходной спецификации машин.[7][8]
    • Точно так же предлагаемая модель, известная как справедливый недетерминизм может случайно позволить оракулу вычислять невычислимые функции, потому что некоторые такие системы, по определению, обладают способностью оракула определять отклоненные входные данные, которые «несправедливо» заставили бы подсистему работать вечно.[9][10]
  • Дмитрий Тарановский предложил финитистический Модель традиционно нефинитистских ветвей анализа, построенная вокруг машины Тьюринга, оснащенной быстрорастущей функцией в качестве своего оракула. С помощью этой и более сложных моделей он смог дать интерпретацию арифметики второго порядка. Эти модели требуют невычислимых входных данных, таких как физический процесс генерации событий, при котором интервал между событиями увеличивается с невычислимо большой скоростью.[11]
    • Точно так же одна неортодоксальная интерпретация модели неограниченный недетерминизм Постулирует по определению, что продолжительность времени, необходимого «Актеру» для урегулирования, принципиально неизвестна, и, следовательно, в рамках модели нельзя доказать, что это не занимает неисчислимо долгого периода времени.[12]

Модели "бесконечных вычислительных шагов"

Для правильной работы определенные вычисления на машинах ниже буквально требуют бесконечного, а не просто неограниченного, но конечного физического пространства и ресурсов; Напротив, с машиной Тьюринга для любого остановленного вычисления потребуется только ограниченное физическое пространство и ресурсы.

  • Машина Тьюринга, которая может полный бесконечно много шагов за конечное время, подвиг, известный как сверхзадача. Недостаточно просто иметь возможность бегать неограниченное количество шагов. Одна математическая модель - это Зенон машина (вдохновленный Парадокс Зенона ). Машина Зенона выполняет свой первый шаг вычислений (скажем) за 1 минуту, второй шаг за ½ минуты, третий шаг за ¼ минуты и т. Д. 1+½+¼+... (а геометрическая серия ) мы видим, что машина выполняет бесконечно много шагов всего за 2 минуты. Согласно Шагриру, машины Зенона вводят физические парадоксы, и их состояние логически не определено за пределами одностороннего открытого периода [0, 2), то есть не определено ровно через 2 минуты после начала вычислений.[13]
  • Кажется естественным, что возможность путешествовать во времени (существование замкнутые времяподобные кривые (CTCs)) сам по себе делает гипервычисления. Однако это не так, поскольку CTC не обеспечивает (сам по себе) неограниченного объема памяти, который потребовался бы для бесконечных вычислений. Тем не менее, существуют пространства-времени, в которых область CTC может использоваться для релятивистских гиперкомпаний.[14] Согласно статье 1992 года,[15] компьютер, работающий в Пространство-время Маламента-Хогарта или на орбите вокруг вращающегося черная дыра[16] теоретически может выполнять вычисления, отличные от Тьюринга, для наблюдателя внутри черной дыры.[17][18] Доступ к CTC может позволить быстрое решение PSPACE-полный задач, сложный класс, который, хотя и разрешим по Тьюрингу, обычно считается вычислительно трудноразрешимым.[19][20]

Квантовые модели

Некоторые ученые предполагают, что квантово-механический система, которая каким-то образом использует бесконечную суперпозицию состояний, могла бы вычислить не-вычислимая функция.[21] Это невозможно при использовании стандартного кубит -модель квантовый компьютер, потому что доказано, что обычный квантовый компьютер PSPACE-сводимый (квантовый компьютер, работающий в полиномиальное время можно моделировать на классическом компьютере, работающем в полиномиальное пространство ).[22]

«В конечном итоге правильные» системы

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

  • В середине 1960-х гг. E Mark Gold и Хилари Патнэм самостоятельно предложенные модели индуктивный вывод («предельные рекурсивные функционалы»[23] и "предикаты проб и ошибок",[24] соответственно). Эти модели позволяют использовать некоторые нерекурсивные наборы чисел или языков (включая все рекурсивно перечислимый наборы языков) быть «изученными в пределе»; тогда как, по определению, машина Тьюринга может идентифицировать только рекурсивные наборы чисел или языков. Хотя машина стабилизируется к правильному ответу на любом обучаемом наборе за некоторое конечное время, она может идентифицировать его как правильный только в том случае, если он рекурсивен; в противном случае правильность устанавливается, только если машина будет работать вечно и не будет пересматривать свой ответ. Патнэм определил эту новую интерпретацию как класс «эмпирических» предикатов, заявив: «если мы всегда« постулируем », что последний сгенерированный ответ верен, мы сделаем конечное количество ошибок, но в конечном итоге получим правильный ответ. (Обратите внимание, однако, что даже если мы получили правильный ответ (конец конечной последовательности), мы никогда не Конечно что у нас есть правильный ответ.) "[24] Л. К. Шуберт Статья 1974 г. «Итерированная предельная рекурсия и проблема минимизации программы»[25] изучили эффекты повторения предельной процедуры; это позволяет любому арифметика вычисляемый предикат. Шуберт писал: «Интуитивно итеративная ограничивающая идентификация может рассматриваться как индуктивный вывод высшего порядка, коллективно выполняемый постоянно растущим сообществом машин индуктивного вывода низшего порядка».
  • Последовательность символов вычислимый в пределе если есть конечная, возможно, не останавливающаяся программа на универсальная машина Тьюринга который постепенно выводит каждый символ последовательности. Сюда входит диадическое расширение π и всех остальных вычислимый реальный, но по-прежнему исключает все невычислимые вещественные числа. «Монотонные машины Тьюринга», традиционно используемые в размер описания теория не может редактировать свои предыдущие результаты; обобщенные машины Тьюринга, как определено Юрген Шмидхубер, может. Он определяет конструктивно описываемые последовательности символов как те, которые имеют конечную, не останавливающуюся программу, работающую на обобщенной машине Тьюринга, так что любой выходной символ в конечном итоге сходится; то есть он больше не меняется после некоторого конечного начального интервала времени. Из-за ограничений, впервые выставленных Курт Гёдель (1931), может оказаться невозможным предсказать время сходимости с помощью программы остановки, в противном случае проблема остановки могло быть решено. Шмидхубер ([26][27]) использует этот подход для определения множества формально описываемых или конструктивно вычислимых вселенных или конструктивных теории всего. Обобщенные машины Тьюринга могут в конечном итоге прийти к правильному решению проблемы остановки путем оценки Последовательность Спекера.

Анализ возможностей

Многие предложения по гиперкомпьютерам сводятся к альтернативным способам чтения оракул или функция консультации встроен в классическую машину. Другие позволяют получить доступ к более высокому уровню арифметическая иерархия. Например, сверхзадачные машины Тьюринга при обычных допущениях могли бы вычислить любой предикат в степень таблицы истинности содержащий или . Ограничивающая рекурсия, напротив, может вычислить любой предикат или функцию в соответствующем Степень Тьюринга, который, как известно, . Далее Голд показал, что ограничение частичной рекурсии позволит точно вычислить предикаты.

МодельВычислимые предикатыПримечанияСсылки
сверхзадачатт ()зависит от стороннего наблюдателя[28]
ограничение / метод проб и ошибок[23]
повторное ограничение (k раз)[25]
Машина Блюма – Шуба – Смейла.несравнимо с традиционными вычислимый реальный функции[29]
Пространство-время Маламента-ХогартаHYPзависит от структуры пространства-времени[30]
аналоговая рекуррентная нейронная сетьж - функция рекомендации, дающая веса соединения; размер ограничен временем выполнения[31][32]
бесконечное время машина ТьюрингаАрифметические квазииндуктивные множества[33]
классическая нечеткая машина Тьюрингадля любых вычислимых t-норма[8]
увеличение функции оракуладля модели с одной последовательностью; являются r.e.[11]

Критика

Мартин Дэвис в своих трудах по гиперкомпьютерам,[34][35]называет этот предмет «мифом» и предлагает контраргументы против физической реализуемости гиперкомпьютеров. Что касается его теории, он возражает против утверждений о том, что это новая область, основанная в 1990-х годах. Эта точка зрения основана на истории теории вычислимости (степени неразрешимости, избыточные функции вычислимости, действительные числа и порядковые числа), как также упоминалось выше. В своем аргументе он делает замечание, что все гипервычисления - это не более чем: "если не вычислимые входные данные разрешены, то невычислимые выходы достижимы."[36]

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

Рекомендации

  1. ^ Алан Тьюринг, 1939 г., Системы логики на основе порядковых чисел Слушания Лондонского математического общества, тома 2–45, выпуск 1, стр. 161–228.[1]
  2. ^ «Предположим, что у нас есть какие-то неопределенные средства решения теоретико-числовых задач; своего рода оракул. Мы не будем углубляться в природу этого оракула, кроме как заявить, что он не может быть машиной» ( Неразрешимый с. 167, перепечатка статьи Тьюринга Системы логики, основанные на порядковых числах)
  3. ^ Х. Кабесса; H.T. Зигельманн (апрель 2012 г.). «Вычислительная мощность интерактивных рекуррентных нейронных сетей» (PDF). Нейронные вычисления. 24 (4): 996–1019. CiteSeerX  10.1.1.411.7540. Дои:10.1162 / neco_a_00263. PMID  22295978.
  4. ^ Арнольд Шёнхаге, «О возможностях машин с произвольным доступом», в Proc. Intl. Коллоквиум по автоматам, языкам и программированию (ICALP), стр. 520–529, 1979. Источник цитирования: Скотт Ааронсон, "NP-полные проблемы и физическая реальность"[2] п. 12
  5. ^ Эндрю Ходжес. "Профессора и мозговые штурмы". Домашняя страница Алана Тьюринга. Получено 23 сентября 2011.
  6. ^ H.T. Зигельманн; E.D. Зонтаг (1994). «Аналоговые вычисления через нейронные сети». Теоретическая информатика. 131 (2): 331–360. Дои:10.1016/0304-3975(94)90178-3.
  7. ^ Biacino, L .; Герла, Г. (2002). «Нечеткая логика, преемственность и эффективность». Архив по математической логике. 41 (7): 643–667. CiteSeerX  10.1.1.2.8029. Дои:10.1007 / s001530100128. ISSN  0933-5846.
  8. ^ а б Видерманн, Иржи (2004). «Описание вычислительной мощности супер-Тьюринга и эффективности классических нечетких машин Тьюринга». Теор. Comput. Наука. 317 (1–3): 61–69. Дои:10.1016 / j.tcs.2003.12.004. Их (способность решать проблему остановки) обусловлена ​​их критерием приемлемости, в котором косвенно предполагается способность решить проблему остановки.
  9. ^ Эдит Спаан; Лин Торенвлит; Питер ван Эмде Боас (1989). «Недетерминизм, справедливость и фундаментальная аналогия». Бюллетень EATCS. 37: 186–193.
  10. ^ Орд, Тоби. «Множество форм гиперкомпьютеров». Прикладная математика и вычисления 178.1 (2006): 143–153.
  11. ^ а б Дмитрий Тарановский (17 июля 2005 г.). «Конечность и гиперкомпьютинг». Получено 26 апреля, 2011.
  12. ^ Хьюитт, Карл. «Что такое обязательство». Физическая, организационная и социальная (пересмотренная), координация, организации, учреждения и нормы в агентских системах II: AAMAS (2006).
  13. ^ Эти модели были независимо разработаны многими разными авторами, включая Герман Вейль (1927). Philosophie der Mathematik und Naturwissenschaft.; модель обсуждается в Шагрир О. (июнь 2004 г.). «Сверхзадачи, ускоряющие машины Тьюринга и невычислимость» (PDF). Теор. Comput. Наука. 317 (1–3): 105–114. Дои:10.1016 / j.tcs.2003.12.007. Архивировано из оригинал (PDF) на 2007-07-09., Петрус Х. Потгитер (июль 2006 г.). «Машины Зенона и гипервычисления». Теоретическая информатика. 358 (1): 23–33. arXiv:cs / 0412022. Дои:10.1016 / j.tcs.2005.11.040. и Винсент К. Мюллер (2011). «О возможностях гиперкомпьютерных суперзадач». Умы и машины. 21 (1): 83–96. CiteSeerX  10.1.1.225.3696. Дои:10.1007 / s11023-011-9222-6.
  14. ^ Хайнал Андрека, Иштван Немети и Гергей Секели, Замкнутые времениподобные кривые в релятивистских вычислениях Параллельный процесс. Lett. 22, 1240010 (2012).[3]
  15. ^ Хогарт, М., 1992, «Позволяет ли общая теория относительности наблюдателю увидеть вечность за конечное время?», Foundations of Physics Letters, 5, 173–181.
  16. ^ Иштван Немети; Хайнал Андрека (2006). «Могут ли общие релятивистские компьютеры преодолеть барьер Тьюринга?». Логические подходы к вычислительным барьерам, Вторая конференция по вычислимости в Европе, CiE 2006, Суонси, Великобритания, 30 июня - 5 июля 2006 г. Труды. Конспект лекций по информатике. 3988. Springer. Дои:10.1007/11780342. ISBN  978-3-540-35466-6.
  17. ^ Этеси, Г., Немети, И., 2002 «Вычисления, не связанные с Тьюрингом, с использованием пространства-времени Маламента-Хогарта», Int.J. Theor.Phys. 41 (2002) 341–370, Вычисления без Тьюринга в пространстве-времени Маламента-Хогарта:.
  18. ^ Эрман, Дж. И Нортон, Дж., 1993, «Навсегда - день: сверхзадачи в пространстве-времени Питовски и Маламента-Хогарта», Философия науки, 5, 22–42.
  19. ^ Тодд А. Брун, Компьютеры с замкнутыми времяподобными кривыми могут решать сложные задачи, Найдено.Phys.Lett. 16 (2003) 245–253.[4]
  20. ^ С. Ааронсон и Дж. Уотроус. Замкнутые времяподобные кривые делают квантовые и классические вычисления эквивалентными [5]
  21. ^ На этот счет были некоторые претензии; увидеть Тянь Киеу (2003). «Квантовый алгоритм десятой проблемы Гильберта». Int. J. Theor. Phys. 42 (7): 1461–1478. arXiv:Quant-ph / 0110136. Дои:10.1023 / А: 1025780028846. или М. Зиглер (2005). «Вычислительная мощность бесконечного квантового параллелизма». Международный журнал теоретической физики. 44 (11): 2059–2071. arXiv:Quant-ph / 0410141. Bibcode:2005IJTP ... 44.2059Z. Дои:10.1007 / s10773-005-8984-0. и последующая литература. Для ответа см. Уоррен Д. Смит (2006). «Три контрпримера, опровергающие план Кье по« квантовому адиабатическому гипервычислению »; и некоторые невычислимые квантово-механические задачи». Прикладная математика и вычисления. 178 (1): 184–193. Дои:10.1016 / j.amc.2005.09.078..
  22. ^ Бернштейн и Вазирани, Квантовая теория сложности, SIAM Журнал по вычислениям, 26(5):1411–1473, 1997. [6]
  23. ^ а б Э. М. Голд (1965). «Предельная рекурсия». Журнал символической логики. 30 (1): 28–48. Дои:10.2307/2270580. JSTOR  2270580., Э. Марк Голд (1967). «Определение языка в пределе». Информация и контроль. 10 (5): 447–474. Дои:10.1016 / S0019-9958 (67) 91165-5.
  24. ^ а б Хилари Патнэм (1965). «Предикаты проб и ошибок и решение проблемы Мостовски». Журнал символической логики. 30 (1): 49–57. Дои:10.2307/2270581. JSTOR  2270581.
  25. ^ а б Л. К. Шуберт (июль 1974 г.). «Итерированная предельная рекурсия и проблема минимизации программы». Журнал ACM. 21 (3): 436–445. Дои:10.1145/321832.321841.
  26. ^ Юрген Шмидхубер (2000). «Алгоритмические теории всего». Разделы в: Иерархии обобщенных колмогоровских сложностей и неисчислимые универсальные меры, вычислимые в пределе. Международный журнал основ информатики 13 (4): 587-612. Раздел 6 в: The Speed ​​Prior: Новая мера простоты, дающая почти оптимальные вычислимые прогнозы. В J. Kivinen и R.H.Sloan, Editors, Proceedings of the 15th Annual Conference on Computational Learning Theory (COLT), Sydney, Australia, Lecture Notes in Artificial Intelligence, Pages 216–228. Спрингер, . 13 (4): 1–5. arXiv:Quant-ph / 0011122. Bibcode:2000quant.ph.11122S.
  27. ^ Дж. Шмидхубер (2002). «Иерархии обобщенных колмогоровских сложностей и неисчислимые универсальные меры, вычислимые в пределе». Международный журнал основ информатики. 13 (4): 587–612. Bibcode:2000quant.ph.11122S. Дои:10.1142 / S0129054102001291.
  28. ^ Петрус Х. Потгитер (июль 2006 г.). «Машины Зенона и гипервычисления». Теоретическая информатика. 358 (1): 23–33. arXiv:cs / 0412022. Дои:10.1016 / j.tcs.2005.11.040.
  29. ^ Ленор Блюм, Фелипе Кукер, Майкл Шуб и Стивен Смейл (1998). Сложность и реальные вычисления. ISBN  978-0-387-98281-6.CS1 maint: несколько имен: список авторов (ссылка на сайт)
  30. ^ П.Д. Welch (2008). «Степень вычислений в пространстве-времени Маламента-Хогарта». Британский журнал философии науки. 59 (4): 659–674. arXiv:gr-qc / 0609035. Дои:10.1093 / bjps / axn031.
  31. ^ H.T. Зигельманн (апрель 1995 г.). «Вычисления за пределами предела Тьюринга» (PDF). Наука. 268 (5210): 545–548. Bibcode:1995Sci ... 268..545S. Дои:10.1126 / science.268.5210.545. PMID  17756722.
  32. ^ Хава Зигельманн; Эдуардо Зонтаг (1994). «Аналоговые вычисления через нейронные сети». Теоретическая информатика. 131 (2): 331–360. Дои:10.1016/0304-3975(94)90178-3.
  33. ^ П.Д. Welch (2009). «Характеристики дискретных моделей машины Тьюринга с трансфинитным временем: времена остановки, времена стабилизации и теоремы нормальной формы». Теоретическая информатика. 410 (4–5): 426–442. Дои:10.1016 / j.tcs.2008.09.050.
  34. ^ Дэвис, Мартин (2006). «Почему нет такой дисциплины, как гипервычисления». Прикладная математика и вычисления. 178 (1): 4–7. Дои:10.1016 / j.amc.2005.09.066.
  35. ^ Дэвис, Мартин (2004). «Миф о гиперкомпьютерах». Алан Тьюринг: жизнь и наследие великого мыслителя. Springer.
  36. ^ Мартин Дэвис (январь 2003 г.). «Миф о гиперкомпьютерах». В Александре Шлапентох (ред.). Мини-практикум: Десятая проблема Гильберта, гипотеза Мазура и последовательности делимости (PDF). Отчет МФО. 3. Mathematisches Forschungsinstitut Oberwolfach. п. 2.

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

внешняя ссылка