Степень Тьюринга - Turing degree
В информатике и математической логике Тьюринг степень (названная в честь Алана Тьюринга ) или степени неразрешимости набора натуральных чисел измеряют уровень алгоритмической неразрешимости множества.
Обзор
Концепция степени Тьюринга является фундаментальной в теории вычислимости , где наборы натуральных чисел часто рассматриваются как проблемы принятия решений . Степень Тьюринга набора - это мера того, насколько сложно решить проблему принятия решения, связанную с набором, то есть определить, есть ли произвольное число в данном наборе.
Два набора эквивалентны по Тьюрингу, если они имеют одинаковый уровень неразрешимости; каждая степень Тьюринга представляет собой набор наборов, эквивалентных по Тьюрингу, так что два набора находятся в разных степенях Тьюринга именно тогда, когда они не эквивалентны по Тьюрингу. Кроме того, степени Тьюринга частично упорядочены, так что если степень Тьюринга набора X меньше, чем степень Тьюринга набора Y, то любая (невычислимая) процедура, которая правильно определяет, находятся ли числа в Y, может быть эффективно преобразована в процедуру, которая правильно решает , следует ли число в X . Именно в этом смысле степень Тьюринга множества соответствует его уровню алгоритмической неразрешимости.
Степени Тьюринга были введены Эмилем Леоном Постом (1944), и многие фундаментальные результаты были установлены Стивеном Коулом Клини и Постом (1954). С тех пор ученые степени Тьюринга стали предметом интенсивных исследований. Многие доказательства в этой области используют технику доказательства, известную как метод приоритета .
Эквивалентность Тьюринга
В остальной части этой статьи набор слов будет относиться к набору натуральных чисел. Множество X называется Тьюринг к множеству Y , если существует машина Тьюринга оракула , который решает членство в X , когда дается оракул для членства в Y . Обозначения Х ≤ Т У указывает на то, что Х является Тьюринга сводится к Y .
Два множества X и Y определены , чтобы быть Тьюринга эквивалентны , если Х является Тьюринга сводится к Y и Y является Тьюринга сводится к X . Обозначение X ≡ T Y указывает, что X и Y эквивалентны по Тьюрингу. Отношение ≡ T можно рассматривать как отношение эквивалентности , что означает, что для всех множеств X , Y и Z :
- Х ≡ Т Х
- X ≡ T Y влечет Y ≡ T X
- Если X ≡ T Y и Y ≡ T Z , то X ≡ T Z .
Тьюрингова степень представляет собой класс эквивалентности по отношению ≡ T . Обозначения [ Х ] обозначает класс эквивалентности , содержащий множество X . Обозначен весь набор степеней Тьюринга .
Тьюринга градусов имеют частичный порядок ≤ определен так , что [ Х ] ≤ [ Y ] тогда и только тогда , когда X ≤ T Y . Существует единственная степень Тьюринга, содержащая все вычислимые множества, и эта степень меньше любой другой степени. Он обозначается 0 (ноль), потому что это наименьший элемент чугуна . (Обычно для обозначения степеней Тьюринга используются жирные обозначения, чтобы отличать их от множеств. Когда не может возникнуть путаницы, например, с [ X ], жирный шрифт не нужен.)
Для любых множеств X и Y , X join Y, обозначенный как X ⊕ Y , определяется как объединение множеств {2 n : n ∈ X } и {2 m +1: m ∈ Y }. Степень Тюринга из X ⊕ Y является меньшей мере верхней границей степеней X и Y . Таким образом, получается джойн-полурешетка . Точная верхняя грань степеней a и b обозначается a ∪ b . Известно, что это не решетка , поскольку есть пары степеней без точной нижней границы.
Для любого множества X обозначение X 'обозначает набор индексов машин-оракулов, которые останавливаются (когда им задан индекс в качестве входных данных) при использовании X в качестве оракула. Множество X 'называется Тьюринг скачок в X . Скачок Тьюринга степени [ X ] определяется как степень [ X ']; это действительное определение , так как X '≡ T Y ' , когда X ≡ T Y . Ключевым примером является 0 ', степень проблемы остановки .
Основные свойства степеней Тьюринга
- Каждая степень Тьюринга счетно бесконечна , то есть содержит ровно множества.
- Есть разные степени Тьюринга.
- Для каждой степени a выполняется строгое неравенство a < a ′.
- Для каждой степени а , множество градусов ниже является счетным . Набор градусов больше a имеет размер .
Структура степеней Тьюринга
Было проведено множество исследований структуры степеней Тьюринга. В следующем обзоре перечислены только некоторые из многих известных результатов. Один общий вывод, который можно сделать из исследования, заключается в том, что структура степеней Тьюринга чрезвычайно сложна.
Свойства заказа
- Есть минимальные степени . Степень является минимальным , если не равен нулю и нет степени между 0 и . Таким образом, отношение порядка на степенях не является плотным порядком .
- Для любой ненулевой степени a существует степень b, несравнимая с a .
- Существует множество попарно несравнимых степеней Тьюринга.
- Есть пары степеней без точной нижней границы. Таким образом, это не решетка.
- Каждое счетное частично упорядоченное множество может быть вложено в степени Тьюринга.
- Никакая бесконечная строго возрастающая последовательность степеней не имеет точной верхней границы.
Свойства, связанные с прыжком
- Для каждой степени a существует степень строго между a и a ′ . На самом деле существует счетное семейство попарно несравнимых степеней между a и a ′ .
- Прыжковая инверсия: степень a имеет вид b ′ тогда и только тогда, когда 0 ′ ≤ a .
- Для любой степени a существует такая степень b , что a < b и b ′ = a ′ ; такая степень b называется низкой по отношению к a .
- Существует бесконечная последовательность a i степеней, такая что a ′ i +1 ≤ a i для каждого i .
Логические свойства
- Симпсон (1977) показал , что теория первого порядка из на языке ⟨≤, =⟩ или ⟨≤ ', =⟩ это много-один эквивалент к теории истинной арифметики второго порядка . Это указывает на то, что структура чрезвычайно сложна.
- Шор и Сламан (1999) показали, что оператор скачка определим в структуре первого порядка с языком ⟨≤, =⟩ .
Рекурсивно перечислимые степени Тьюринга
Степень называется рекурсивно перечислимой (пере), если она содержит рекурсивно перечислимое множество . Каждая степень re ниже 0 ′ , но не каждая степень ниже 0 ′ является re.
- ( GE Sacks , 1964) Число степеней плотное; между любыми двумя степенями есть третья степень.
- (AH Lachlan, 1966a и CEM Yates, 1966) Существуют две повторные степени, у которых нет наибольшей нижней границы.
- (AH Lachlan, 1966a и CEM Yates, 1966) Существует пара ненулевых re степеней, точная нижняя граница которых равна 0 .
- (AH Lachlan, 1966b) Не существует пары re степеней, точная нижняя граница которых равна 0, а наименьшая верхняя граница равна 0 ' . Этот результат неофициально называется неалмазной теоремой .
- (С. К. Томасон, 1971) Каждую конечную дистрибутивную решетку можно вложить в re степени. Фактически, счетная безатомная булева алгебра может быть вложена таким образом, чтобы сохранить верхнюю и нижнюю границу .
- (AH Lachlan and RI Soare , 1980) Не все конечные решетки могут быть вложены в re степени (посредством вложения, сохраняющего верхнюю и нижнюю границу). Справа показан конкретный пример.
- ( Л. Харрингтон и Т. Сламана см НИЕС, Шор, Сламана (1998)) Теория первого порядка повторных градусов на языке ⟨ 0 , ≤, =⟩ является много-один эквивалент теории истинного первого порядка арифметика .
Проблема поста и метод приоритета
Эмиль Пост изучил повторные степени Тьюринга и спросил, существует ли какая-либо степень re строго между 0 и 0 ′ . Проблема построения такой степени (или демонстрации того, что ее не существует) стала известна как проблема Поста . Эта проблема была независимо решена Фридбергом и Мучником в 1950-х годах, которые показали, что эти промежуточные степени действительно существуют. В каждом из их доказательств был разработан один и тот же новый метод построения повторных степеней, который стал известен как метод приоритета . Метод приоритета в настоящее время является основным методом получения результатов о сбросах.
Идея приоритетного метода построения набора X состоит в том, чтобы перечислить счетную последовательность требований, которым X должен удовлетворять. Например, чтобы построить набор X между 0 и 0 ′, достаточно удовлетворить требованиям A e и B e для каждого натурального числа e , где A e требует, чтобы машина оракула с индексом e не вычисляла 0 ′ из X и B е требует, чтобы машина Тьюринга с индексом е (и не оракул) не вычисляет X . Эти требования размещены в порядке приоритета , который является явным взаимно однозначным соответствием требований и натуральных чисел. Доказательство проводится индуктивно, с одним этапом для каждого натурального числа; эти этапы можно рассматривать как шаги времени , в течение которого множество X перечисляется. На каждом этапе числа могут быть помещены в X или навсегда исключены возможность ввода X в попытке удовлетворить требования (то есть заставить их удерживаться после того, как все X будут перечислены). Иногда число может быть пронумеровано в X, чтобы удовлетворить одно требование, но выполнение этого может привести к тому, что ранее выполненное требование станет неудовлетворенным (то есть будет повреждено ). Порядок приоритета требований используется для определения того, какое требование следует удовлетворить в этом случае. Неформальная идея состоит в том, что если требование нарушено, оно в конечном итоге перестанет быть поврежденным после того, как перестают быть поврежденными все требования с более высоким приоритетом, хотя не каждый аргумент приоритета имеет это свойство. Необходимо аргументировать, что весь набор X исправен и удовлетворяет всем требованиям. Аргументы приоритета могут быть использованы для доказательства многих фактов о сбросах; используемые требования и способ их выполнения должны быть тщательно выбраны для получения требуемого результата.
Смотрите также
использованная литература
- Монографии (бакалавриат)
- Купер С.Б. Теория вычислимости . Chapman & Hall / CRC, Бока-Ратон, Флорида, 2004. ISBN 1-58488-237-9
- Катленд, Н. Вычислимость. Издательство Кембриджского университета, Кембридж-Нью-Йорк, 1980. ISBN 0-521-22384-9 ; ISBN 0-521-29465-7
- Монографии и обзорные статьи (для выпускников)
- Амбос-Спис, К., Фейер, П. Степени неразрешимости. Не опубликовано. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
- Лерман М. Степени неразрешимости. Перспективы математической логики. Springer-Verlag, Берлин, 1983. ISBN 3-540-12155-2
- Odifreddi, PG (1989), Классическая теория рекурсии , Исследования в области логики и основ математики, 125 , Амстердам: Северная Голландия, ISBN 978-0-444-87295-1, Руководство по ремонту 0982269
- Одифредди, П. Г. (1999), Классическая теория рекурсии. Vol. II , Исследования по логике и основам математики, 143 , Амстердам: Северная Голландия, ISBN 978-0-444-50205-6, MR 1718169
- Роджерс, Х. Теория рекурсивных функций и эффективная вычислимость , MIT Press. ISBN 0-262-68052-1 , ISBN 0-07-053522-1
- Сакс, Джеральд Э. Степени неразрешимости (Анналы математических исследований), Princeton University Press. ISBN 978-0-6910-7941-7
- Симпсон, С. Степени неразрешимости: обзор результатов. Справочник по математической логике , Северная Голландия, 1977, стр. 631–652.
- Шенфилд, Джозеф Р. Степени неразрешимости , Северная Голландия / Эльзевир, ISBN 978-0-7204-2061-6 .
- Шор, Р. (1993). «Теории степеней T, tt и wtt: неразрешимость и не только». В Univ. Nac. дель Сур, Баия Бланка (ред.). Материалы IX латиноамериканского симпозиума по математической логике, часть 1 (Bahía Blanca, 1992) . Notas Lógica Mat. 38 . С. 61–70.
- Соаре Р. Рекурсивно перечислимые множества и степени. Перспективы математической логики. Springer-Verlag, Берлин, 1987. ISBN 3-540-15299-7
- Соаре, Роберт I. Рекурсивно перечислимые множества и степени. Бык. Амер. Математика. Soc. 84 (1978), нет. 6, 1149–1181. Руководство по ремонту 508451
- Научно-исследовательские работы
- Клини, Стивен Коул ; Сообщение, Эмиль Л. (1954), "Верхний полу-решетки степеней рекурсивной неразрешимости", Анналы математики , Вторая серия, 59 (3): 379-407, DOI : 10,2307 / 1969708 , ISSN 0003-486X , JSTOR 1969708 , Руководство по ремонту 0061078
- Лахлан, AH (1966a), "Нижние границы для пар рекурсивно перечислимых степеней", Труды Лондонского математического общества , 3 (1): 537–569, CiteSeerX 10.1.1.106.7893 , doi : 10.1112 / plms / s3-16.1 .537 .
- Lachlan, AH (1966b), "Невозможность найти относительные дополнения для рекурсивно перечислимых степеней", J. Symb. Бревно. , 31 (3): 434-454, DOI : 10,2307 / 2270459 , JSTOR 2270459 .
- Лахлан, AH; Соар Р.И. (1980), «Не всякая конечная решетка вложима в рекурсивно перечислимые степени», Успехи в математике , 37 : 78–82, DOI : 10.1016 / 0001-8708 (80) 90027-4 .
- Нис, Андре; Шор, Ричард А .; Сламана, Теодор А. (1998), "Интерпретируемость и определимость в перечислимых степеней", Труды Лондонского математического общества , 77 (2): 241-291, CiteSeerX 10.1.1.29.9588 , DOI : 10,1112 / S002461159800046X , ISSN 0024-6115 , Руководство MR 1635141
- Сообщение, Эмиль Л. (1944), «перечислимых множеств натуральных чисел и их проблемы решения», Бюллетень Американского математического общества , 50 (5): 284-316, DOI : 10,1090 / S0002-9904-1944-08111- 1 , ISSN 0002-9904 , MR 0010514
- Мешки, GE (1964), "The рекурсивно перечислимые степени плотны", Анналы математики , Вторая серия, 80 (2): 300-312, DOI : 10,2307 / 1970393 , JSTOR 1970393 .
- Шор, Ричард А .; Сламана, Теодор А. (1999), "Определение скачка Тьюринга", Математический Research Letters , 6 (6): 711-722, DOI : 10,4310 / mrl.1999.v6.n6.a10 , ISSN 1073-2780 , МР 1739227
- Симпсон, Стивен Г. (1977), "Теория первого порядка степеней рекурсивной неразрешимости", Анналы математики , второй серии, 105 (1): 121-139, DOI : 10,2307 / 1971028 , ISSN 0003-486X , JSTOR 1971028 , Руководство по ремонту 0432435
- Томасон, С. К. (1971), "Подрешетки рекурсивно перечислимых степеней", Z. Math. Logik Grundlag. Математика. , 17 : 273-280, DOI : 10.1002 / malq.19710170131 .
- Йейтс, СЕМ (1966), "Минимальная пара рекурсивно перечислимых степеней", журнал символической логики , 31 (2): 159-168, DOI : 10,2307 / 2269807 , JSTOR 2269807 .