Введение в математическую логику и теорию алгоритмов Лекция 14 Алексей Львович Семенов

2 План Ансамбли (напоминание) Действия, проверки Алгоритмы Вычислимые функции Универсальный алгоритм, универсальная функция Диагональ (напоминание) Диагональ невычислимости Исчисления (напоминание) Связь между проводимостью и вычислимостью Разрешимость Непородилость Грамматики (напоминание) Алгоритмы Маркова Тезис Поста (напоминание) Тезис Чёрча

3 Ансамбли (напоминание) Цепочка = конечная последовательность, которая может быть и пустой – Λ. Длина цепочки – число элементов в ней. Алфавит = цепочка различных символов Слово (в данном алфавите) – цепочка символов этого алфавита. Ансамбль слов в данном алфавите – все слова. Часто алфавит: 0 1 Ансамбль цепочек слов в данном алфавите – все цепочки слов. Ансамбль списков в данном алфавите – все слова и все цепочки списков (индуктивное определение): – 011; (01,0); (0, ((01,0), 0))…

44 Ансамбль двоичных слов Двоичные слова – слова в алфавите 0, 1 Линейный порядок: Λ, 0, 1, 00, 01, 10, 11, 000, 001,… Слова получают номера: 1, 2, 3… (их тоже можно писать как двоичные числа) Кодирование слов в произвольном алфавите двоичными словами Цепочки слов и списки могут кодироваться словами (в произвольном алфавите)

5 Действия и проверки. Описания Действие – исходное понятие. Действие: Слово на каком-то языке, человек понимает, что значит применить это слово к любому исходному данному из фиксированного ансамбля, при этом ясно, что всегда получается результат (применения) – элемент (возможно, другого) фиксированного ансамбля; применить слово может и подходящее устройство. Действие задает всюду (на данном ансамбле) определенную функцию Проверка – действие с результатом 0 или 1 Проверка задает характеристическую функцию множества (где она дает 1), она допускает его элементы (а другие – не допускает) 5

66 Алгоритмы Алгоритм – цепочка вида А Пока Б В Г где А, В, Г – действия, Б – проверка. А - начало Б - продолжение В - переработка Г - извлечение результата.

77 Применение алгоритма к исходному данному x – это (конечная или бесконечная) последовательность: x 0, x 1, …, x n, …, получаемая так: x 0 – это x x 1 – это результат применения Начала А к x 0 при i>0 к уже полученному x i нужно применить Продолжение Б. Затем: – если проверка Б дает 1, то к x i применить Переработку В; то, что получится, и есть x i+1. – если проверка Б дает 0, то к x i применить Извлечение результата Г, результат этого применения является последним в последовательности. Результат применения алгоритма к x – последний элемент последовательности. Действия (в том числе – проверки) всегда дают результат Задача. Когда алгоритм не дает результат?

8 Вычислимые функции Алгоритм задает (вычисляет) функцию, возможно, не всюду определенную Функция, вычисляемая каким-то алгоритмом, называется вычислимой. Говорят также, что алгоритм является ее описанием. Одно из основных понятий данного курса и математики

99 Универсальные алгоритм и функция Фиксирован язык алгоритмов. Можно считать, что алфавит = {0, 1}. Универсальный алгоритм: Начало: выясняет, является ли исходное данное кодом пары, где первый элемент – это код алгоритма, если да, выделяем в первом элементе – алгоритме P, его составные части и применяем Начало P если нет, то результат. Продолжение: Если на входе, то 1, иначе Продолжение P Переработка: Если на входе, то, иначе Переработка P Извлечение результата : Извлечение результата P Универсальная функция: У ( P, x ) = P(x).

Диагонали (повторение) В квадратной таблице выписано (по горизонтали) конечное число цепочек. Как построить цепочку, которой нет в таблице?

11 Диагональ (конечная) чл.посл. посл Взять диакональ и испортить её в каждом члене. Например, прибавляем 1 и получаем t(i,j) – это элемент, стоящий в i–ой строке и j–ом столбце. Цепочка a(i) = t(i,i) +1. Пусть она в строке c. Тогда t(с,с) = t(с,с) +1. Противоречие.

12 Диагональ несчетности (Кантора) Функция, которой нет в таблице – это (1 – t(i,i)), не t(i,i), нули заменили на единицы, единицы – на нули. Аргумент характ. функции … …

13 Существуют ли невычислимые функции? Сколько есть вычислимых функций? Не больше, чем алгоритмов. Не больше, чем слов. -Счетное количество -Всех функций – несчетное.

14 Диагональ невычислимости Аргумент Функция 0101…1111 0… 1… …01 ………………… …(диак) 10 Имена строк и столбцов – (непустые) слова. В клетке (i,j) – значение функции с описанием i на аргументе j. Если значения нет, оставим клетку пустой:

15 Диагональ невычислимости Аргумент Функция 0101…1111 0… 1… … 01 ……… … …… … …10 «Диагональная» функция t(i,i) вычислима. Вычислима и «испорченная диакональ» d(i), которая равна нулю, если t(i,i) > 0, и равна 1, если t(i,i) = 0. Задача. Есть ли d в таблице?

16 Диагональ невычислимости Задача. Может ли функция d(i,i) быть всюду определенной? Задача. Можно ли продолжить функцию d(i,i) до всюду определенной? Задача. Можно ли продолжить функцию d(i,i) до вычислимой всюду определенной?

17 Исчисления (напоминание) Исчисление в данном ансамбле – это пара из двух проверок:. проверка создания применяется к цепочке объектов, проверка окончания – к объекту. создаваемый исчислением объект определяется так: Если проверка создания допускает цепочку объектов a 1,… a n и все элементы этой цепочки, кроме последнего – создаваемы, то и последний элемент создаваем. Если проверка создания допускает цепочку из одного элемента, то его называют начальным объектом (в некоторых контекстах – аксиомой).

18 Фиксирован какой-то ансамбль Объект порождаем данным исчислением, если он создаваем и его допускает проверка окончания. Исчисление порождает множество из всех порождаемых им объектов – множество, порождаемое этим исчислением. Порождение – «недетерминированный процесс» – возможность, разрешение чего-то: если цепочка допускается проверкой создания, то ее последний элемент разрешается создать «из предыдущих» (если предыдущие созданы) Исчисления. Породимые множества

19 Фиксируем исчисление. Если a 1, …, a n – допускается проверкой создания, то говорим. что a n создается из a 1, …, a n-1 (в данном исчислении). Вывод объекта a – цепочка объектов S, каждый из которых создается из какой-то цепочки объектов, встретившихся в S раньше него. Задача. Объект создаваем тогда и только тогда, когда имеется его вывод. Задача. Пусть дано исчисление. Как организовать процесс выписывания всех выводов? Задача. Пусть дано исчисление. Как организовать процесс выписывания всех порождаемых (в нем) объектов (и только их)? Выводы

20 Порождение Объект порождаем, если существует его вывод и для объекта выполнена проверка окончания Можно перейти к кодам Существует алгоритм, который по любому элементу проверяет, является ли оно кодом вывода, и: – если не является, то не дает результата (вариант – дает всегда один и тот же фиксированный результат) – если является, то дает порождаемое выводом слово

21 Породимые множества Породимое множество – множество, порождаемое каким-то исчислением. Теоремы замкнутости для исчислений Т. Объединение и пересечение по родимых множеств породимы.

22 Перечислимые множества О. Перечислимое множество – это множеством значений вычислимой функции. Задача. Следующие свойства множества эквивалентны: 1. Оно – перечислимо 2. Оно – область определения вычислимой функции 3. Оно – породило Можно указать общие способы (алгоритмы) построения по любому из описаний 1 – 3 любого другого.

23 Замечание. Есть действие S, для которого: множество {Λ, S(Λ), S(S(Λ)),…} содержит все элементы ансамбля. Задача. Перечислимое множество пусто или является множеством значений всюду определенной вычислимой функции. Задача. Имея описание 1 – 3 такое описание всюду определенной функции не построить!

24 Определение вычислимости через перечислимость Задача. Функция вычислима ее график перечислим (породим) Вычислимость можно определить через породилость.

25 Разрешимые множества О. Множество разрешимо, если его характеристическая функция вычислима Задача. Множество разрешимо оно и его дополнение перечислимы Задача. Бывает ли перечислимое множество с неперечислимым дополнением? Вариант: номера функций, у которых на диаконали – непустая клетка?

26 Грамматики (напоминание)( Хомский) Определение. Грамматика Γ – это цепочка Σ – основной алфавит Γ Ω – вспомогательный алфавит Γ S – начальный символ Γ ΣΩ=Ø, объединение Σ и Ω – это алфавит Γ, обозначим его Δ. Π – это конечное множество пар слов в алфавите Δ. Эти пары называются заменами.

27 Грамматика определяет исчисление Γ* Проверка создания Γ* допускает: S – Всякий вывод в исчислении начинается с S. Для каждой замены из Π, все пары вида, где t,p – произвольные слова в алфавите Δ – Один шаг вывода состоит в замене в слове некоторого входящего в него u на v. Проверка окончания для грамматики Γ допускает все слова в алфавите Σ. – Порождаемые слова не могут содержать букв из вспомогательного алфавита. Код грамматики - слово в конечном алфавите (можно считать 0 1).

28 Алгоритмы Маркова Определение. Задание алгоритма Маркова – это цепочка Ф = Σ, Δ, Π, где Σ – основной алфавит Ф, у нас {0,1}, Σ Δ, П – цепочка слов вида u v или u v – замен Ф; u, v – в алфавите Δ ;, Δ, u называется левой частью замены, v – правой. Замены, содержащие, называются заключительными.

29 Алгоритмы Маркова Какой алгоритм определяется этим заданием? – Дан объект – слово Начало: – не требуется делать ничего – тождественное преобразование объекта. Продолжение: – 0, если нет ни одной замены, левая часть которой входит в объект, или в объекте есть ; иначе 1. Переработка: – Найти первую замену, левая часть которой входит в объект, найти первое ее вхождение в объект и заменить его на правую часть этой замены. Извлечение результата: – Стереть в слове все символы, которые есть.

30 Пример: Алфавит из трех символов: 0, 1 и дополнительного символа | (палочки). Цепочка замен: |0 0|| 1 0| 0 Исходный объект: 101. Работа алгоритма: 0|01 00||1 00||0| 00|0||| 000||||| 00||||| 0||||| ||||| Андрей Марков мл. (9 [22] – )

31 Тезис Поста (напоминание). Всякое породилое множество порождается некоторой грамматикой.

32 Тезис Черча (вариант). Всякая вычислимая функция вычислима некоторым алгоритмом Маркова. Алонзо Чёрч ( )

33 Алгоритмические проблемы Проблемы построения алгоритмов Проблема построения алгоритма разрешения – вычислимость характеристической функции 10-ая Проблема Гильберта Построить алгоритм, который по всякому алгебраическому уравнению от нескольких неизвестных с целыми коэффициентами выясняет, есть ли у него решение в целых числах. Отрицательное решение: Юрий Матиясевич ( )