Алан Тьюринг показал, что число вычисляемых функций счетно; поскольку число всех функций несчетно, то подавляющее большинство функций нельзя вычислить на машине Тьюринга. Среди них находится так называемая функция остановки — по описанию программы определить произойдет ли ее нормальное завершение или нет.
Далее Тьюринг работал вместе с Алонзо Чёрчем. В диссертационной работе ‘Логические системы, основанные на ординальных числах‘ были введены гипотетические машины Тьюринга с оракулом:
‘Давайте представим, что мы обладаем некими неведомыми средствами решения [неразрешимых] теоретико-числовых задач; своего рода оракулом, как бывало прежде. Не вдаваясь в природу этого оракула, скажем только, что он не может быть машиной. С помощью оракула мы могли бы создать новый вид машины (назовем их o-машинами), одной из основных операций которой является решение данной теоретико-числовой задачи.’
Использование оракула для разрешения проблемы остановки позволило создать новый класс математических структур; вопрос соответствия этих структур реальным вычислениям не ставился. Это является хорошим примером чистой математики и исследования возможностей машины Тьюринга с оракулом продолжаются до настоящего времени.
В то же время это вдохновило более практически настроенных граждан на поиск возможности создания физического устройства, которое будет способно вычислять функции, невычислимые машиной Тьюринга. Таким образом в ход вошли представления о гипервычислениях. Следует отметить, что до настоящего времени работа в этом направлении не увенчалась практическим успехом; злые языки даже характеризуют ее как поиск вечного двигателя. Тем не менее, были предложены устройства, способные к гипервычислениям, которые формально нельзя отвергнуть. Ниже я рассмотрю так называемую бесконечно ускоряющуюся машину Тьюринга.
Далее: http://blog.rudnyi.ru/ru/2023/09/hypercomputation.html