Вычисление по Тьюрингу функций
Рассмотрим расширенный натуральный ряд: , рассмотрим функции от переменных , где
Такие функции называются частичными функциями счётнозначной логики. Множество функций .
Если область определения функции совпадает со всем , то тогда называется всюду определенной.
Пусть , ; закодируем числа натурального ряда: , тогда слово будем записывать на ленте
Определение: говорят, что функция вычислима по Тьюрингу, если существует машина Тьюринга, работающая в алфавите и обладающая следующими свойствами:
1. Если набор - область определения и , то машина Тьюринга применима к слову в начальной конфигурации
2. Если , то машина не применима к слову в начальной конфигурации, то есть начиная работу над словом она начинает циклить.
Рекурсивные функции:
1. 0 – функция:
2. Функция следования
3. Оператор проектирования
Введем следующие операции:
1. Операция суперпозиции:
…
2. Примитивная рекурсия
3. Процедура взятия оператора
Ищем следующим образом:
Определение: функция называется частично рекурсивной, если она может быть получена из простейших функций: 0 – функции, функции следования, функции выбора переменной, с помощью конечного числа применений суперпозиций примитивной рекурсии и взятия оператора. Если функция всюду определена и частична рекурсивна, она называется общерекурсивной функцией.
Теорема: всякая частично рекурсивная функция вычислима по Тьюрингу и наоборот: всякая вычислимая по Тьюрингу функция является частично рекурсивной.
Определение: множество называется общерекурсивным, если оно совпадает с множеством значений некоторой общерекурсивной функции (например множество чётных чисел).
Определение: рассмотрим некоторое множество , которое является подмножеством некоторого множества, тогда характеристической функцией данного множества
Определение: множество называется рекурсивным, если его характеристическая функция частично рекурсивная.
Теорема: всякое рекурсивное множество является общерекурсивным.
Нормальные алгоритмы Маркова.
Рассмотрим некоторую совокупность символов – алфавит , - слово, – пустое слово.
Определение: Марковской подстановкой называется операция, которая записывается , которая ищет первое вхождение слова в некоторое слово и заменяет слово на слово .
– если дальше продолжаем работу
– окончание работы после
Работа алгоритма происходит следующим образом: рассматривается слово и ищется первое , если ни одно из не является подсловом , то в этом случае алгоритм не начинает свою работу, иначе и получаем новое слово . Если эта подстановка была заключительной, то останавливаемся и результат , иначе начинаем работу сначала, но уже с .
Определение: функция, заданная на некотором множестве слов алфавита называется нормально вычислимой, если существует такое расширение данного алфавита и такой нормальный алгоритм Маркова, работающий над словами алфавита , который каждое слово из области определения функции преобразует слово в , такое, что .
Принципы нормализации алгоритма Маркова:
Для нахождения значений функции в некотором алфавите тогда и только тогда существует алгоритм, когда функция нормально вычислима.
Теорема: следующие классы функций (заданы на расширенном натуральном ряде и принимают значения с расширенного натурального ряда) совпадают:
1. Класс функций, вычислимых по Тьюрингу
2. Класс частично рекурсивных функций
3. Класс нормально вычислимых функций
Неразрешимые алгоритмические проблемы:
1. Проблема распознавания выводимости в математической логике: для любых двух формул и в логическом исчислении узнать, существует ли дедуктивная цепочка, ведущая от формулы к формуле
Теорема Чёрча: проблема распознавания выводимости алгоритмически не разрешима.
2. Проблема распознавания самоприменимости.
– код символа.
- код команды.
Тогда наша программа – совокупность команд
На вход машины Тьюринга Т отправляем
1) если машина Тьюринга применима к своему коду – самопримаенимая
2) если начиная работу над своим кодом машина Тьюринга циклит – несамоприменимая
Таким образом все машины Тьюринга, работающие в алфавите делятся на 2 класса: самоприменимые и несамоприменимые.
Проблема самоприменимости состоит в следующем: построить такой алгоритм, который по коду машины Тьюринга Т давал бы однозначный ответ самоприменима машина Т или нет (без запуска).
Для решения проблемы необходимо построить машину в алфавите , которая, работая над кодом машины Тьюринга Т, останавливалась и выдавала 1, самоприменима, или 0.
Теорема: проблема самоприменимости алгоритмически не разрешена.
Доказательство: предположим противное: пусть существует машина , решающая проблему самоприменимости. Опираясь на неё, построим машину Тьюринга , которая:
1) применима к кодам несамоприменимых машин Тьюринга,
2) не применима к кодам самоприменимых машин Тьюринга.
Для этого:
1) все команды машины объявляем командами машины ;
2) заключительное состояние машины объявляем не заключительным для машины ;
3) добавляем заключительное состояние для и команды:
Машина работает над кодами всех машин, в том числе и на своим.
Пусть
1) машина Тьюринга самоприменима, то есть применима к своему коду, но она не применима к кодам самоприменимых машин, значит является несамоприменимой.
Получено противоречие.
2) машина Тьюринга несамоприменима, но она применима к кодам несамоприменимых машин, значит самоприменима.
Получено противоречие.
3. Проблема применимости.
Машина Тьюринга работает в алфавите , - слово. Требуется по коду машины Тьюринга Т и слову определить, применима ли машина Тьюринга к слову или нет. В разработке такого алгоритма и заключается проблема применимости: построить машину Тьюринга , на вход которой поступает . В результате 1, если машина применима, иначе 0.
Теорема: проблема применимости алгоритмически неразрешима.
Доказательство: предположим противное: пусть машину Тьюринга можно построить, тогда наш код - это машина . Подадим слово , тогда машина решала бы проблему самоприменимости, а она алгоритмически неразрешима.
4. Проблема определения общей рекурсивности алгоримов, т.е. проблема определения того, ко всяким ли допустимым в начале данным применим данный алгоритм.
алгоритм. Нужно построить , на вход которой бы поступал номер алгоритма . В результате: 1 – алгоритм всюду определён, 0 – алгоритм не является общим.
Лемма: для любого перечисления любого множества общерекурсивных функций существует функция, не входящая в это перечисление.
Доказательство: рассмотрим все общерекурсивные функции и функцию
𝐹 общерекурсивная.
Будем предполагать, что , тогда в нашем перечислении имеет номер , тогда совпадает с , но . Получено противоречие.
Теорема: проблема определения общерекурсивных функций алгоритмически неразрешима.
Доказательство: предположим противное: пусть алгоритм , решающий проблему, существует, тогда он определяет общерекурсивную функцию . На основании построим общерекурсивную функцию следующего вида:
Построенная функция перечисляет все общерекурсивные функции, а так как множество общерекурсивных функций не является счётным, то получили противоречие.
Теория графов.
Основные понятия и определения.
Графом называется пара , , где - это множество вершин (в начальном варианте считается конечным и непустым), - бинарное отношение, заданное на , - множество дуг. Элементы множества - упорядоченные пары – дуги, где - начало, - конец.
Вершины, соединённые дугой, называют инцидентными дуге. Между собой – смежными (соединенными одной дугой).
Дуги, имеющие общую вершину, - смежные.
Граф называется ориентированным (орграфом), если
Если в этом случае граф называют неориентированным (неоргаф).
- ребро, без направления.
Если необходимо представить объекты, связанные несколькими связями, используют мультиграф.
Граф, не содержащий кратных дуг и петель называется простым графом.
Если дугам или вершинам необходимо приписать числа, то речь идёт о взвешенном графе.
Для взвешенного графа :
- функция распределения меток вершин, - множество значений; - функция распределения меток дуг, - множество значений.
Простой граф, в котором каждая пара вершин является смежной, называется полным графом.
Пусть , если , то тогда это множество подмножеств называется покрытием .
Граф называется двудольным, если существует такое разбиение множества вершин на два подмножества (доли), что концы каждого ребра принадлежат разным подмножествам (долям), если при этом любые две вершины, входящие в разные дуги, являются смежными, то граф называется полным двудольным графом.
Полный двудольный граф, содержащий в одной доле один элемент – звезда.
Рассмотрим графы , .
Графы называются гомоморфными, если существует отображение (гомоморфизмом) со свойством:
Если , то - изоморфизм, а графы и изоморфные.