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

редактировать

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

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

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

СОДЕРЖАНИЕ

1 История
2 Государственное пространство
3 модели
- 3.1 Невычислимые входы или компоненты черного ящика
- 3.2 Модели «бесконечных вычислительных шагов»
- 3.3 Квантовые модели
- 3.4 «В конечном итоге правильные» системы
4 Анализ возможностей
5 Критика
6 См. Также
7 ссылки
8 Дальнейшее чтение
9 Внешние ссылки

История

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

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

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

Модели

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Критика

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

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

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

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

Марио Антуан Аун, « Достижения в трех моделях гипервычислений », (2016)
Л. Блюм, Ф. Кукер, М. Шуб, С. Смейл, Сложность и реальные вычисления, Springer-Verlag 1997. Общее развитие теории сложности для абстрактных машин, которые вычисляют действительные числа вместо битов.
Бургин, М.С. (1983) Индуктивные машины Тьюринга, Извещения АН СССР, т. 270, № 6, стр. 1289–1293.
Кейт Дуглас. Вычисление Супер-Тьюринга: анализ конкретного случая ( PDF ), диссертация магистратуры, Университет Карнеги-Меллона, 2003.
Марк Бургин (2005), Суперрекурсивные алгоритмы, Монографии по информатике, Springer. ISBN 0-387-95569-0
Кокшотт П. и Майклсон Г. Существуют ли новые модели вычислений? Ответ Вегнеру и Эбербаху, Компьютерный журнал, 2007 г.
Купер, С.Б. (2006). «Определимость как гиперкомпьютерный эффект» (PDF). Прикладная математика и вычисления. 178: 72–82. CiteSeerX 10.1.1.65.4088. DOI : 10.1016 / j.amc.2005.09.072. Архивировано из оригинального (PDF) 24 июля 2011 года. Проверено 16 июня 2011.
Купер, SB; Одифредди, П. (2003). «Невычислимость в природе» (PDF). В С. Б. Купере; С.С. Гончаров (ред.). Вычислимость и модели: перспективы Востока и Запада. Издательство Пленума, Нью-Йорк, Бостон, Дордрехт, Лондон, Москва. С. 137–160.
Коупленд, Дж. (2002) Гипервычисления, Умы и машины, т. 12, стр. 461–502.
Дэвис, Мартин (2006), « Тезис Чёрча-Тьюринга: консенсус и оппозиция ». Труды, Вычислимость в Европе, 2006. Запрошенный URL /~simon/TEACH/28000/DavisUniversal.pdf не был найден на этом сервере. Конспект лекций по информатике, 3988 с. 125–132
Агарь А., Королев А. Квантовые гипервычисления - обман или вычисление?, (2007)
Мюллер, Винсент К. (2011). «О возможностях гиперкомпьютерных суперзадач». Умы и машины. 21 (1): 83–96. CiteSeerX 10.1.1.225.3696. DOI : 10.1007 / s11023-011-9222-6.
Орд, Тоби. Гипервычисления: Вычислить больше, чем может вычислить машина Тьюринга : обзорная статья о различных формах гипервычислений.
Пиччинини, Гуальтьеро : вычисления в физических системах
Пуц, Фолькмар и Карл Свозил, Можно ли « заставить» компьютер работать со скоростью быстрее скорости света?, (2010)
Роджерс, Х. (1987) Теория рекурсивных функций и эффективной вычислимости, MIT Press, Кембридж, Массачусетс
Майк Стэннетт, Майк (1990). «Х-машины и проблема остановки: создание супер-машины Тьюринга». Формальные аспекты вычислений. 2 (1): 331–341. DOI : 10.1007 / BF01888233.
Майк Стэннетт, Случай гиперкомпьютеров, Прикладная математика и вычисления, Том 178, выпуск 1, 1 июля 2006 г., страницы 8–24, специальный выпуск о гиперкомпьютерах
Сиропулос, Апостолос (2008), Гипервычисления: Вычисления за пределами барьера Черча – Тьюринга ( предварительный просмотр ), Springer. ISBN 978-0-387-30886-9
Тьюринг, Алан (1939). «Логические системы на основе ординалов». Труды Лондонского математического общества. 45: 161–228. DOI : 10.1112 / ПНИЛИ / s2-45.1.161. ЛВП : 21,11116 / 0000-0001-91CE-3.

внешние ссылки

Сеть исследований гиперкомпьютеров