Матлогика · Часть VI — Теория алгоритмов (36–42)

Строгое определение → идея доказательства → объяснение «на пальцах» → типичные ловушки. Слева — оглавление по всем 5 файлам: текущий файл листается мгновенно, билеты других файлов (со стрелкой ↗) открываются в своём файле. Файлы держите в одной папке.

Часть VI · Теория алгоритмов (билеты 36–42)

36

Машины Тьюринга. Вычислимые функции. Тезис Чёрча.

машина Тьюринга M=⟨Q, Γ, δ, q0, F⟩: конечное множество состояний Q, ленточный алфавит Γ (с пустым символом), функция перехода δ:Q×Γ→Q×Γ×{L,R}, начальное q0 и заключительные F. Лента бесконечна; головка читает символ, пишет новый, сдвигается влево/вправо и меняет состояние по δ.
вычислимая функция Частичная функция f:ℕk→ℕ вычислима, если существует МТ, которая на (кодированном) входе x̄ останавливается с f(x̄) на ленте, когда f(x̄) определено, и не останавливается, когда не определено.
тезис Чёрча–Тьюринга «Интуитивно вычислимое = вычислимое на машине Тьюринга» (= λ-определимое = частично рекурсивное, б.38). Это тезис, а не теорема: он связывает неформальное понятие «алгоритм» с формальным и подтверждается совпадением всех предложенных формализаций.
на пальцах МТ — предельно примитивный «компьютер»: бесконечная клетчатая лента и крошечная инструкция «что делать, видя символ в состоянии». Тезис Чёрча утверждает, что эта примитивность не теряет общности: всё, что вообще можно вычислить алгоритмом, считается уже и на МТ.
37

Суперпозиция и примитивная рекурсия. Примитивно рекурсивные функции.

базовые функции Нуль O(x̄)=0, следование S(x)=x+1, проекции Ink(x1,…,xn)=xk.
операторы Суперпозиция (композиция):
h(x̄) = f(g1(x̄),…,gm(x̄)).
Примитивная рекурсия:
f(x̄,0)=g(x̄),   f(x̄,y+1)=h(x̄,y,f(x̄,y)).
ПРФ — наименьший класс, содержащий базовые и замкнутый под этими двумя операторами.
свойства и примеры Все ПРФ всюду определены и вычислимы. Примеры: x+y, x·y, xy, x!, sg(x), ограниченные суммы/произведения, характеристические функции =,<. Класс замкнут относительно определения по случаям и ограниченных кванторов.
на пальцах ПРФ — это «программы только с циклами for»: число итераций известно заранее (рекурсия по последнему аргументу = цикл «повторить y раз»). Поэтому они никогда не зацикливаются и всегда дают ответ. Чего им не хватает — цикла while с неизвестным числом шагов (б.38).
38

Минимизация. Частично рекурсивные функции. Функция Аккермана.

μ-оператор (минимизация)
f(x̄) = μy[ g(x̄,y)=0 ]
— наименьший y, при котором g(x̄,y)=0 (и g(x̄,y′) определено для всех y′<y); если такого y нет, f(x̄) не определено.
классы функций Частично рекурсивные функции (ЧРФ) — замыкание базовых под суперпозицией, примитивной рекурсией и минимизацией. Общерекурсивные — всюду определённые ЧРФ. Теорема (Тьюринг–Чёрч–Клини): ЧРФ = функции, вычислимые на МТ.
функция Аккермана Двойная рекурсия A(0,n)=n+1, A(m+1,0)=A(m,1), A(m+1,n+1)=A(m,A(m+1,n)) — всюду определена и вычислима, но не примитивно рекурсивна (растёт быстрее любой ПРФ). Это доказывает: ПРФ ⊊ общерекурсивные — минимизация (while) действительно расширяет класс.
на пальцах μ — это цикл while (g≠0) y++;: ищем подходящий y, не зная заранее, найдём ли. Отсюда и частичность: поиск может не закончиться. Аккерман показывает, что без такого «неограниченного поиска» некоторые вполне законные функции не построить.
39

Разрешимые и перечислимые множества. Теорема Поста.

определения A⊆ℕ разрешимо (рекурсивно), если вычислима его характеристическая функция χA. A перечислимо (р.п.), если выполнено одно из эквивалентных условий: A=∅ или A — область значений вычислимой функции; A — область определения вычислимой функции; A полуразрешимо (есть алгоритм, останавливающийся тогда и только тогда, когда x∈A).
теорема Поста A разрешимо ⟺ и A, и его дополнение A̅ перечислимы. «⟸»: запускаем параллельно (с чередованием шагов) полуразрешающие алгоритмы для A и для A̅; ровно один из них остановится — он и даёт ответ «да/нет» за конечное время. «⟹»: разрешимое тривиально полуразрешимо, как и его дополнение. ∎
на пальцах Перечислимое — «да»-ответ можно подтвердить за конечное время (дождавшись остановки), но «нет»-ответ можно ждать вечно. Разрешимое — подтверждаемы оба ответа. Пост: если умеешь подтверждать и «да», и «нет» — умеешь и решать (запусти обе проверки наперегонки).
40

Универсальные функции. Теорема о s-m-n.

нумерация и универсальная функция Зафиксируем эффективную нумерацию программ (МТ); φe — частичная функция, вычисляемая e-й машиной. Универсальная функция
U(e,x) = φe(x)
сама вычислима — её считает универсальная машина Тьюринга (интерпретатор: по коду e симулирует работу e-й машины на x).
теорема s-m-n Существует примитивно рекурсивная функция s, такая что
φs(e,y)(x) = φe(y,x).
То есть часть входа можно «зашить» в код программы, эффективно получив новый код.
на пальцах Универсальная функция — это один интерпретатор для всех программ (как виртуальная машина, исполняющая чужой код). Теорема s-m-n — «частичное применение»/каррирование на уровне программ: можно заранее подставить аргумент y и автоматически получить специализированную программу. Эти два факта — фундамент всей теории вычислимости.
41

Существование перечислимого неразрешимого множества.

множество K
K = { e : φe(e)↓ }
— коды программ, останавливающихся на собственном коде.
K перечислимо, но неразрешимо Перечислимо: универсальной машиной (б.40) симулируем φe(e); если остановилась — e∈K. Это полуразрешение.
Неразрешимо (диагональ): допустим, χK вычислима. Определим
f(e) = ↑ (зацикливается), если e∈K;   f(e)=0, если e∉K.
f вычислима, значит f=φe0 для некоторого e0. Тогда
e0∈K ⟺ φe0(e0)↓ ⟺ f(e0)↓ ⟺ e0∉K
— противоречие. Значит χK невычислима. ∎
следствие Дополнение K̅ не перечислимо (иначе по теореме Поста K было бы разрешимо). Так разрешимое ⊊ перечислимое: есть р.п. множества, которые не разрешить.
на пальцах Тот же диагональный приём Кантора (как у «|X|<|𝒫(X)|», б.16), но применённый к программам: строим функцию, которая на каждом коде «делает наоборот» предполагаемого решателя — и она же где-то обязана встретить саму себя, что и рушит предположение.
42

Проблема остановки. Теорема Райса.

проблема остановки
HALT = { (e,x) : φe(x)↓ }
— «остановится ли программа e на входе x». Утверждение: HALT неразрешима.
доказательство (сведение K к HALT) e∈K ⟺ φe(e)↓ ⟺ (e,e)∈HALT. Если бы HALT была разрешима, то и K разрешалось бы (подставляя x=e) — противоречие с б.41. Значит HALT неразрешима. ∎
теорема Райса Любое нетривиальное свойство вычислимых функций (зависящее только от вычисляемой функции, а не от текста программы; нетривиальное = выполнено не для всех и не ни для кого) — неразрешимо. Например, нельзя алгоритмически проверить «φe всюду определена», «φe≡0», «φe вычисляет данную функцию».
на пальцах Фундаментальный предел: по коду программы нельзя алгоритмически предсказать её поведение. Остановка — простейший такой вопрос, и уже он неразрешим; Райс обобщает: любое содержательное свойство «что программа делает» алгоритмически непроверяемо. Единственный общий способ узнать — запустить и ждать (а ждать, возможно, придётся вечно).