Суперрекурсивный алгоритм - Super-recursive algorithm

В теория вычислимости, суперрекурсивные алгоритмы являются обобщением обычных алгоритмы которые являются более мощными, то есть вычисляют больше, чем Машины Тьюринга. Термин был введен Марком Бургином, чья книга «Суперрекурсивные алгоритмы» развивает их теорию и представляет несколько математических моделей. Машины Тьюринга и другие математические модели обычных алгоритмов позволяют исследователям находить свойства рекурсивных алгоритмов и их вычислений. Аналогичным образом математические модели суперрекурсивных алгоритмов, таких как индуктивные машины Тьюринга, позволяют исследователям находить свойства суперрекурсивных алгоритмов и их вычислений.

Бургин, а также другие исследователи (в том числе Селим Акл, Евгений Эбербах, Питер Кугель, Ян ван Леувен, Хава Зигельманн, Питер Вегнер и Йиржи Видерманн), которые изучали различные виды суперрекурсивных алгоритмов и внесли свой вклад в теорию суперрекурсивных алгоритмов, утверждали, что суперрекурсивные алгоритмы могут использоваться для опровержения Тезис Черча-Тьюринга, но эта точка зрения подверглась критике в математическом сообществе и не получила широкого признания.

Определение

Бургин (2005: 13) использует термин рекурсивные алгоритмы за алгоритмы который может быть реализован на машинах Тьюринга, и использует слово алгоритм в более общем смысле. Затем суперрекурсивный класс алгоритмов является "классом алгоритмов, в котором можно вычислять функции, не вычисляемые никакими Машина Тьюринга "(Бургин 2005: 107).

Суперрекурсивные алгоритмы тесно связаны с гипервычисления аналогично отношениям между обычными вычислениями и обычными алгоритмами. Вычисление - это процесс, а алгоритм - это конечное конструктивное описание такого процесса. Таким образом, суперрекурсивный алгоритм определяет «вычислительный процесс (включая процессы ввода и вывода), который не может быть реализован рекурсивными алгоритмами». (Бургин 2005: 108). Более ограниченное определение требует, чтобы гипервычисления решает сверхзадача (см. Copeland 2002; Hagar, Korolev 2007).

Суперрекурсивные алгоритмы также связаны с алгоритмические схемы, которые являются более общими, чем суперрекурсивные алгоритмы. Бургин утверждает (2005: 115), что необходимо проводить четкое различие между суперрекурсивными алгоритмами и теми алгоритмическими схемами, которые не являются алгоритмами. В соответствии с этим различием некоторые типы гипервычислений получаются с помощью суперрекурсивных алгоритмов, например, индуктивных машин Тьюринга, в то время как другие типы гипервычислений управляются алгоритмическими схемами, например, машины Тьюринга с бесконечным временем. Это объясняет, как работа над суперрекурсивными алгоритмами связана с гипервычислениями и наоборот. Согласно этому аргументу, суперрекурсивные алгоритмы - это всего лишь один из способов определения гиперкомпьютерного процесса.

Примеры

Примеры суперрекурсивных алгоритмов включают (Burgin 2005: 132):

ограничивающие рекурсивные функции и ограничивающие частичные рекурсивные функции (Э.М. Голд 1965)
предикаты проб и ошибок (Хилари Патнэм, 1965)
машины индуктивного вывода (Карл Смит)
индуктивные машины Тьюринга, которые выполняют вычисления, аналогичные вычислениям Машины Тьюринга и дают свои результаты после конечного числа шагов (Марк Бургин)
предельные машины Тьюринга, которые выполняют вычисления, аналогичные вычислениям машин Тьюринга, но их конечные результаты являются пределами их промежуточных результатов (Марк Бургин)
машины проб и ошибок (Я. Хинтикка и А. Мутанен, 1998 г.)
общие машины Тьюринга (Я. Шмидхубер)
Интернет-машины (ван Леувен, Дж. и Видерманн, Дж.)
эволюционные компьютеры, которые используют ДНК для получения значения функции (Дарко Роглич)
нечеткое вычисление (Иржи Видерманн, 2004)
эволюционные машины Тьюринга (Юджин Эбербах 2005)

Примеры алгоритмических схем включают:

Машины Тьюринга с произвольными оракулами (Алан Тьюринг)
Трансрекурсивные операторы (Бородянский и Бургин)
машины, которые вычисляют с действительными числами (Л. Блюм, Ф. Кукер, М. Шуб, С. Смейл, 1998 г.)
нейронные сети на основе реальных чисел (Хава Зигельманн, 1999)

Примеры практических суперрекурсивные алгоритмы, см. книгу Бургина.

Индуктивные машины Тьюринга

Индуктивные машины Тьюринга реализовать важный класс суперрекурсивных алгоритмов. Индуктивная машина Тьюринга - это определенный список четко определенных инструкций для выполнения задачи, которая при задании начального состояния будет проходить через четко определенную серию последовательных состояний, в конечном итоге давая окончательный результат. Разница между индуктивной машиной Тьюринга и обычной Машина Тьюринга заключается в том, что обычная машина Тьюринга должна остановиться, когда она получила свой результат, тогда как в некоторых случаях индуктивная машина Тьюринга может продолжать вычисления после получения результата, не останавливаясь. Клини по имени назвал процедуры, которые могут выполняться бесконечно, не останавливаясь. процедура или алгоритм расчета (Клини 1952: 137). Клини также потребовал, чтобы такой алгоритм в конечном итоге обнаружил «какой-то объект» (Kleene 1952: 137). Бургин утверждает, что этому условию удовлетворяют индуктивные машины Тьюринга, поскольку их результаты отображаются после конечного числа шагов. Причина, по которой индуктивные машины Тьюринга не могут быть проинструктированы останавливаться, когда их конечный результат получается, заключается в том, что в некоторых случаях индуктивные машины Тьюринга могут не знать, на каком этапе был получен результат.

Простые индуктивные машины Тьюринга эквивалентны другим моделям вычислений, таким как общие машины Тьюринга Шмидхубера, предикаты проб и ошибок Хилари Патнэм, ограничивающие частично рекурсивные функции Голда и машины проб и ошибок Хинтикки и Мутанена (1998). Более совершенные индуктивные машины Тьюринга намного мощнее. Существуют иерархии индуктивных машин Тьюринга, которые могут определять принадлежность к произвольным множествам арифметическая иерархия (Бургин 2005). По сравнению с другими эквивалентными моделями вычислений, простые индуктивные машины Тьюринга и общие машины Тьюринга дают прямые конструкции вычислительных автоматов, которые полностью основаны на физических машинах. Напротив, предикаты методом проб и ошибок, ограничивающие рекурсивные функции и ограничивающие частично рекурсивные функции представляют только синтаксические системы символов с формальными правилами для их манипуляции. Простые индуктивные машины Тьюринга и общие машины Тьюринга связаны с ограничением частично рекурсивных функций и предикатов методом проб и ошибок, поскольку машины Тьюринга связаны с частично рекурсивными функциями и лямбда-исчислением.

Непрерывные вычисления индуктивных машин Тьюринга не следует путать с вычислениями в бесконечном времени (см., Например, Potgieter 2006). Во-первых, некоторые вычисления индуктивных машин Тьюринга останавливаются. Как и в случае с обычными машинами Тьюринга, некоторые вычисления с остановкой дают результат, а другие - нет. Даже если она не останавливается, индукционная машина Тьюринга время от времени производит выходные данные. Если этот результат перестает изменяться, он считается результатом вычисления.

Есть два основных различия между обычными машинами Тьюринга и простыми индуктивными машинами Тьюринга. Первое отличие состоит в том, что даже простые индуктивные машины Тьюринга могут делать гораздо больше, чем обычные машины Тьюринга. Второе отличие состоит в том, что обычная машина Тьюринга всегда будет определять (переходя в конечное состояние), когда будет получен результат, в то время как простая индуктивная машина Тьюринга в некоторых случаях (например, когда «вычисляет» что-то, что не может быть вычислено с помощью обычная машина Тьюринга), не сможет сделать это определение.

Обобщенные машины Тьюринга Шмидхубера

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

Связь с тезисом Чёрча – Тьюринга

Тезис Черча – Тьюринга в теории рекурсии опирается на конкретное определение термина алгоритм. Основываясь на определениях, которые являются более общими, чем то, которое обычно используется в теории рекурсии, Бургин утверждает, что суперрекурсивные алгоритмы, такие как индуктивные машины Тьюринга опровергнуть Тезис Черча – Тьюринга. Кроме того, он доказывает, что суперрекурсивные алгоритмы теоретически могут обеспечить даже больший прирост эффективности, чем использование квантовые алгоритмы.

Интерпретация Бургином суперрекурсивных алгоритмов встретила сопротивление в математическом сообществе. Один критик - логик Мартин Дэвис, который утверждает, что утверждения Бургина были хорошо поняты "в течение десятилетий". Дэвис заявляет:

«Настоящая критика касается не математического обсуждения этих вопросов, а только вводящих в заблуждение утверждений относительно физических систем настоящего и будущего» (Davis 2006: 128)

Дэвис оспаривает утверждения Бургина, которые устанавливают уровень ${ displaystyle Delta _ {2} ^ {0}}$ из арифметическая иерархия можно назвать вычислимым, говоря

«Обычно понимается, что для того, чтобы результат вычислений был полезным, нужно уметь хотя бы признать, что это действительно искомый результат». (Дэвис 2006: 128)

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

Интерактивные вычисления

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

Акл С.Г. Три контрпримера, чтобы развеять миф об универсальном компьютере. Письма параллельной обработки, Vol. 16, No. 3, сентябрь 2006 г., стр. 381 - 403.
Акл, С.Г., Миф об универсальных вычислениях, в: Parallel Numerics, Trobec, R., Zinterhof, P., Vajtersic, M., and Uhl, A., Eds., Part 2, Системы и моделирование, Зальцбургский университет, Зальцбург, Австрия, и Институт Йозефа Стефана, Любляна, Словения, 2005 г., стр. 211 - 236
Angluin, D., and Smith, C.H. (1983) Индуктивный вывод: теория и методы, Comput. Обзоры, т. 15, вып. 3. С. 237–269.
Апситис, К., Арикава, С., Фрейвальдс, Р., Хироватари, Э., и Смит, К. Х. (1999) Об индуктивном выводе рекурсивных действительных функций, Теоретическая информатика, 219(1-2): 3—17
Бодди, М., Дин, Т. 1989. "Решение задач планирования, зависящих от времени". Технический отчет: CS-89-03, Брауновский университет
Бургин, М. "Алгоритмическая сложность рекурсивных и индуктивных алгоритмов", Теоретическая информатика, т. 317, № 1/3, 2004 г., стр. 31–60
Бургин М. и Клингер А. Опыт, поколения и ограничения в машинном обучении. Теоретическая информатика, т. 317, № 1/3, 2004 г., стр. 71–91
Эбербах, Э., Вегнер, П., «За пределами машин Тьюринга», Бюллетень Европейская ассоциация теоретической информатики (Бюллетень EATCS), 81, октябрь 2003 г., 279-304
С. Зильберштейн, Использование алгоритмов в любое время в интеллектуальных системах, "AI Magazine", 17 (3): 73-83, 1996

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

Новая парадигма вычислений. Встреча представителей ACM в Лос-Анджелесе, 1 декабря 1999 г.
Алгоритм в любое время из FOLDOC