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