В теории вычислимости теорема Поста , названная в честь Эмиля Поста , описывает связь между арифметической иерархией и степенями Тьюринга .
Задний план
В формулировке теоремы Поста используются несколько концепций, относящихся к теории определимости и рекурсии . В этом разделе дается краткий обзор этих концепций, которые подробно рассматриваются в соответствующих статьях.
В арифметической иерархии классифицирует определенные наборы натуральных чисел, которые определимы в языке арифметики Пеано. Формула называетсяесли это экзистенциальное утверждение в предварительной нормальной форме (все кванторы впереди) счередование экзистенциальных и универсальных кванторов, применяемых только к формулам с ограниченными кванторами . Формально формула на языке арифметики Пеано - это формула, если она имеет вид
где содержит только ограниченные кванторы, а Q -если м четно иесли m нечетное.
Набор натуральных чисел как говорят если это определяется формула, то есть если есть формула так что каждое число в если и только если держит. Известно, что если набор тогда это для любой , но для каждого m существует набор, который не . Таким образом, количество изменений квантора, необходимое для определения набора, дает меру сложности набора.
Теорема Поста использует релятивизированную арифметическую иерархию, а также только что определенную нерелятивизированную иерархию. Множество натуральных чисел называется относительно набора , написано , если определяется формула на расширенном языке, которая включает предикат для членства в .
В то время как арифметическая иерархия измеряет определимость множеств натуральных чисел, степени Тьюринга измеряют уровень невычислимости множеств натуральных чисел. Множествоназывается тьюринговым сводимым к множеству, написано , если существует машина Тьюринга оракула, которая, учитывая оракул для, Вычисляет характеристическую функцию из. Тьюринг скачок множестваявляется формой проблемы остановки относительно. Учитывая набор, скачок Тьюринга - это набор индексов оракульных машин Тьюринга, которые останавливаются при вводе при запуске с оракулом . Известно, что каждый комплект сводится по Тьюрингу к своему скачку Тьюринга, но скачок Тьюринга множества никогда не сводится по Тьюрингу к исходному множеству.
Теорема Поста использует конечно итерированные скачки Тьюринга. Для любого набора натуральных чисел, обозначение указывает на –Кратный повторный скачок Тьюринга . Таким образом просто , а также это скачок Тьюринга .
Теорема Поста и следствия
Теорема Поста устанавливает тесную связь между арифметической иерархией и степенями Тьюринга формы , то есть конечно итерированные скачки Тьюринга пустого множества. (Пустое множество можно заменить любым другим вычислимым множеством без изменения истинности теоремы.)
Теорема Поста гласит:
- Множество является если и только если это перечислимое с помощью оракула машины Тьюринга с оракулом для, то есть тогда и только тогда, когда является .
- Набор является -полный на каждый . Это означает, что каждыймножество много-одно сводится к.
Теорема Поста имеет множество следствий, которые раскрывают дополнительные связи между арифметической иерархией и степенями Тьюринга. Это включает:
- Исправить набор . Множество является если и только если является . Это релятивизация первой части теоремы Поста к оракулу..
- Множество является если и только если . В более общем смысле, является если и только если .
- Набор определяется как арифметический, если он для некоторых . Теорема Поста показывает, что, эквивалентно, множество арифметично тогда и только тогда, когда оно сводится по Тьюрингу кдля некоторых м .
Доказательство теоремы Поста.
Формализация машин Тьюринга в арифметике первого порядка
Работа машины Тьюринга на входе может быть формализована логически в арифметике первого порядка . Например, мы можем использовать символы , , а также для конфигурации ленты, состояния машины и расположения на ленте после шаги соответственно. «S система перехода определяет соотношение между а также ; их начальные значения (для) являются входом, начальным состоянием и нулем соответственно. Машина останавливается тогда и только тогда, когда есть номер такой, что состояние остановки.
Точное соотношение зависит от конкретной реализации понятия машины Тьюринга (например, их алфавита, разрешенного режима движения по ленте и т. Д.)
В случае останавливается во времени , связь между а также должно выполняться только для k, ограниченного сверху .
Таким образом, существует формула в арифметике первого порядка без неограниченных кванторов , таких что останавливается при вводе вовремя самое большее, если и только если доволен.
Пример реализации
Например, для машины Тьюринга без префиксов с двоичным алфавитом и без пустого символа мы можем использовать следующие обозначения:
- - это однозначный символ конфигурации всей ленты послешагов (которые мы можем записать как число с младшим битом первым, значение m-го места на ленте является его m-м младшим значащим битом). В частности - начальная конфигурация ленты, соответствующая входу в машину.
- - это одномерный символ состояния машины Тьюринга послешаги. В частности,, начальное состояние машины Тьюринга.
- - это однозначный символ, обозначающий расположение машины Тьюринга на ленте послешаги. В частности.
- - функция перехода машины Тьюринга, записанная как функция от дублета (состояние машины, бит, прочитанный машиной) к триплету (новое состояние машины, бит, записанный машиной, +1 или -1 движение машины по ленте ).
- это j-й бит числа . Это можно записать как арифметическую формулу первого порядка без неограниченных кванторов.
Для машины Тьюринга без префиксов мы можем использовать для ввода n начальную конфигурацию лентыгде кошка означает конкатенацию; таким образом это длина строки с последующим а затем .
Работа машины Тьюринга на первых порах шаги, таким образом, могут быть записаны как сочетание начальных условий и следующих формул, количественно выраженных по для всех :
- . Поскольку M имеет конечную область определения, ее можно заменить бескванторной арифметической формулой первого порядка . Точная формула, очевидно, зависит от M.
- . Обратите внимание, что при первом шаги никогда не достигает места на ленте больше, чем . Таким образом, универсальный квантор над J может быть ограничен по+1, поскольку биты за пределами этого местоположения не имеют отношения к работе машины.
T останавливается при вводе вовремя самое большее, если и только если выполнено, где:
Это арифметическая формула первого порядка без неограниченных кванторов, т.е. .
Рекурсивно перечислимые множества
Позволять - множество, которое может быть рекурсивно перечислено машиной Тьюринга . Тогда есть машина Тьюринга это для каждого в , останавливается, когда дается как вход.
Это можно формализовать с помощью арифметической формулы первого порядка, представленной выше. Члены числа удовлетворяющий следующей формуле:
Эта формула находится в . Следовательно, в . Таким образом, каждое рекурсивно перечислимое множество находится в.
Верно и обратное: для каждой формулы в с помощью k экзистенциальных кванторов, мы можем перечислить –Наборы натуральных чисел и запустите машину Тьюринга, которая перебирает их все, пока не обнаружит, что формула удовлетворяется. Эта машина Тьюринга останавливается в точности на множестве натуральных чисел, удовлетворяющих, и таким образом перечисляет соответствующее ему множество.
Машины Oracle
Точно так же и работа машины-оракула с оракулом O, который останавливается самое большее после шаги на входе можно описать формулой первого порядка , за исключением того, что формула теперь включает:
- Новый предикат, , давая ответ оракула. Этот предикат должен удовлетворять некоторой формуле, которая будет рассмотрена ниже.
- Дополнительная лента - лента оракула - на которой должен записывать число m для каждого обращения O (m) к оракулу; запись на этой ленте может быть логически формализована аналогично записи на магнитной ленте машины. Обратите внимание, что машина оракула, которая останавливается не более чем через шаги успевает написать самое большее цифры на ленте оракула. Таким образом, оракул можно вызвать только с числами m, удовлетворяющими.
Если оракул за решение проблемы, всегда равно «Да» или «Нет», которые мы можем формализовать как 0 или 1. Предположим, что сама проблема решения может быть формализована арифметической формулой первого порядка. . потом останавливается на самое большее после шаги тогда и только тогда, когда выполняется следующая формула:
где формула первого порядка без неограниченных кванторов.
Прыжок Тьюринга
Если O - оракул проблемы остановки машины , тогда то же самое, что и "существует такой, что начиная с входа m находится в состоянии остановки после шаги ». Таким образом: где формула первого порядка, формализующая . Если машина Тьюринга (без оракула), в (т.е. у него нет неограниченных кванторов).
Поскольку существует конечное число чисел m, удовлетворяющих , мы можем выбрать для всех одинаковое количество шагов: есть число , так что останавливается после шаги именно по этим входам для чего он вообще останавливается.
Переходя к предварительной нормальной форме , мы получаем, что машина оракула останавливается при вводе тогда и только тогда, когда выполняется следующая формула:
(неформально есть «максимальное количество шагов» такой каждый оракул, который не останавливается на первом шаги не останавливаются вообще; однако для каждого, каждый оракул, останавливающийся после шаги останавливаются).
Обратите внимание, что мы можем заменить оба а также одним числом - их максимумом - без изменения истинностного значения . Таким образом, мы можем написать:
Для оракула проблемы остановки машин Тьюринга в а также в . Таким образом, каждый набор, рекурсивно перечисляемый оракульной машиной с оракулом для, в .
Верно и обратное: предположим формула в с участием экзистенциальные кванторы, за которыми следуют универсальные кванторы. Эквивалентно, имеет > экзистенциальные кванторы, за которыми следует отрицание формулы в ; последняя формула может быть перечислена машиной Тьюринга и, таким образом, может быть немедленно проверена оракулом на предмет.
Таким образом, мы можем перечислить –Наборы натуральных чисел и запустить машину оракула с оракулом для который проходит через все, пока не находит удовлетворение для формулы. Эта машина-оракул останавливается в точности на множестве натуральных чисел, удовлетворяющих, и таким образом перечисляет соответствующее ему множество.
Высшие прыжки Тьюринга
В более общем смысле, предположим, что каждый набор, который рекурсивно перечисляется оракульной машиной с оракулом для в . Затем для машины оракула с оракулом для, в .
С такой же как для предыдущего прыжка Тьюринга его можно построить (как мы только что сделали с выше) так что в . После перехода к формальной форме prenex новый в .
По индукции каждый набор, который рекурсивно перечислим с помощью оракула с оракулом для , в .
Другое направление также может быть доказано по индукции: предположим, что каждая формула в можно перечислить с помощью машины оракула с оракулом для .
Теперь предположим формула в с участием экзистенциальные кванторы, за которыми следуют универсальные кванторы и т. д. имеет > экзистенциальные кванторы, за которыми следует отрицание формулы в ; последняя формула может быть перечислена машиной оракула с оракулом для и, таким образом, может быть немедленно проверен оракулом на предмет .
Таким образом, мы можем перечислить –Наборы натуральных чисел и запустить машину оракула с оракулом для который проходит через все, пока не находит удовлетворение для формулы. Эта машина-оракул останавливается в точности на множестве натуральных чисел, удовлетворяющих, и таким образом перечисляет соответствующее ему множество.
Рекомендации
Роджерс, Х. Теория рекурсивных функций и эффективная вычислимость , MIT Press. ISBN 0-262-68052-1 ; ISBN 0-07-053522-1
Соаре, Р. Рекурсивно перечислимые множества и степени. Перспективы математической логики. Springer-Verlag, Берлин, 1987. ISBN 3-540-15299-7