Рекурсивные функции и регистровые машины

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

Definition

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

Scope

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

Core questions

• Как можно определить вычислимые функции арифметически без какой-либо машины?
• Почему неограниченная минимизация необходима помимо примитивной рекурсии?
• Как простые регистровые машины достигают полной вычислительной мощности?
• Почему эти арифметические и машинные модели совпадают с машинами Тьюринга?

Key theories

Эквивалентность с вычислимостью по Тьюрингу

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

За пределами примитивной рекурсии

Функция Аккермана является тотальной и вычислимой, но растет слишком быстро, чтобы быть примитивно-рекурсивной, показывая, что неограниченный поиск необходим и что примитивно-рекурсивные функции являются собственным подклассом вычислимых функций.

Универсальность регистровых машин

Минский показал, что машина всего с двумя счетчиками и операциями инкремента, декремента и проверки на ноль уже является тьюринг-полной, что является экстремальной демонстрацией того, как мало структуры требуется для полной вычислительной мощности.

Clinical relevance

Регистровые машины моделируют целочисленную арифметику реальных процессоров более непосредственно, чем ленты; примитивная рекурсия соответствует программам, которые всегда завершаются, и лежит в основе тотальных функциональных языков и анализа завершимости; а взгляд на рекурсивные функции связывает вычисления с основаниями математики.

History

Гёдель и Эрбранд определили общерекурсивные функции в начале 1930-х годов, а Клини разработал теорию, включая роль минимизации. Аккерман ранее представил свою быстрорастущую функцию, а Минский ввел регистровые и счетчиковые машины в 1960-х годах, доказав универсальность даже двухсчетчиковых машин.

Key figures

• Kurt Gödel
• Stephen Kleene
• Wilhelm Ackermann
• Marvin Minsky

Seminal works

• cutland1980
• minsky1967

Frequently asked questions

В чем разница между примитивно-рекурсивными и общерекурсивными функциями?

Примитивно-рекурсивные функции строятся с использованием ограниченных циклов и всегда завершаются, но они не охватывают все вычислимые функции. Добавление неограниченной минимизации, поиска, который может продолжаться неопределенно долго, дает общерекурсивные функции, которые точно совпадают с тьюринг-вычислимыми функциями.

Как машина всего с двумя счетчиками может быть такой же мощной, как компьютер?

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