Степень Тьюринга - Turing degree

В информатике и математической логике Тьюринг степень (названная в честь Алана Тьюринга ) или степени неразрешимости набора натуральных чисел измеряют уровень алгоритмической неразрешимости множества.

Обзор

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

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

Степени Тьюринга были введены Эмилем Леоном Постом (1944), и многие фундаментальные результаты были установлены Стивеном Коулом Клини и Постом (1954). С тех пор ученые степени Тьюринга стали предметом интенсивных исследований. Многие доказательства в этой области используют технику доказательства, известную как метод приоритета .

Эквивалентность Тьюринга

В остальной части этой статьи набор слов будет относиться к набору натуральных чисел. Множество X называется Тьюринг к множеству Y , если существует машина Тьюринга оракула , который решает членство в X , когда дается оракул для членства в Y . Обозначения ХТ У указывает на то, что Х является Тьюринга сводится к Y .

Два множества X и Y определены , чтобы быть Тьюринга эквивалентны , если Х является Тьюринга сводится к Y и Y является Тьюринга сводится к X . Обозначение XT Y указывает, что X и Y эквивалентны по Тьюрингу. Отношение ≡ T можно рассматривать как отношение эквивалентности , что означает, что для всех множеств X , Y и Z :

  • ХТ Х
  • XT Y влечет YT X
  • Если XT Y и YT Z , то XT Z .

Тьюрингова степень представляет собой класс эквивалентности по отношению ≡ T . Обозначения [ Х ] обозначает класс эквивалентности , содержащий множество X . Обозначен весь набор степеней Тьюринга .

Тьюринга градусов имеют частичный порядок ≤ определен так , что [ Х ] ≤ [ Y ] тогда и только тогда , когда XT Y . Существует единственная степень Тьюринга, содержащая все вычислимые множества, и эта степень меньше любой другой степени. Он обозначается 0 (ноль), потому что это наименьший элемент чугуна . (Обычно для обозначения степеней Тьюринга используются жирные обозначения, чтобы отличать их от множеств. Когда не может возникнуть путаницы, например, с [ X ], жирный шрифт не нужен.)

Для любых множеств X и Y , X join Y, обозначенный как XY , определяется как объединение множеств {2 n  : nX } и {2 m +1: mY }. Степень Тюринга из XY является меньшей мере верхней границей степеней X и Y . Таким образом, получается джойн-полурешетка . Точная верхняя грань степеней a и b обозначается ab . Известно, что это не решетка , поскольку есть пары степеней без точной нижней границы.

Для любого множества X обозначение X 'обозначает набор индексов машин-оракулов, которые останавливаются (когда им задан индекс в качестве входных данных) при использовании X в качестве оракула. Множество X 'называется Тьюринг скачок в X . Скачок Тьюринга степени [ X ] определяется как степень [ X ']; это действительное определение , так как X '≡ T Y ' , когда XT 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 степеней, такая что ai +1a i для каждого i .

Логические свойства

Рекурсивно перечислимые степени Тьюринга

Конечная решетка, которую нельзя вложить в re-степени.

Степень называется рекурсивно перечислимой (пере), если она содержит рекурсивно перечислимое множество . Каждая степень 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
Научно-исследовательские работы