Введение

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

Предыстория

В формулировке теоремы Поста используются несколько концепций, относящихся к теории определимости и рекурсии. В данном разделе представлен краткий обзор этих понятий, которые подробно рассматриваются в соответствующих статьях. Арифметическая иерархия классифицирует определенные множества натуральных чисел, которые можно определить на языке арифметики Пеано. Формула называется Σ<sub>m</sub>-формулой, если это экзистенциальное утверждение в пренекс нормальной форме (все кванторы в начале) с *m* чередованиями между экзистенциальными и универсальными кванторами, примененными к формуле, содержащей только ограниченные кванторы. Формально, формула на языке арифметики Пеано является Σ<sub>m</sub>-формулой, если она имеет вид

где φ содержит только ограниченные кванторы, а Q является ∃, если *m* четно, и ∀, если *m* нечетно. Множество натуральных чисел называется Σ<sub>m</sub>-множеством, если оно определяется Σ<sub>m</sub>-формулой, то есть существует Σ<sub>m</sub>-формула φ такая, что каждое число *n* принадлежит множеству, если и только если φ(n) истинно. Известно, что если множество является Σ<sub>m</sub>-множеством, то оно является Σ<sub>n</sub>-множеством для любого *n* > *m*, но для каждого *m* существует Σ<sub>m</sub>-множество, которое не является Σ<sub>m-1</sub>-множеством. Таким образом, количество чередований кванторов, необходимых для определения множества, является мерой сложности этого множества. Теорема Поста использует релятивизированную арифметическую иерархию, а также неорилятивизированную иерархию, только что определенную. Множество натуральных чисел *A* называется Σ<sub>m</sub>-относительным к множеству *B*, что записывается как *A ≤<sub>m</sub> B*, если *A* определяется Σ<sub>m</sub>-формулой в расширенном языке, который включает предикат принадлежности к *B*.

В то время как арифметическая иерархия измеряет определимость множеств натуральных чисел, степени Тьюринга измеряют уровень невычислимости множеств натуральных чисел. Множество *A* называется Тьюрингово сводимым к множеству *B*, что записывается как *A ≤<sub>T</sub> B*, если существует оракульная машина Тьюринга, которая, получив оракул для *B*, вычисляет характеристическую функцию *A*. Прыжок Тьюринга множества *A* является формой задачи останова относительно *A*. Для любого множества *A*, прыжок Тьюринга *A'* является множеством индексов оракульных машин Тьюринга, которые останавливаются на входе *e*, когда выполняются с оракулом *A*. Известно, что каждое множество *A* Тьюрингово сводимо к своему прыжку Тьюринга *A'*, но прыжок Тьюринга множества *A'* никогда не Тьюрингово сводим к исходному множеству *A*. Теорема Поста использует конечно итерированные прыжки Тьюринга. Для любого множества *A* натуральных чисел обозначение *A<sup>(n)</sup>* указывает на *n*-кратно итерированный прыжок Тьюринга *A*. Таким образом, *A<sup>(0)</sup>* это просто *A*, а *A<sup>(1)</sup>* это прыжок Тьюринга *A*.

Формализация машин Тьюринга в арифметике первого порядка

Работа машины Тьюринга на входе может быть формализована логически в арифметике первого порядка. Например, мы можем использовать символы , , и для конфигурации ленты, состояния машины и положения на ленте после шагов, соответственно. Система переходов определяет отношение между и ; их начальные значения (для ) – это вход, начальное состояние и ноль, соответственно. Машина останавливается тогда и только тогда, когда существует число , которое является останавливающим состоянием. Точное отношение зависит от конкретной реализации понятия машины Тьюринга (например, её алфавита, допустимого режима движения по ленте и т.д.). В случае остановки в момент времени , отношение между и должно выполняться только для k, ограниченного сверху значением . Таким образом, существует формула в арифметике первого порядка, не содержащая неограниченных кванторов, такая, что машина Тьюринга останавливается на входе за время , не превышающее , тогда и только тогда, когда эта формула выполняется.

Рекурсивно перечисляемые множества

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

Эта формула находится в , следовательно, в . Таким образом, каждое рекурсивно перечислимое множество находится в .

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

Высшие прыжки Тьюринга

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

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

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