Вычислимость

Recursive Functions и mu-recursion

Задолго до компьютеров математики пытались точно определить, что значит 'вычислить'. Частично-рекурсивные функции - третий ответ на этот вопрос, наряду с машиной Тьюринга и lambda-исчислением. Все три ответа совпадают - но каждый открывает свой угол зрения на природу вычислений.

**Union-Find (DSU)** - амортизированная сложность O(α(n)), где α - обратная функция Аккермана, практически O(1)
**Теоремы Гёделя** - следствие гёделевского кодирования: в арифметике есть недоказуемые истины
**Теория рекурсивных функций** - фундамент математической логики и верификации программ
**Нумерация программ** - основа понятия 'компилируемая программа - это данные'

Примитивно-рекурсивные функции

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

**Примитивная рекурсия гарантирует завершение**, но это ограничение: есть вычислимые функции, которые не являются примитивно-рекурсивными. Классический пример - функция Аккермана, которая растёт быстрее любой примитивно-рекурсивной функции.

Почему каждая примитивно-рекурсивная функция гарантированно завершается?

Mu-оператор и частичная рекурсия

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

**Частичность** - ключевое слово. Частично-рекурсивные функции могут быть не определены на некоторых входах (зависать). Это не баг - это необходимость: проблема останова доказывает, что нельзя ограничиться только тотальными (всегда завершающимися) функциями и охватить весь класс вычислимого.

Что произойдёт при вычислении μy [f(y) = 0], если f(y) ≠ 0 для всех y?

Функция Аккермана

В 1928 году Вильгельм Аккерман построил функцию, которая вычислима (завершается для любых входных данных), но растёт быстрее, чем любая примитивно-рекурсивная функция. Это доказало, что примитивная рекурсия не охватывает все вычислимые функции.

**Функция Аккермана в алгоритмах** - обратная функция Аккермана α(n) растёт так медленно, что при любых практических n она не превышает 4. Она фигурирует в анализе Union-Find (Disjoint Set Union) - амортизированная сложность операции O(α(n)), что практически O(1).

Почему функция Аккермана доказывает неполноту примитивной рекурсии?

Числа Гёделя и кодирование

Гёдель в 1931 году для доказательства своих теорем о неполноте разработал технику, которая оказалась фундаментальной для теории вычислимости: арифметическое кодирование формул и доказательств. Любой текст можно превратить в число, и наоборот.

Гёделевское кодирование позволяет формулам говорить о самих себе: «Эта формула недоказуема». Именно это привело к первой теореме Гёделя о неполноте: в любой непротиворечивой системе, достаточно богатой для арифметики, есть истинные, но недоказуемые утверждения.

**Универсальная нумерация программ** - прямое следствие идеи Гёделя: любую программу для МТ можно закодировать натуральным числом. Так возникает понятие «программа с номером e» - основа теории рекурсивных функций и рисайзинга теорем (s-m-n теорема, теорема о неподвижной точке Клини).

Почему для кодирования Гёделя используются степени простых чисел, а не просто суммы?