Эффективная перечислимость и распознаваемость множеств

Июль 23, 2022

Главная
Математика
Эффективная перечислимость и распознаваемость множеств

Содержание

2. Определения Эффективно перечислимым множеством называется множество, элементы которого можно перечислить по алгоритму (пронумеровать натуральным рядом без
3. Теорема Поста Если множество А эффективно перечислимо, то подмножество В эффективно распознается в А тогда и
4. Теорема Поста достаточность Пусть B и А\B эффективно перечислимы. Множества В и А\B представляет собой набор
5. Теорема Поста Для каждого элемента запустим параллельно алгоритмы перечисления В и А\В (поочерёдно по одному элементу
6. Теорема Множество машин Тьюринга эффективно перечислимо. Доказательство: Идея: описать произвольную машину Тьюринга некоторым числом, которое эффективно
7. Произведём кодировку. Для этого перечислим и пронумеруем состояния (символы внутреннего алфавита) и закодируем их единичками: Эффективное
8. Пронумеруем ленточные знаки (символы внешнего алфавита) и закодируем их двойками: Символы, определяющие движение управляющей головки получат
9. Эффективное перечисление машин Тьюринга Например, А а ? b L B ?? 111222422223311115. Поменяем местами символы
10. Теперь можно убрать “4” и “5”, тогда получим 222111222233111, тем самым уменьшив длину кода (данный шаг
11. Теорема Множество алгоритмов Маркова эффективно перечислимо. Доказательство: Идея: описать произвольный алгоритм некоторым числом, которое эффективно распознаётся
12. Произведём кодировку: Нормальный алгоритм представляет собой набор строк, например: ab → c Λ ? d •
13. Если мы возьмем ряд простых чисел и каждое из них возведём в какую-нибудь степень, а затем
14. Возьмём первую строчку алгоритма Маркова и представим её следующим образом: a b → c 24 •
15. Далее формируем кодовое число всего алгоритма. Для этого выпишем ряд простых чисел и возведем каждое число
16. Теперь возьмем ряд натуральных чисел и применим к нему алгоритм распознавания, определяющий является ли данное число
17. Доказательство: Возьмем множество машин, останавливающихся на первом такте, и пронумеруем их: T11,T12,T13,T14… Затем пронумеруем множество машин,
18. Используя диагональный метод, перечислим их (пронумеруем натуральными числами): Таким образом, каждая останавливающаяся машина Тьюринга получит свой
19. Доказательство: Предположим противное, а именно, что множество не останавливающихся машин эффективно перечислимо. Тогда используем Теорему Поста,
21. Скачать презентацию

Слайд 2

Определения
Эффективно перечислимым множеством называется множество, элементы которого можно перечислить по алгоритму

(пронумеровать натуральным рядом без пропусков и повторений).

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

Слайд 3

Теорема Поста
Если множество А эффективно перечислимо, то подмножество В эффективно

распознается в А тогда и только тогда, когда В и А\В оба эффективно перечислимы.
Доказательство: необходимость
Пусть В распознается в А. Множество А представляет собой набор элементов А={a1,a2,…}. Вытаскиваем ∀ элемент ai из множества A.
Если ai∈B, то нумеруем его в B,
Если ai∉B, то нумеруем его в А\B.
Т.к. A эффективно перечислимо, то таким образом будут вытащены все его элементы. Таким образом эффективно перечислены множества B и А\B.

Слайд 4

$Теорема Поста достаточность Пусть B и А\B эффективно перечислимы. Множества В$

Теорема Поста
достаточность
Пусть B и А\B эффективно перечислимы.
Множества В и

А\B представляет собой набор элементов B={x1,x2,…} и A\B={y1,y2,…}.
В силу того, что множества В и А\В эффективно перечислимы, существуют алгоритмы их перечисления. Т.к. A эффективно перечислимо, то начнем перечислять его элементы ai.

Слайд 5

Теорема Поста
Для каждого элемента запустим параллельно алгоритмы перечисления В и

А\В (поочерёдно по одному элементу из каждого множества) и будем сравнивать элементы множеств с ai.
Так как ai принадлежит либо В, либо А\В, то он встретится на каком-то конечном шаге перечисления. Таким образом, можно определить, к какому множеству он относится, а значит, В эффективно распознается в А, Q.E.D.

Слайд 6

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

которое эффективно распознаётся среди натуральных чисел. Тогда, применив алгоритм распознавания к натуральному ряду, удастся перенумеровать все машины Тьюринга. А это будет означать, что они эффективно перечислимы.

Эффективное перечисление машин Тьюринга

Слайд 7

Произведём кодировку. Для этого перечислим и пронумеруем состояния (символы внутреннего алфавита)

и закодируем их единичками:

Эффективное перечисление машин Тьюринга

Слайд 8

Пронумеруем ленточные знаки (символы внешнего алфавита) и закодируем их двойками:
Символы,

определяющие движение управляющей головки получат коды, состоящие из троек. Стрелку в строке таблицы обозначим четверкой, а разделитель между строк (переход на новую строку), обозначим пятеркой.

Эффективное перечисление машин Тьюринга

Слайд 9

Эффективное перечисление машин Тьюринга
Например,
А а ? b L B ??

111222422223311115.
Поменяем местами символы элемента алфавита и состояния (в левой части), получим:
a A ? b L B ?? 22211142222331115.

Слайд 10

Теперь можно убрать “4” и “5”, тогда получим 222111222233111, тем самым

уменьшив длину кода (данный шаг не является обязательным). Таким образом, каждой машине Тьюринга сопоставлено натуральное число.
Теперь возьмем ряд натуральных чисел и применим к нему алгоритм распознавания, определяющий, является ли данное число кодом какой-либо машины Тьюринга. Если в результате проверки выясняется, что данный формат допустим, то соответствующему числу присваивается очередной свободный номер. Т.о. каждая машина Тьюринга получит свой собственный номер, следовательно, такие машины эффективно перечислимы, Q.E.D.

Эффективное перечисление м. Тьюринга - доказательство

Слайд 11

Теорема
Множество алгоритмов Маркова эффективно перечислимо.
Доказательство:
Идея: описать произвольный алгоритм некоторым

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

Эффективное перечисление алгоритмов Маркова

Слайд 12

Произведём кодировку:
Нормальный алгоритм представляет собой набор строк, например:
ab → c
Λ ?

d •
Пронумеруем символы алфавита. Первые три символа служебные, для них зарезервируем числа 1,2,3.
→ ”1”
Λ ”2”
• ”3”
Остальные символы получают следующие вакантные номера:
a (x1) ”4”
b (x2) ”5”
c (x3) ”6”
. . . .
(xk) “k+3”

Доказательство

Слайд 13

Если мы возьмем ряд простых чисел и каждое из них возведём

в какую-нибудь степень, а затем их перемножим, то по полученному числу мы сможем сказать, в какой именно степени были соответствующие простые числа. Это делается путем деления получившегося числа поочередно на простые числа, начиная с двойки, до тех пор, пока возможно деление без остатка. Потом производится деление на 3, потом на 5 и т.д. до тех пор, пока не получится единица.
2x • 3y • 5z •…=N
Например, мы можем рассчитать степени, в которые были возведены простые числа, произведение которых образует 540:
540=2x • 3y • 5z
540/2 = 270; 270/2 = 135; 135/3 = 45;
45/3 = 15; 15/3 = 5; 5/5 = 1
Двойка участвовала в делении 2 раза, тройка – 3 раза, пятерка – 1 раз. Проверим: 22 • 33 • 51 = 4 • 27 • 5 = 540

Отступление (из области свойств простых чисел)

Слайд 14

Возьмём первую строчку алгоритма Маркова и представим её следующим образом:
a b

→ c
24 • 35 • 51 • 76 = A
Полученное натуральное число A является кодом данной строчки (такая нумерация называется Гёделевой).
Аналогично поступаем со второй строчкой алгоритма:
Λ → d •
22 • 31 • 57 • 73 = B
B является кодом второй строчки.

Геделева нумерация

Слайд 15

Далее формируем кодовое число всего алгоритма. Для этого выпишем ряд простых

чисел и возведем каждое число в соответствующую этой строчке степень.
2A, 3B, …
Перемножив эти числа, получим кодовый номер алгоритма.
2A • 3B … = К
Таким образом, алгоритм представлен в виде произведения простых чисел, взятых в степенях, соответствующих коду каждой строки. Полученное число К является кодом данного алгоритма. При этом по данному коду можно восстановить полностью весь алгоритм.

Геделева нумерация

Слайд 16

Теперь возьмем ряд натуральных чисел и применим к нему алгоритм распознавания,

определяющий является ли данное число кодом какого либо алгоритма Маркова. Такой алгоритм распознавания будет состоять из двух процедур: сначала по данному числу К вычисляются числа А, B, C… (коды строк), а затем из этих чисел извлекаются соответствующие x, y, z,… (коды символов в рамках каждой строки). Полученные значения проверяются на предмет соответствия формату строк алгоритмов Маркова. Если ответ положительный, то соответствующему числу К присваивается очередной свободный номер. Т.о. каждый алгоритм Маркова получит свой собственный номер, следовательно, нормальные алгоритмы эффективно перечислимы, Q.E.D.

Доказательство

Слайд 17

Доказательство:
Возьмем множество машин, останавливающихся на первом такте, и пронумеруем их:
T11,T12,T13,T14…
Затем

пронумеруем множество машин, останавливающихся на втором такте:
T21,T22,T23,T24…
Аналогично, на третьем такте:
T31,T32,T33,T34…, и т.д.
Затем расположим их в виде бесконечной матрицы.

Теорема
Множество останавливающихся машин Тьюринга эффективно перечислимо.

Слайд 18

Используя диагональный метод, перечислим их
(пронумеруем натуральными числами):
Таким образом, каждая

останавливающаяся машина
Тьюринга получит свой собственный номер. Отсюда следует, что останавливающиеся машины можно эффективно перечислить, Q.E.D.

Доказательство

Слайд 19

Доказательство:
Предположим противное, а именно, что множество не останавливающихся машин эффективно перечислимо.

Тогда используем Теорему Поста, которая гласит, что подмножество В эффективно перечислимого множества А эффективно распознается в нем тогда и только тогда, когда это подмножество и его дополнение до всего множества эффективно перечислимы.
Пусть множество А – это множество всех машин Тьюринга (оно эффективно перечислимо), а подмножество В - это множество останавливающихся машин Тьюринга (оно эффективно перечислимо).

Теорема
Множество не останавливающихся машин Тьюринга невозможно эффективно перечислить.

Эффективная перечислимость и распознаваемость множеств

Содержание

Определения Эффективно перечислимым множеством называется множество, элементы которого можно перечислить по алгоритму

Теорема ПостаЕсли множество А эффективно перечислимо, то подмножество В эффективно

Теорема ПостадостаточностьПусть B и А\B эффективно перечислимы. Множества В и

Теорема ПостаДля каждого элемента запустим параллельно алгоритмы перечисления В и

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

Произведём кодировку. Для этого перечислим и пронумеруем состояния (символы внутреннего алфавита)

Пронумеруем ленточные знаки (символы внешнего алфавита) и закодируем их двойками: Символы,

Эффективное перечисление машин Тьюринга Например,А а ? b L B ??

Теперь можно убрать “4” и “5”, тогда получим 222111222233111, тем самым

ТеоремаМножество алгоритмов Маркова эффективно перечислимо. Доказательство:Идея: описать произвольный алгоритм некоторым

Произведём кодировку:Нормальный алгоритм представляет собой набор строк, например: ab → c Λ ?

Если мы возьмем ряд простых чисел и каждое из них возведём

Возьмём первую строчку алгоритма Маркова и представим её следующим образом:a b

Далее формируем кодовое число всего алгоритма. Для этого выпишем ряд простых

Теперь возьмем ряд натуральных чисел и применим к нему алгоритм распознавания,

Доказательство:Возьмем множество машин, останавливающихся на первом такте, и пронумеруем их:T11,T12,T13,T14… Затем

Используя диагональный метод, перечислим их (пронумеруем натуральными числами): Таким образом, каждая

Доказательство:Предположим противное, а именно, что множество не останавливающихся машин эффективно перечислимо.

Похожие презентации

Определения
Эффективно перечислимым множеством называется множество, элементы которого можно перечислить по алгоритму

Теорема Поста
Если множество А эффективно перечислимо, то подмножество В эффективно

Теорема Поста
достаточность
Пусть B и А\B эффективно перечислимы.
Множества В и

Теорема Поста
Для каждого элемента запустим параллельно алгоритмы перечисления В и

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

Пронумеруем ленточные знаки (символы внешнего алфавита) и закодируем их двойками:
Символы,

Эффективное перечисление машин Тьюринга
Например,
А а ? b L B ??

Теорема
Множество алгоритмов Маркова эффективно перечислимо.
Доказательство:
Идея: описать произвольный алгоритм некоторым

Произведём кодировку:
Нормальный алгоритм представляет собой набор строк, например:
ab → c
Λ ?

Возьмём первую строчку алгоритма Маркова и представим её следующим образом:
a b

Доказательство:
Возьмем множество машин, останавливающихся на первом такте, и пронумеруем их:
T11,T12,T13,T14…
Затем

Используя диагональный метод, перечислим их
(пронумеруем натуральными числами):
Таким образом, каждая

Доказательство:
Предположим противное, а именно, что множество не останавливающихся машин эффективно перечислимо.