Суперрекурсивный алгоритм
 | Тема этой статьи Википедии может не соответствовать общему правилу по известности . ( февраль 2024 г. ) |
 | Эта статья включает список литературы , связанную литературу или внешние ссылки , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( февраль 2023 г. ) |
В теории вычислимости суперрекурсивные алгоритмы позиционируются как обобщение гипервычислений : гипотетические алгоритмы , которые являются более мощными, то есть вычисляют больше, чем машины Тьюринга .
Этот термин был введен Марком Бургиным, чья книга «Суперрекурсивные алгоритмы» развивает их теорию и представляет несколько математических моделей.
Бургин утверждает, что суперрекурсивные алгоритмы можно использовать для опровержения тезиса Чёрча-Тьюринга . Эта точка зрения подверглась критике в математическом сообществе и не получила широкого признания.
Определение
[ редактировать ]Бургин (2005: 13) использует термин «рекурсивные алгоритмы» для алгоритмов , которые могут быть реализованы на машинах Тьюринга, и использует слово «алгоритм» в более общем смысле. Тогда суперрекурсивный класс алгоритмов — это «класс алгоритмов, в которых можно вычислять функции, не вычислимые никакой машиной Тьюринга » (Бургин 2005: 107).
Суперрекурсивные алгоритмы также связаны с алгоритмическими схемами , еще одной новой концепцией Бергина, которая является более общей, чем суперрекурсивные алгоритмы. Бургин утверждает (2005: 115), что необходимо проводить четкое различие между суперрекурсивными алгоритмами и теми алгоритмическими схемами, которые не являются алгоритмами. Согласно этому различию, некоторые типы гипервычислений достигаются с помощью суперрекурсивных алгоритмов.
Отношение к тезису Чёрча – Тьюринга
[ редактировать ]Тезис Чёрча-Тьюринга в теории рекурсии опирается на конкретное определение термина «алгоритм» . Основываясь на своих личных определениях, которые являются более общими, чем те, которые обычно используются в теории рекурсии, Бергин утверждает, что суперрекурсивные алгоритмы опровергают тезис Чёрча-Тьюринга . Кроме того, он утверждает, что доказал, что суперрекурсивные алгоритмы гипотетически могут обеспечить даже больший прирост эффективности, чем использование квантовых алгоритмов .
Интерпретация суперрекурсивных алгоритмов, предложенная Бергином, встретила сопротивление в математическом сообществе. Одним из критиков является логик Мартин Дэвис , который утверждает, что утверждения Бургина были хорошо поняты «на протяжении десятилетий». Дэвис заявляет,
- «Настоящая критика касается не математического обсуждения этих вопросов, а только вводящих в заблуждение утверждений относительно физических систем настоящего и будущего» (Дэвис 2006: 128).
Дэвис оспаривает утверждения Бергина, которые находятся на уровне арифметической иерархии можно назвать вычислимой, говоря
- «Обычно считается, что для того, чтобы результат вычислений был полезным, необходимо, по крайней мере, признать, что это действительно искомый результат». (Дэвис 2006: 128)
Ссылки
[ редактировать ]- Бургин, Марк (2005), Суперрекурсивные алгоритмы , Монографии по информатике, Springer. ISBN 0-387-95569-0
- Дэвис, Мартин (2006), « Тезис Церкви – Тьюринга: консенсус и оппозиция ». Труды, Вычислимость в Европе, 2006. Конспекты лекций по информатике, 3988, стр. 125–132.
- Питер Кугель, «Пришло время мыслить за пределами вычислительных рамок» , Сообщения ACM , том 48, выпуск 11, ноябрь 2005 г.
Внешние ссылки
[ редактировать ]- Новая парадигма вычислений . Заседание отделения ACM в Лос-Анджелесе, 1 декабря 1999 г.