Арифметическая иерархия

Иллюстрация того, как взаимодействуют уровни иерархии и где в ней находятся некоторые основные категории.

В математической логике , в арифметической иерархии , арифметической иерархии или иерархии Клини-Мостовской (после того, как математика Клини и Анджей Мостовский ) классифицирует определенные наборы , основанные на сложностях формул , которые определяют их. Любой набор, получивший классификацию, называется арифметическим .

Арифметическая иерархия важна в теории рекурсии , эффективной дескриптивной теории множеств и изучении формальных теорий, таких как арифметика Пеано .

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

Гиперарифметическая иерархия и аналитическая иерархия расширить арифметическую иерархию для классификации дополнительных формул и множеств.

Арифметическая иерархия формул [ править ]

Арифметическая иерархия классифицирует формулы на языке арифметики первого порядка . Обозначены классификации и для натуральных чисел n (включая 0). Греческие буквы здесь - это световые символы, что означает, что формулы не содержат заданных параметров.${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$

Если формула логически эквивалентна формуле только с ограниченными кванторами, то ей присваиваются классификации и .${\ displaystyle \ phi}$${\ displaystyle \ phi}$${\displaystyle \Sigma _{0}^{0}}$${\displaystyle \Pi _{0}^{0}}$

Классификации и определяются индуктивно для каждого натурального числа n с использованием следующих правил:${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$

• Если логически эквивалентна формуле вида , где есть , то присваивается классификация .${\displaystyle \phi }$${\displaystyle \exists m_{1}\exists m_{2}\cdots \exists m_{k}\psi }$${\displaystyle \psi }$${\displaystyle \Pi _{n}^{0}}$${\displaystyle \phi }$${\displaystyle \Sigma _{n+1}^{0}}$
• Если логически эквивалентна формуле вида , где есть , то присваивается классификация .${\displaystyle \phi }$${\displaystyle \forall m_{1}\forall m_{2}\cdots \forall m_{k}\psi }$${\displaystyle \psi }$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \phi }$${\displaystyle \Pi _{n+1}^{0}}$

Кроме того, формула эквивалентна формуле, которая начинается с некоторых экзистенциальных кванторов и чередует время между сериями экзистенциальных и универсальных кванторов ; в то время как формула эквивалентна формуле, которая начинается с некоторых универсальных кванторов и чередуется аналогичным образом.${\displaystyle \Sigma _{n}^{0}}$${\displaystyle n-1}$${\displaystyle \Pi _{n}^{0}}$

Поскольку каждая формула эквивалентна формуле в предваренной нормальной форме , каждой формуле без заданных кванторов присваивается хотя бы одна классификация. Поскольку избыточные кванторы могут быть добавлены к любой формуле, как только формуле будет присвоена классификация, или ей будут назначены классификации и для каждого r больше n . Таким образом, наиболее важной классификацией, назначаемой формуле, является класс с наименьшим n , поскольку этого достаточно для определения всех остальных классификаций.${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle \Sigma _{r}^{0}}$${\displaystyle \Pi _{r}^{0}}$

Арифметическая иерархия множеств натуральных чисел [ править ]

Множество натуральных чисел X определяется формулой φ в языке арифметики Пеано (язык первого порядка с символами «0» для нуля, «S» для функции-преемника, «+» для сложения, «×» для умножения , и "=" для равенства), если элементы X - это в точности числа, удовлетворяющие φ. То есть, для всех натуральных чисел п ,

${\displaystyle n\in X\Leftrightarrow \mathbb {N} \models \varphi ({\underline {n}}),}$

где - число на языке арифметики, соответствующее . Множество определимо в арифметике первого порядка, если оно определяется некоторой формулой на языке арифметики Пеано.${\displaystyle {\underline {n}}}$${\displaystyle n}$

Каждый набор Х натуральных чисел , что определимо в арифметиках первого порядка присваиваются классификация формы , и , где это натуральное число, следующим образом . Если X определяется формулой, то X присваивается классификация . Если X определяется формулой, то X присваивается классификация . Если X равно и то и другое, то ему назначается дополнительная классификация .${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle \Delta _{n}^{0}}$${\displaystyle n}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle X}$${\displaystyle \Delta _{n}^{0}}$

Обратите внимание, что редко имеет смысл говорить о формулах; первый квантор формулы либо экзистенциальный, либо универсальный. Итак, набор не определяется формулой; скорее, есть и те и другие формулы, которые определяют набор.${\displaystyle \Delta _{n}^{0}}$${\displaystyle \Delta _{n}^{0}}$${\displaystyle \Delta _{n}^{0}}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$

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

Релятивизированные арифметические иерархии [ править ]

Подобно тому , как мы можем определить , что это значит для множества X быть рекурсивными относительно другого множество Y , позволяя вычисление , определяющее X проконсультироваться Y в качестве оракула , мы можем распространить это понятие на всю арифметическую иерархию и определить , что значит для X в быть , или в Y , обозначаемые соответственно и . Для этого зафиксируйте набор целых чисел Y и добавьте предикат членства в Y в язык арифметики Пеано. Затем мы говорим, что X находится внутри, если он определяется${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Delta _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle \Sigma _{n}^{0,Y}}$ ${\displaystyle \Delta _{n}^{0,Y}}$${\displaystyle \Pi _{n}^{0,Y}}$${\displaystyle \Sigma _{n}^{0,Y}}$${\displaystyle \Sigma _{n}^{0}}$формула на этом расширенном языке. Другими словами, X есть , если она определяется формулой разрешено задавать вопросы о членстве в Y . В качестве альтернативы можно рассматривать наборы как те наборы, которые могут быть построены, начиная с наборов, рекурсивных по Y, и поочередно принимая объединения и пересечения этих наборов до n раз.${\displaystyle \Sigma _{n}^{0,Y}}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Sigma _{n}^{0,Y}}$

Например, пусть Y будет набором целых чисел. Пусть X будет набором чисел, делящихся на элемент Y. Тогда X определяется формулой, так что X находится в (на самом деле он также входит, поскольку мы могли бы связать оба квантора с помощью n).${\displaystyle \phi (n)=\exists m\exists t(Y(m)\land m\times t=n)}$${\displaystyle \Sigma _{1}^{0,Y}}$${\displaystyle \Delta _{0}^{0,Y}}$

Арифметическая сводимость и степени [ править ]

Арифметическая сводимость - это промежуточное понятие между сводимостью по Тьюрингу и гиперарифметической сводимостью .

Набор является арифметическим (также арифметическим и арифметически определимым ), если он определяется некоторой формулой на языке арифметики Пеано. Эквивалентно X является арифметическим, если X равно или для некоторого целого числа n . Множество Х является арифметической в множестве Y , обозначаются , если Х определят , как некоторая формула на языке арифметики Пеано продлена предикатом на членство в Y . Эквивалентно, X является арифметическим по Y, если X находится в или${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle X\leq _{A}Y}$${\displaystyle \Sigma _{n}^{0,Y}}$${\displaystyle \Pi _{n}^{0,Y}}$для некоторого целого n . Синоним является: X является арифметический сводим к Y .${\displaystyle X\leq _{A}Y}$

Отношение рефлексивно и транзитивно, поэтому отношение определяется правилом${\displaystyle X\leq _{A}Y}$${\displaystyle \equiv _{A}}$

${\displaystyle X\equiv _{A}Y\Leftrightarrow X\leq _{A}Y\land Y\leq _{A}X}$

является отношением эквивалентности. Классы эквивалентности этого отношения называются арифметическими степенями ; они частично заказаны под .${\displaystyle \leq _{A}}$

Арифметическая иерархия подмножеств пространства Кантора и Бэра [ править ]

Канторовым пространство , обозначается , есть множество всех бесконечных последовательностей 0 и 1; бэровский , обозначаются или , есть множество всех бесконечных последовательностей натуральных чисел. Обратите внимание, что элементы пространства Кантора можно отождествить с наборами целых чисел, а элементы пространства Бэра - с функциями от целых до целых чисел.${\displaystyle 2^{\omega }}$${\displaystyle \omega ^{\omega }}$${\displaystyle {\mathcal {N}}}$

Обычная аксиоматизация арифметики второго порядка использует язык, основанный на множествах, в котором кванторы множеств естественным образом могут рассматриваться как количественные в пространстве Кантора. Подмножеству пространства Кантора присваивается классификация, если оно определяется формулой. Набору присваивается классификация, если она определяется формулой. Если набор как и тогда дается дополнительная классификация . Например, пусть будет набор всех бесконечных двоичных строк, которые не все 0 (или, что эквивалентно, набор всех непустых наборов целых чисел). Как мы видим, это определяется формулой и, следовательно, является набором.${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle \Delta _{n}^{0}}$${\displaystyle O\subset 2^{\omega }}$${\displaystyle O=\{X\in 2^{\omega }|\exists n(X(n)=1)\}}$${\displaystyle O}$${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \Sigma _{1}^{0}}$

Обратите внимание, что хотя элементы пространства Кантора (рассматриваемые как наборы целых чисел) и подмножества пространства Кантора классифицируются в арифметических иерархиях, это не одна и та же иерархия. На самом деле отношения между двумя иерархиями интересны и нетривиальны. Например, элементы пространства Кантора (в общем случае) не совпадают с элементами пространства Кантора, так что это подмножество пространства Кантора. Однако есть много интересных результатов, касающихся двух иерархий.${\displaystyle \Pi _{n}^{0}}$${\displaystyle X}$${\displaystyle \{X\}}$${\displaystyle \Pi _{n}^{0}}$

Существует два способа классификации подмножества пространства Бэра в арифметической иерархии.

• Подмножество пространства Бэра имеет соответствующее подмножество Cantor пространства при отображении , который принимает каждую функцию из , чтобы к характеристической функции ее графа. Подмножеству пространства Бэра дается классификация , или тогда и только тогда, когда соответствующее подмножество пространства Кантора имеет ту же классификацию.${\displaystyle \omega }$${\displaystyle \omega }$${\displaystyle \Sigma _{n}^{1}}$${\displaystyle \Pi _{n}^{1}}$${\displaystyle \Delta _{n}^{1}}$
• Эквивалентное определение аналитической иерархии в пространстве Бэра дается путем определения аналитической иерархии формул с использованием функциональной версии арифметики второго порядка; тогда аналитическая иерархия на подмножествах пространства Кантора может быть определена из иерархии на пространстве Бэра. Это альтернативное определение дает точно такие же классификации, как и первое определение.

Параллельное определение используется для определения арифметической иерархии конечных декартовых степеней пространства Бэра или пространства Кантора с использованием формул с несколькими свободными переменными. Арифметическая иерархия может быть определена на любом эффективном польском пространстве ; определение особенно просто для пространств Кантора и Бэра, потому что они соответствуют языку обычной арифметики второго порядка.

Обратите внимание, что мы также можем определить арифметическую иерархию подмножеств пространств Кантора и Бэра относительно некоторого набора целых чисел. На самом деле полужирный только объединение всех множеств целых чисел Y . Обратите внимание, что иерархия жирным шрифтом - это просто стандартная иерархия наборов Бореля .${\displaystyle \mathbf {\Sigma } _{n}^{0}}$${\displaystyle \Sigma _{n}^{0,Y}}$

Расширения и варианты [ править ]

Можно определить арифметическую иерархию формул, используя язык, расширенный функциональным символом для каждой примитивной рекурсивной функции . Этот вариант немного меняет классификацию , поскольку использование примитивных рекурсивных функций в арифметике Пеано первого порядка требует, как правило, неограниченного экзистенциального квантора, и, таким образом, некоторые множества, которые входят в это определение, входят в определение, данное в начале этого статья. и, таким образом, все более высокие классы в иерархии остаются неизменными.${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$${\displaystyle \Sigma _{0}^{0}}$${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \Sigma _{1}^{0}}$

Более семантическая вариация иерархии может быть определена для всех конечных отношений натуральных чисел; используется следующее определение. Каждое вычислимое отношение определяется как . Классификации и определяются индуктивно по следующим правилам.${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$

• Если отношение , то отношение определяется как${\displaystyle R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle S(n_{1},\ldots ,n_{l})=\forall m_{1}\cdots \forall m_{k}R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})}$${\displaystyle \Pi _{n+1}^{0}}$
• Если отношение , то отношение определяется как${\displaystyle R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle S(n_{1},\ldots ,n_{l})=\exists m_{1}\cdots \exists m_{k}R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})}$${\displaystyle \Sigma _{n+1}^{0}}$

Этот вариант немного меняет классификацию некоторых наборов. В частности, как класс множеств (определяемых отношениями в классе) идентичен тому, как последний был определен ранее. Его можно расширить, чтобы охватить финитарные отношения в натуральных числах, пространстве Бэра и пространстве Кантора.${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$${\displaystyle \Delta _{1}^{0}}$

Значение обозначений [ править ]

Обозначению арифметической иерархии формул можно придать следующие значения.

Нижний индекс в символах и указывает количество чередований блоков кванторов универсальных и экзистенциальных чисел, которые используются в формуле. Более того, самый внешний блок экзистенциальный в формулах и универсальный в формулах.${\displaystyle n}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$

Верхний индекс в символах , и указывает на тип объектов, по которым проводится количественная оценка. Объекты типа 0 - это натуральные числа, а объекты типа - это функции, которые сопоставляют набор объектов типа с натуральными числами. Количественная оценка объектов более высокого типа, таких как функции от натуральных чисел до натуральных чисел, описывается надстрочным индексом больше 0, как в аналитической иерархии . Верхний индекс 0 указывает кванторы над числами, верхний индекс 1 будет указывать количественную оценку функций от чисел к числам (объекты типа 1), верхний индекс 2 будет соответствовать количественной оценке функций, которые принимают объект типа 1 и возвращают число, и так далее.${\displaystyle 0}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle \Delta _{n}^{0}}$${\displaystyle i+1}$${\displaystyle i}$

Примеры [ править ]

• Эти наборы чисел являются те , определяемой формулой вида , где имеют только ограниченные кванторы. Это в точности рекурсивно перечислимые множества .${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \exists n_{1}\cdots \exists n_{k}\psi (n_{1},\ldots ,n_{k},m)}$${\displaystyle \psi }$
• Набор натуральных чисел, которые являются индексами машин Тьюринга, вычисляющих общие функции, равен . Интуитивно, индекс попадает в этот набор тогда и только тогда, когда для каждого «существует такое, что машина Тьюринга с индексом останавливается при вводе после шагов». Полное доказательство показало бы, что свойство, показанное в кавычках в предыдущем предложении, может быть определено в язык арифметики Пеано формулой.${\displaystyle \Pi _{2}^{0}}$${\displaystyle e}$${\displaystyle m}$${\displaystyle s}$${\displaystyle e}$${\displaystyle m}$${\displaystyle s}$${\displaystyle \Sigma _{1}^{0}}$
• Каждое подмножество пространства Бэра или пространства Кантора является открытым множеством в обычной топологии на пространстве. Более того, для любого такого множества существует вычислимая нумерация гёделевских чисел основных открытых множеств, объединение которых является исходным множеством. По этой причине наборы иногда называют фактически открытыми . Точно так же каждое множество замкнуто, и множества иногда называют эффективно замкнутыми .${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \Pi _{1}^{0}}$${\displaystyle \Pi _{1}^{0}}$
• Каждое арифметическое подмножество пространства Кантора или пространства Бэра является борелевским множеством . Иерархия Lightface Borel расширяет арифметическую иерархию за счет включения дополнительных наборов Borel. Например, каждое подмножество пространства Кантора или Бэра является набором (то есть набором, который равен пересечению счетного числа открытых множеств). Более того, каждое из этих открытых множеств есть, и список гёделевских чисел этих открытых множеств имеет вычислимое перечисление. Если это формула со свободным набором переменной X и свободными числовыми переменными, то набор является пересечением множеств формы, поскольку n пробегает множество натуральных чисел.${\displaystyle \Pi _{2}^{0}}$${\displaystyle G_{\delta }}$${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \phi (X,n,m)}$${\displaystyle \Sigma _{0}^{0}}$${\displaystyle n,m}$${\displaystyle \Pi _{2}^{0}}$${\displaystyle \{X\mid \forall n\exists m\phi (X,n,m)\}}$${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \{X\mid \exists m\phi (X,n,m)\}}$
• Эти формулы могут быть проверены при переходе всех случаях один за другим, что возможно , так как все их кванторы ограничены. Время для этого полиномиально по их аргументам (например, полиномиально от n для ); таким образом, соответствующие им проблемы решения включены в E (поскольку n экспоненциально по количеству битов). Это больше не выполняется при альтернативных определениях , которые позволяют использовать примитивные рекурсивные функции, поскольку теперь кванторы могут быть связаны любой примитивно рекурсивной функцией аргументов.${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$${\displaystyle \varphi (n)}$${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$
• В формулах под альтернативным определением, что позволяет использовать примитивные рекурсивные функции с ограниченными кванторами, соответствуют наборам целых чисел вида для примитивной рекурсивной функции F . Это происходит потому , что позволяет ограниченный квантор не добавляет ничего к определению: для примитивно рекурсивной F , такое же , как и то же ; с рекурсией курса значений каждый из них может быть определен одной простой функцией рекурсии.${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$${\displaystyle \{n:f(n)=0\}}$${\displaystyle \forall k<n:f(k)=0}$${\displaystyle f(0)+f(1)+...f(n)=0}$${\displaystyle \exists k<n:f(k)=0}$${\displaystyle f(0)*f(1)*...f(n)=0}$

Свойства [ править ]

Следующие свойства имеют место для арифметической иерархии множеств натуральных чисел и арифметической иерархии подмножеств пространства Кантора или Бэра.

• Наборы и замкнуты относительно конечных объединений и конечных пересечений соответствующих им элементов.${\displaystyle \Pi _{n}^{0}}$${\displaystyle \Sigma _{n}^{0}}$
• Набор есть тогда и только тогда, когда его дополнение есть . Набор есть тогда и только тогда, когда набор одновременно и , и в этом случае его дополнение также будет .${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle \Delta _{n}^{0}}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle \Pi _{n}^{0}}$${\displaystyle \Delta _{n}^{0}}$
• Включения и держи для всех . Таким образом иерархия не рушится. Это прямое следствие теоремы Поста .${\displaystyle \Pi _{n}^{0}\subsetneq \Pi _{n+1}^{0}}$${\displaystyle \Sigma _{n}^{0}\subsetneq \Sigma _{n+1}^{0}}$${\displaystyle n}$
• Включения , и удержания для .${\displaystyle \Delta _{n}^{0}\subsetneq \Pi _{n}^{0}}$${\displaystyle \Delta _{n}^{0}\subsetneq \Sigma _{n}^{0}}$${\displaystyle \Sigma _{n}^{0}\cup \Pi _{n}^{0}\subsetneq \Delta _{n+1}^{0}}$${\displaystyle n\geq 1}$

• Например, для универсальной машины Тьюринга T, множество пар (п, т) , такие , что Т останавливается на п , но не от т, в (будучи вычислимо с оракулом к проблемам остановки) , но не в ,.${\displaystyle \Delta _{2}^{0}}$${\displaystyle \Sigma _{1}^{0}\cup \Pi _{1}^{0}}$
• ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}=\Sigma _{0}^{0}\cup \Pi _{0}^{0}\subset \Delta _{1}^{0}}$. Включение строгое по определению, данному в этой статье, но тождество с выполняется при одном из вариантов определения, данного выше .${\displaystyle \Delta _{1}^{0}}$

Отношение к машинам Тьюринга [ править ]

Вычислимые множества [ править ]

Если S - вычислимое множество по Тьюрингу , то и S, и его дополнение рекурсивно перечислимы (если T - машина Тьюринга, дающая 1 для входных данных в S и 0, в противном случае мы можем построить машину Тьюринга, останавливающуюся только на первом, а другую - только на остановке. на последнем).

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

Аналогично, для каждого множества S in как S, так и его дополнение входят в и, следовательно, (по теореме Поста ) рекурсивно перечисляются некоторыми машинами Тьюринга T ₁ и T ₂ соответственно. Для каждого числа n ровно одна из этих остановок. Поэтому мы можем построить машину Тьюринга T, которая чередуется между T ₁ и T ₂ , останавливаясь и возвращая 1, когда первая останавливается, или останавливается и возвращает 0, когда последняя останавливается. Таким образом, T останавливается на каждом n и возвращает, находится ли он в S, поэтому S вычислим.${\displaystyle \Delta _{1}^{0}}$${\displaystyle \Sigma _{1}^{0}}$

Резюме основных результатов [ править ]

Вычислимые по Тьюрингу наборы натуральных чисел - это в точности наборы на уровне арифметической иерархии. Рекурсивно перечислимые множества - это в точности множества на уровне .${\displaystyle \Delta _{1}^{0}}$${\displaystyle \Sigma _{1}^{0}}$

Ни одна машина-оракул не способна решить свою собственную проблему остановки (применима разновидность доказательства Тьюринга). На самом деле проблема остановки для оракула заключается в этом .${\displaystyle \Delta _{n}^{0,Y}}$${\displaystyle \Sigma _{n+1}^{0,Y}}$

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

• Множество ( п - я Тьюринг скачки пустого множества) является много-один полным в .${\displaystyle \emptyset ^{(n)}}$${\displaystyle \Sigma _{n}^{0}}$
• Набор много-один комплектный .${\displaystyle \mathbb {N} \setminus \emptyset ^{(n)}}$${\displaystyle \Pi _{n}^{0}}$
• Набор является полным по Тьюрингу .${\displaystyle \emptyset ^{(n-1)}}$${\displaystyle \Delta _{n}^{0}}$

Полином иерархия является «выполним ресурсами ограничены» версией арифметической иерархии , в которой длина граница полиномиальной размещена на номерах участвующих (или, что эквивалентно, полиномиальные оценки времени помещается на тьюринговых машинах , участвующих). Он дает более тонкую классификацию некоторых наборов натуральных чисел, находящихся на уровне арифметической иерархии.${\displaystyle \Delta _{1}^{0}}$

Связь с другими иерархиями [ править ]

См. Также [ править ]

• Иерархия Леви
• Иерархия (математика)
• Логика интерпретируемости
• Полиномиальная иерархия

Ссылки [ править ]