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

Обобщение обычных алгоритмов, которые вычисляют больше, чем машины Тьюринга

В теории вычислимости суперрекурсивные алгоритмы рассматриваются как обобщение гипервычислений : гипотетические алгоритмы , которые являются более мощными, то есть вычисляют больше, чем машины Тьюринга .

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

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

Определение

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

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

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

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

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

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

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

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

Ссылки

• Бергин, Марк (2005), Суперрекурсивные алгоритмы , Монографии по информатике, Springer. ISBN  0-387-95569-0
• Дэвис, Мартин (2006), «Тезис Чёрча–Тьюринга: консенсус и оппозиция». Труды, Computability in Europe 2006. Конспект лекций по информатике, 3988 стр. 125–132
• Питер Кугель, «Пришло время мыслить вне вычислительных рамок», Communications of the ACM , том 48, выпуск 11, ноябрь 2005 г.

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

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