Теорема о сообщениях - Posts theorem

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

Фон

Смотрите также: Арифметическая_ иерархия § Отношение_ к_ машинам Тьюринга

В формулировке теоремы Поста используются несколько понятий, относящихся к определимость и теория рекурсии. В этом разделе дается краткий обзор этих концепций, которые подробно рассматриваются в соответствующих статьях.

В арифметическая иерархия классифицирует определенные наборы натуральных чисел, которые можно определить на языке арифметики Пеано. А формула как говорят ${\displaystyle \Sigma _{m}^{0}}$ если это экзистенциальное утверждение в пренекс нормальная форма (все кванторы впереди) с ${\displaystyle m}$ чередования экзистенциальных и универсальных кванторов, применяемых к формуле с ограниченные кванторы Только. Формально формула ${\displaystyle \phi (s)}$ на языке арифметики Пеано - это ${\displaystyle \Sigma _{m}^{0}}$ формула, если она имеет вид

${\displaystyle \left(\exists n_{1}^{1}\exists n_{2}^{1}\cdots \exists n_{j_{1}}^{1}\right)\left(\forall n_{1}^{2}\cdots \forall n_{j_{2}}^{2}\right)\left(\exists n_{1}^{3}\cdots \right)\cdots \left(Qn_{1}^{m}\cdots \right)\rho (n_{1}^{1},\ldots n_{j_{m}}^{m},x_{1},\ldots ,x_{k})}$

куда ${\displaystyle \rho }$ содержит только ограниченные кванторы и Q является ${\displaystyle \forall }$ если м даже и ${\displaystyle \exists }$ если м странно.

Набор натуральных чисел А как говорят ${\displaystyle \Sigma _{m}^{0}}$ если это определяется ${\displaystyle \Sigma _{m}^{0}}$ формула, то есть, если есть ${\displaystyle \Sigma _{m}^{0}}$ формула ${\displaystyle \phi (s)}$ так что каждое число п в А если и только если ${\displaystyle \phi (n)}$ держит. Известно, что если набор ${\displaystyle \Sigma _{m}^{0}}$ тогда это ${\displaystyle \Sigma _{n}^{0}}$ для любого ${\displaystyle n>m}$, но для каждого м Существует ${\displaystyle \Sigma _{m+1}^{0}}$ набор, который не ${\displaystyle \Sigma _{m}^{0}}$. Таким образом, количество изменений квантора, необходимое для определения набора, дает меру сложности набора.

Теорема Поста использует релятивизированную арифметическую иерархию, а также только что определенную нерелятивизированную иерархию. Множество А натуральных чисел называется ${\displaystyle \Sigma _{m}^{0}}$ относительно набора B, написано ${\displaystyle \Sigma _{m}^{0,B}}$, еслиА определяется ${\displaystyle \Sigma _{m}^{0}}$ формула на расширенном языке, которая включает предикат для членства в B.

В то время как арифметическая иерархия измеряет определимость множеств натуральных чисел, Степени Тьюринга измерить уровень невычислимости множеств натуральных чисел. Множество А как говорят Сводимый по Тьюрингу к набору B, написано ${\displaystyle A\leq _{T}B}$, если есть оракул машина Тьюринга это, учитывая оракул для B, вычисляет характеристическая функция из А. Прыжок Тьюринга набора А это форма Проблема с остановкой относительно А. Учитывая набор А, скачок Тьюринга ${\displaystyle A'}$ это набор индексов оракульных машин Тьюринга, которые останавливаются при вводе 0 при запуске с оракулом А. Известно, что каждый комплект А сводится по Тьюрингу к своему скачку Тьюринга, но скачок Тьюринга множества никогда не сводится по Тьюрингу к исходному множеству.

Теорема Поста использует конечно итерированные скачки Тьюринга. Для любого набора А натуральных чисел, обозначение${\displaystyle A^{(n)}}$ указывает на п-кратный повторный скачок Тьюринга А. Таким образом ${\displaystyle A^{(0)}}$ просто А, и ${\displaystyle A^{(n+1)}}$ это скачок Тьюринга ${\displaystyle A^{(n)}}$.

Теорема Поста и следствия

Теорема Поста устанавливает тесную связь между арифметической иерархией и степенями Тьюринга формы ${\displaystyle \emptyset ^{(n)}}$, то есть конечно итерированные скачки Тьюринга пустого множества. (Пустое множество может быть заменено любым другим вычислимым множеством без изменения истинности теоремы.)

Теорема Поста гласит:

1. Множество B является ${\displaystyle \Sigma _{n+1}^{0}}$ если и только если ${\displaystyle B}$ является рекурсивно перечислимый с помощью оракула машины Тьюринга с оракулом для ${\displaystyle \emptyset ^{(n)}}$, то есть тогда и только тогда, когда B является ${\displaystyle \Sigma _{1}^{0,\emptyset ^{(n)}}}$.
2. Набор ${\displaystyle \emptyset ^{(n)}}$ является ${\displaystyle \Sigma _{n}^{0}}$-полный на каждый ${\displaystyle n>0}$. Это означает, что каждый ${\displaystyle \Sigma _{n}^{0}}$ набор много-один сводимый к ${\displaystyle \emptyset ^{(n)}}$.

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

1. Исправить набор C. Множество B является ${\displaystyle \Sigma _{n+1}^{0,C}}$ если и только если B является ${\displaystyle \Sigma _{1}^{0,C^{(n)}}}$. Это релятивизация первой части теоремы Поста к оракулу. C.
2. Множество B является ${\displaystyle \Delta _{n+1}}$ если и только если ${\displaystyle B\leq _{T}\emptyset ^{(n)}}$. В более общем смысле, B является ${\displaystyle \Delta _{n+1}^{C}}$ если и только если ${\displaystyle B\leq _{T}C^{(n)}}$.
3. Набор определяется как арифметический, если он ${\displaystyle \Sigma _{n}^{0}}$ для некоторых п. Теорема Поста показывает, что, эквивалентно, множество арифметично тогда и только тогда, когда оно сводится по Тьюрингу к ${\displaystyle \emptyset ^{(m)}}$ для некоторых м.

Доказательство теоремы Поста

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

Работа Машина Тьюринга T на входе n можно логически формализовать в виде арифметика первого порядка. Например, мы можем использовать символы А_k, B_k и C_k для конфигурации ленты, состояния машины и местоположения вдоль ленты после k шагов, соответственно. Т переходная система определяет связь между (A_k, B_k, С_k) и (A_{к + 1}, B_{к + 1}, С_{к + 1}); их начальные значения (при k = 0) являются входом, начальным состоянием и нулем соответственно. Машина останавливается тогда и только тогда, когда существует число k такое, что B_k состояние остановки.

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

В случае остановки T в момент времени n₁, связь между (A_k, B_k, С_k) и (A_{к + 1}, B_{к + 1}, С_{к + 1}) должно выполняться только для k, ограниченного сверху числом n₁.

Таким образом, существует формула ${\displaystyle \varphi (n,n_{1})}$ в арифметика первого порядка без ООНограниченные кванторы, так что T останавливается на входе n в момент n₁ самое большее, если и только если ${\displaystyle \varphi (n,n_{1})}$ доволен.

Пример реализации

Например, для без префиксов Машина Тьюринга с двоичным алфавитом и без пробела, мы можем использовать следующие обозначения:

• А_k это 1-арый символ для конфигурации всей ленты после k шагов (которые мы можем записать в виде числа с LSB сначала значение m-го места на ленте является его m-м младшим битом). В частности, A₀ - начальная конфигурация ленты, соответствующая входу в машину.
• B_k это 1-арый символ состояния машины Тьюринга после k шагов. В частности, B₀ = q_я, начальное состояние машины Тьюринга.
• C_k это 1-арый символ расположения машины Тьюринга на ленте после k шагов. В частности, C₀ = 0.
• M (q, b) - функция перехода машины Тьюринга, записанная как функция от дублета (состояние машины, бит, прочитанный машиной) к триплету (новое состояние машины, бит, записанный машиной, +1 или - 1 машинное движение по ленте).
• bit (j, m) - j-й бит числа m. Это можно записать как арифметическую формулу первого порядка без неограниченных кванторов.

Для без префиксов Машину Тьюринга мы можем использовать для ввода n начальную конфигурацию ленты ${\displaystyle t(n)=cat(2^{ceil(log_{2}n)}-1,0,n)}$ где кошка означает конкатенацию; таким образом, t (n) представляет собой строку длины log (n), состоящую из единиц, за которой следует 0, а затем n.

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

• ${\displaystyle (B_{k+1},bit(C_{k},A_{k+1}),D)=M(B_{k},bit(C_{k},A_{k}))}$. Поскольку M имеет конечную область, ее можно заменить на область первого порядка бескванторный арифметическая формула. Точная формула, очевидно, зависит от M.
• ${\displaystyle C_{k+1}=C_{k}+D}$
• ${\displaystyle \forall j:j\neq C_{k}\rightarrow bit(j,A_{k+1})=bit(j,A_{k})}$. Обратите внимание, что при первых n₁ шагов, T никогда не достигает точки на ленте, превышающей n₁. Таким образом универсальный квантор над j может быть ограниченный автор n₁+1, поскольку биты за пределами этого местоположения не имеют отношения к работе машины.

T останавливается на входе n в момент времени n₁ самое большее, если и только если ${\displaystyle \varphi (n,n_{1})}$ выполнено, где:

${\displaystyle {\begin{aligned}\varphi (n,n_{1})=&(A_{0}=t(n))\land (B_{0}=q_{I})\land (C_{0}=0)\land (B_{n_{1}}=q_{H})\\&\land \forall k<n_{1}:((B_{k+1},bit(C_{k},A_{k+1}),1)=M(B_{k},bit(C_{k},A_{k}))\land C_{k+1}=C_{k}+1)&\\&\lor ((B_{k+1},bit(C_{k},A_{k+1}),-1)=M(B_{k},bit(C_{k},A_{k}))\land C_{k+1}=C_{k}-1))&\\&\land \forall j<n_{1}+1:j\neq C_{k}\rightarrow (bit(j,A_{k+1})=bit(j,A_{k}))&\end{aligned}}}$

Это арифметическая формула первого порядка без неограниченных кванторов, т.е. ${\displaystyle \Sigma _{0}^{0}}$.

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

Пусть S - множество, которое может быть рекурсивно пронумеровано Машина Тьюринга. Затем существует машина Тьюринга T, которая для каждого n в S останавливается, когда n задано на входе.

Это можно формализовать с помощью арифметической формулы первого порядка, представленной выше. Члены S - это числа n, удовлетворяющие следующей формуле:

${\displaystyle \exists n_{1}:\varphi (n,n_{1})}$

Эта формула находится в ${\displaystyle \Sigma _{1}^{0}}$. Следовательно, S находится в ${\displaystyle \Sigma _{1}^{0}}$Таким образом, каждое рекурсивно перечислимое множество находится в ${\displaystyle \Sigma _{1}^{0}}$.

Верно и обратное: для каждой формулы ${\displaystyle \varphi (n)}$ в ${\displaystyle \Sigma _{1}^{0}}$ с помощью k экзистенциальных кванторов, мы можем перечислить k-кортежи натуральных чисел и запустить машину Тьюринга, которая перебирает их все, пока не обнаружит, что формула удовлетворяется. Эта машина Тьюринга останавливается в точности на наборе натуральных чисел, удовлетворяющих ${\displaystyle \varphi (n)}$, и таким образом перечисляет соответствующее ему множество.

Машины Oracle

Точно так же работа машина оракула T с оракулом O, который останавливается не более чем через n₁ шаги на входе n можно описать формулой первого порядка ${\displaystyle \varphi _{O}(n,n_{1})}$, за исключением того, что формула ${\displaystyle \varphi _{1}(n,n_{1})}$ теперь включает:

• Новый предикат O_м, давая ответ оракула. Этот предикат должен удовлетворять некоторой формуле, которая будет рассмотрена ниже.
• Дополнительная лента - лента оракула, на которой T должен записывать число m для каждого обращения O (m) к оракулу; запись на этой ленте может быть логически формализована аналогично записи на магнитной ленте машины. Обратите внимание, что машина-оракул, которая останавливается не более чем через n₁ шагов успевает написать не более n₁ цифры на ленте оракула. Таким образом, оракул можно вызвать только с числами m, удовлетворяющими ${\displaystyle m<2^{n_{1}}}$.

Если оракул стоит за решение проблемы, O_м всегда «Да» или «Нет», которые мы можем формализовать как 0 или 1. Предположим, что сама проблема решения может быть формализована арифметической формулой первого порядка ${\displaystyle \psi ^{O}(m)}$.Затем T останавливается на n после не более чем n.₁ шаги тогда и только тогда, когда выполняется следующая формула:${\displaystyle \varphi _{O}(n,n_{1})=\forall m<2^{n_{1}}:((\psi ^{O}(m)\rightarrow (O_{m}=1))\land (\lnot \psi ^{O}(m)\rightarrow (O_{m}=0)))\land {\varphi _{O}}_{1}(n,n_{1})}$

куда ${\displaystyle {\varphi _{O}}_{1}(n,n_{1})}$ формула первого порядка без неограниченных кванторов.

Прыжок Тьюринга

Если O - оракул проблемы остановки машины T ', то ${\displaystyle \psi ^{O}(m)}$ то же самое, что "существует m₁ такой, что T ', начиная с входа m, находится в состоянии остановки после m₁ шаги ». Таким образом:${\displaystyle \psi ^{O}(m)=\exists m_{1}:\psi _{H}(m,m_{1})}$куда ${\displaystyle \psi _{H}(m,m_{1})}$ - формула первого порядка, формализующая T '. Если T 'машина Тьюринга (без оракула), ${\displaystyle \psi _{H}(m,m_{1})}$ в ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}}$ (т. е. не имеет неограниченных кванторов).

Поскольку существует конечное число чисел m, удовлетворяющих ${\displaystyle m<2^{n_{1}}}$, мы можем выбрать для всех одинаковое количество шагов: существует число m₁, такая, что T 'останавливается после m₁ шаги именно по этим входам ${\displaystyle m<2^{n_{1}}}$ для чего он вообще останавливается.

Переехать в пренекс нормальная форма, мы получаем, что машина оракула останавливается на входе n тогда и только тогда, когда выполняется следующая формула:${\displaystyle \varphi (n)=\exists n_{1}\exists m_{1}\forall m_{2}:(\psi _{H}(m,m_{2})\rightarrow (O_{m}=1))\land (\lnot \psi _{H}(m,m_{1})\rightarrow (O_{m}=0)))\land {\varphi _{O}}_{1}(n,n_{1})}$

(неформально существует «максимальное количество шагов» m₁ такой каждый оракул, который не останавливается в пределах первых метров₁ шаги не останавливаются вообще; однако для каждого m₂, каждый оракул, останавливающийся после m₂ шаги останавливаются).

Обратите внимание, что мы можем заменить как n₁ И м₁ одним числом - их максимумом - без изменения истинностного значения ${\displaystyle \varphi (n)}$. Таким образом, мы можем написать:${\displaystyle \varphi (n)=\exists n_{1}\forall m_{2}:(\psi _{H}(m,m_{2})\rightarrow (O_{m}=1))\land (\lnot \psi _{H}(m,n_{1})\rightarrow (O_{m}=0)))\land {\varphi _{O}}_{1}(n,n_{1})}$

Для оракула проблемы остановки машин Тьюринга ${\displaystyle \psi _{H}(m,m_{1})}$ в ${\displaystyle \Pi _{0}^{0}}$ и ${\displaystyle \varphi (n)}$ в ${\displaystyle \Sigma _{2}^{0}}$. Таким образом, каждый набор, рекурсивно перечисляемый оракульной машиной с оракулом для ${\displaystyle \emptyset ^{(1)}}$, в ${\displaystyle \Sigma _{2}^{0}}$.

Верно и обратное: предположим ${\displaystyle \varphi (n)}$ формула в ${\displaystyle \Sigma _{2}^{0}}$ с k₁ экзистенциальные кванторы, за которыми следует k₂ универсальные кванторы. Эквивалентно ${\displaystyle \varphi (n)}$ имеет k₁ экзистенциальные кванторы с последующим отрицанием формулы в ${\displaystyle \Sigma _{1}^{0}}$; последняя формула может быть перечислена машиной Тьюринга и, таким образом, может быть немедленно проверена оракулом на предмет ${\displaystyle \emptyset ^{(1)}}$.

Таким образом, мы можем перечислить k₁-наборы натуральных чисел и запустить машину оракула с оракулом для ${\displaystyle \emptyset ^{(1)}}$ который проходит через все, пока не найдет удовлетворение для формулы. Эта машина-оракул останавливается в точности на наборе натуральных чисел, удовлетворяющих ${\displaystyle \varphi (n)}$, и таким образом перечисляет соответствующее ему множество.

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

В более общем смысле, предположим, что каждый набор, который рекурсивно перечисляется оракульной машиной с оракулом для ${\displaystyle \emptyset ^{(p)}}$ в ${\displaystyle \Sigma _{p+1}^{0}}$. Затем для машины оракула с оракулом для ${\displaystyle \emptyset ^{(p+1)}}$, ${\displaystyle \psi ^{O}(m)=\exists m_{1}:\psi _{H}(m,m_{1})}$ в ${\displaystyle \Sigma _{p+1}^{0}}$.

С ${\displaystyle \psi ^{O}(m)}$ такой же как ${\displaystyle \varphi (n)}$ для предыдущего прыжка Тьюринга его можно построить (как мы только что сделали с ${\displaystyle \varphi (n)}$ выше) так что ${\displaystyle \psi _{H}(m,m_{1})}$ в ${\displaystyle \Pi _{p}^{0}}$. После перехода к формальной форме prenex новый ${\displaystyle \varphi (n)}$ в ${\displaystyle \Sigma _{p+2}^{0}}$.

По индукции каждый набор, который рекурсивно перечислим с помощью оракула с оракулом для ${\displaystyle \emptyset ^{(p)}}$, в ${\displaystyle \Sigma _{p+1}^{0}}$.

Другое направление можно также доказать по индукции: предположим, что каждая формула в ${\displaystyle \Sigma _{p+1}^{0}}$ можно перечислить с помощью оракула с оракулом для ${\displaystyle \emptyset ^{(p)}}$.

Теперь предположим ${\displaystyle \varphi (n)}$ формула в ${\displaystyle \Sigma _{p+2}^{0}}$ с k₁ экзистенциальные кванторы, за которыми следует k₂ универсальные кванторы и т. д. ${\displaystyle \varphi (n)}$ имеет k₁ экзистенциальные кванторы с последующим отрицанием формулы в ${\displaystyle \Sigma _{p+1}^{0}}$; последняя формула может быть пересчитана машиной оракула с оракулом для ${\displaystyle \emptyset ^{(p)}}$ и, таким образом, может быть немедленно проверен оракулом на предмет ${\displaystyle \emptyset ^{(p+1)}}$.

Таким образом, мы можем перечислить k₁-наборы натуральных чисел и запустить машину оракула с оракулом для ${\displaystyle \emptyset ^{(p+1)}}$ который проходит через все, пока не найдет удовлетворение для формулы. Эта машина-оракул останавливается в точности на наборе натуральных чисел, удовлетворяющих ${\displaystyle \varphi (n)}$, и таким образом перечисляет соответствующее ему множество.

Рекомендации

Роджерс, Х. Теория рекурсивных функций и эффективной вычислимости, MIT Press. ISBN  0-262-68052-1; ISBN  0-07-053522-1

Соаре, Р. Рекурсивно перечислимые множества и степени. Перспективы математической логики. Springer-Verlag, Берлин, 1987. ISBN  3-540-15299-7