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

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

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

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

История

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

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

В некотором смысле большинство функций невычислимы: существуют $\aleph _{0}$ вычислимых функций, но их несчетное количество ( $2^{\aleph _{0}}$) возможных супер-Тьюринговых функций.

Модели

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

Невычислимые входные данные или компоненты «черного ящика»

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

• Оригинальные машины-оракулы Тьюринга, определенные Тьюрингом в 1939 году.
• Настоящий компьютер (своего рода идеализированный аналоговый компьютер ) может выполнять гипервычисления. если физика допускает общие действительные переменные (а не только вычислимые действительные числа ), и они каким-то образом «пригодны» для полезных (а не случайных) вычислений. Для этого могут потребоваться довольно причудливые законы физики (например, измеримая физическая константа с пророческим значением, такая как константа Чайтина ) и способность измерять реальную физическую величину с произвольной точностью, хотя стандартная физика делает такие произвольные. -точные измерения теоретически невозможны.
  • Точно так же нейронная сеть, в весовую функцию которой каким-то образом встроена константа Чайтина, сможет решить проблему остановки: но сталкивается с теми же физическими трудностями, что и другие модели гипервычислений, основанные на реальных вычислениях.
• Некоторые «нечеткие машины Тьюринга», основанные на нечеткой логике , по определению могут случайно решить проблему остановки, но только потому, что их способность решать проблему остановки косвенно предполагается в спецификации машины; это обычно рассматривается как «ошибка» в исходной спецификации машин.
  • Аналогичным образом, предлагаемая модель, известная как справедливый недетерминизм , может случайно допустить пророческое вычисление невычислимых функций, поскольку некоторые такие системы по определению обладают пророческой способностью идентифицировать отклоненные входные данные, которые «несправедливо» заставят подсистему работать вечно.
• Дмитрий Тарановский предложил финитистскую модель традиционно нефинитистских разделов анализа, построенную вокруг машины Тьюринга, оснащенной быстро растущей функцией оракула. С помощью этой и более сложных моделей он смог дать интерпретацию арифметики второго порядка. Эти модели требуют невычислимых входных данных, таких как физический процесс генерации событий, при котором интервал между событиями растет с невычислимо большой скоростью.
  • Аналогичным образом, одна неортодоксальная интерпретация модели неограниченного недетерминизма по определению утверждает, что продолжительность времени, необходимая «актору» для урегулирования, фундаментально непознаваема, и поэтому в рамках модели нельзя доказать, что для этого не требуется неисчислимо длительный период времени.

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

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

Машина Тьюринга, которая может выполнить бесконечное количество шагов за конечное время — подвиг, известный как суперзадача . Просто уметь пробежать неограниченное количество шагов недостаточно. Одной из математических моделей является машина Зенона (вдохновленная парадоксом Зенона ). Машина Зенона выполняет свой первый шаг вычислений (скажем) за 1 минуту, второй шаг за ½ минуты, третий шаг за ¼ минуты и т. д. Суммируя 1 + ½ + ¼ + ... ( геометрическую прогрессию ), мы видим, что машина выполняет бесконечное количество шагов всего за 2 минуты. По словам Орона Шагрира , машины Зенона создают физические парадоксы, и их состояние логически неопределенно за пределами одностороннего открытого периода [0, 2), поэтому оно не определено ровно через 2 минуты после начала вычислений.

Кажется естественным, что возможность путешествий во времени (существование замкнутых времяподобных кривых (ЗВК)) сама по себе делает возможными гипервычисления. Однако это не так, поскольку CTC не обеспечивает (сам по себе) неограниченный объем памяти, который потребовался бы для бесконечных вычислений. Тем не менее, существуют пространства-времени, в которых область CTC можно использовать для релятивистских гипервычислений. Согласно статье 1992 года, компьютер, работающий в пространстве-времени Маламента – Хогарта или на орбите вращающейся черной дыры теоретически может выполнять не-Тьюринговские вычисления для наблюдателя внутри черной дыры. Доступ к CTC может обеспечить быстрое решение PSPACE-полных задач, класса сложности, который, хотя и разрешим по Тьюрингу, обычно считается вычислительно неразрешимым.

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

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

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

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

В середине 1960-х годов Э. Марк Голд и Хилари Патнэм независимо друг от друга предложили модели индуктивного вывода («предельные рекурсивные функционалы»). и «предикаты проб и ошибок», соответственно). некоторые нерекурсивные наборы чисел или языков (включая все рекурсивно перечислимые Эти модели позволяют «изучить в пределе» наборы языков); тогда как по определению машина Тьюринга может идентифицировать только рекурсивные наборы чисел или языков. Хотя машина стабилизируется на правильном ответе на любом обучаемом множестве за некоторое конечное время, она может идентифицировать его как правильный только в том случае, если он рекурсивный; в противном случае правильность устанавливается только путем постоянного запуска машины и учета того, что она никогда не пересматривает свой ответ. Патнэм определил эту новую интерпретацию как класс «эмпирических» предикатов, заявив: «если мы всегда будем утверждать, что последний сгенерированный ответ верен, мы сделаем конечное число ошибок, но в конечном итоге получим правильный ответ. (Однако заметим, что даже если мы дошли до правильного ответа (конец конечной последовательности), мы никогда не уверены , что получили правильный ответ.)» Статья Л.К. Шуберта 1974 года «Итерированная предельная рекурсия и проблема минимизации программы» изучили эффекты итерации предельной процедуры; это позволяет любой арифметический вычислить предикат. Шуберт писал: «Интуитивно повторяемую ограничивающую идентификацию можно рассматривать как индуктивный вывод более высокого порядка, выполняемый коллективно постоянно растущим сообществом машин индуктивного вывода более низкого порядка».

Последовательность символов является вычислимой в пределе, если существует конечная, возможно, непрерывная программа на универсальной машине Тьюринга , которая постепенно выводит каждый символ последовательности. Это включает в себя двоичное разложение числа π и любого другого вычислимого числа , но при этом исключает все невычислимые числа. «Монотонные машины Тьюринга», традиционно используемые в теории размера описаний , не могут редактировать свои предыдущие результаты; Обобщенные машины Тьюринга, по определению Юргена Шмидхубера , могут. Он определяет конструктивно описываемые последовательности символов как те, которые имеют конечную, непрерывную программу, работающую на обобщенной машине Тьюринга, такую, что любой выходной символ в конечном итоге сходится; то есть он больше не меняется после некоторого конечного начального интервала времени. Из-за ограничений, впервые выявленных Куртом Гёделем (1931), может оказаться невозможным предсказать само время сходимости с помощью программы остановки, иначе проблему остановки можно было бы решить. Шмидхубер ( ) использует этот подход для определения набора формально описываемых или конструктивно вычислимых вселенных или конструктивных теорий всего . Обобщенные машины Тьюринга могут в конечном итоге прийти к правильному решению проблемы остановки путем вычисления последовательности Спекера .

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

Многие предложения по гипервычислениям представляют собой альтернативные способы чтения функций оракула или совета, встроенных в классическую машину. Другие обеспечивают доступ к более высокому уровню арифметической иерархии . Например, сверхзадачные машины Тьюринга при обычных предположениях смогут вычислить любой предикат в степени таблицы истинности, содержащий $\Sigma _{1}^{0}$ или $\Pi _{1}^{0}$. Предельная рекурсия, напротив, может вычислить любой предикат или функцию в соответствующей степени Тьюринга , которая, как известно, $\Delta _{2}^{0}$. Голд далее показал, что ограничение частичной рекурсии позволит вычислить именно $\Sigma _{2}^{0}$ предикаты.

Модель	Вычислимые предикаты	Примечания	Ссылки
сверхзадача	$\operatorname {tt} \left(\Sigma _{1}^{0},\Pi _{1}^{0}\right)$	зависит от стороннего наблюдателя
ограничение/метод проб и ошибок	$\Delta _{2}^{0}$
итерированное ограничение ( k раз)	$\Delta _{k+1}^{0}$
Машинка Блюм-Шуб-Смале		несравнимо с традиционными вычислимыми действительными функциями
Пространство-время Маламента – Хогарта	ГИП	зависит от структуры пространства-времени
аналоговая рекуррентная нейронная сеть	$\Delta _{1}^{0}[f]$	f — рекомендательная функция, задающая веса соединений; размер ограничен временем выполнения
машина Тьюринга бесконечного времени	$AQI$	Арифметические квазииндуктивные множества
классическая нечеткая машина Тьюринга	$\Sigma _{1}^{0}\cup \Pi _{1}^{0}$	для любой вычислимой t-нормы
возрастающая функция оракула	$\Delta _{1}^{1}$	для однопоследовательной модели; $\Pi _{1}^{1}$ повторно

Критика

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

См. также

• Цифровая физика
• Пределы вычислений

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

• Аун, Марио Антуан (2016). «Достижения в области трех моделей гипервычислений» (PDF) . Электронный журнал теоретической физики . 13 (36): 169–182.
• Бургин, М.С. (1983). «Индуктивные машины Тьюринга». Извещения Академии наук СССР . 270 (6): 1289–1293.
• Бургин, Марк (2005). Суперрекурсивные алгоритмы . Монографии по информатике. Спрингер. ISBN  0-387-95569-0 .
• Кокшотт, П.; Майклсон, Г. (2007). «Существуют ли новые модели вычислений? Ответ Вегнеру и Эбербаху». Компьютерный журнал . дои : 10.1093/comjnl/bxl062 .
• Купер, С.Б.; Одифредди, П. (2003). «Неисчислимость в природе» (PDF) . В Купере, Южная Каролина; Гончаров С.С. (ред.). Вычислимость и модели: перспективы Востока и Запада . Нью-Йорк, Бостон, Дордрехт, Лондон, Москва: Издательство Пленум. стр. 137–160. Архивировано из оригинала (PDF) 24 июля 2011 г. Проверено 16 июня 2011 г.
• Купер, С.Б. (2006). «Определимость как гипервычислительный эффект». Прикладная математика и вычислительная техника . 178 : 72–82. CiteSeerX   10.1.1.65.4088 . дои : 10.1016/j.amc.2005.09.072 . S2CID   1487739 .
• Коупленд, Дж. (2002). «Гиперкомпьютеры» (PDF) . Разум и машины . 12 (4): 461–502. дои : 10.1023/A:1021105915386 . S2CID   218585685 . Архивировано из оригинала (PDF) 14 марта 2016 г.
• Агар, А.; Королев, А. (2007). «Квантовые гипервычисления — шумиха или вычисления? *» (PDF) . Философия науки . 74 (3): 347–363. дои : 10.1086/521969 . S2CID   9857468 .
• Орд, Тоби (2002). «Гипервычисления: вычисления больше, чем может вычислить машина Тьюринга: обзорная статья о различных формах гипервычислений». arXiv : math/0209332 .
• Пиччинини, Гуальтьеро (16 июня 2021 г.). «Вычисления в физических системах» . Стэнфордская энциклопедия философии . Проверено 31 июля 2023 г.
• Шарма, Ашиш (2022). «Вдохновленные природой алгоритмы со рандомизированной гипервычислительной перспективой». Информационные науки . 608 : 670–695. дои : 10.1016/j.ins.2022.05.020 . S2CID   248881264 .
• Стэннетт, Майк (1990). «X-машины и проблема остановки: построение супермашины Тьюринга» . Формальные аспекты вычислений . 2 (1): 331–341. дои : 10.1007/BF01888233 . S2CID   7406983 .
• Стэннетт, Майк (2006). «Дело в пользу гипервычислений» (PDF) . Прикладная математика и вычислительная техника . 178 (1): 8–24. дои : 10.1016/j.amc.2005.09.067 . Архивировано из оригинала (PDF) 4 марта 2016 г.
• Сиропулос, Апостолос (2008). Гиперкомпьютерные вычисления: вычисления за пределами барьера Церкви – Тьюринга . Спрингер. ISBN  978-0-387-30886-9 .