Вычисление по Тьюрингу функций
Рассмотрим расширенный натуральный ряд: , рассмотрим функции от переменных , где Такие функции называются частичными функциями счётнозначной логики. Множество функций . Если область определения функции совпадает со всем , то тогда называется всюду определенной. Пусть , ; закодируем числа натурального ряда: , тогда слово будем записывать на ленте Определение: говорят, что функция вычислима по Тьюрингу, если существует машина Тьюринга, работающая в алфавите и обладающая следующими свойствами: 1. Если набор - область определения и , то машина Тьюринга применима к слову в начальной конфигурации 2. Если , то машина не применима к слову в начальной конфигурации, то есть начиная работу над словом она начинает циклить. Рекурсивные функции: 1. 0 – функция: 2. Функция следования 3. Оператор проектирования Введем следующие операции: 1. Операция суперпозиции: 2. Примитивная рекурсия 3. Процедура взятия оператора Определение: функция называется частично рекурсивной, если она может быть получена из простейших функций: 0 – функции, функции следования, функции выбора переменной, с помощью конечного числа применений суперпозиций примитивной рекурсии и взятия оператора. Если функция всюду определена и частична рекурсивна, она называется общерекурсивной функцией. Теорема: всякая частично рекурсивная функция вычислима по Тьюрингу и наоборот: всякая вычислимая по Тьюрингу функция является частично рекурсивной. Определение: множество называется общерекурсивным, если оно совпадает с множеством значений некоторой общерекурсивной функции (например множество чётных чисел). Определение: рассмотрим некоторое множество , которое является подмножеством некоторого множества, тогда характеристической функцией данного множества Определение: множество называется рекурсивным, если его характеристическая функция частично рекурсивная. Теорема: всякое рекурсивное множество является общерекурсивным. Рассмотрим некоторую совокупность символов – алфавит , - слово, – пустое слово. – окончание работы после Работа алгоритма происходит следующим образом: рассматривается слово и ищется первое , если ни одно из не является подсловом , то в этом случае алгоритм не начинает свою работу, иначе и получаем новое слово . Если эта подстановка была заключительной, то останавливаемся и результат , иначе начинаем работу сначала, но уже с . Определение: функция, заданная на некотором множестве слов алфавита называется нормально вычислимой, если существует такое расширение данного алфавита и такой нормальный алгоритм Маркова, работающий над словами алфавита , который каждое слово из области определения функции преобразует слово в , такое, что . Принципы нормализации алгоритма Маркова: Для нахождения значений функции в некотором алфавите тогда и только тогда существует алгоритм, когда функция нормально вычислима. Теорема: следующие классы функций (заданы на расширенном натуральном ряде и принимают значения с расширенного натурального ряда) совпадают: 1. Класс функций, вычислимых по Тьюрингу 2. Класс частично рекурсивных функций 3. Класс нормально вычислимых функций Неразрешимые алгоритмические проблемы: 1. Проблема распознавания выводимости в математической логике: для любых двух формул и в логическом исчислении узнать, существует ли дедуктивная цепочка, ведущая от формулы к формуле 2. Проблема распознавания самоприменимости. 3. Проблема применимости. 4. Проблема определения общей рекурсивности алгоримов, т.е. проблема определения того, ко всяким ли допустимым в начале данным применим данный алгоритм.
Теория графов. Основные понятия и определения. Графом называется пара , , где - это множество вершин (в начальном варианте считается конечным и непустым), - бинарное отношение, заданное на , - множество дуг. Элементы множества - упорядоченные пары – дуги, где - начало, - конец. Вершины, соединённые дугой, называют инцидентными дуге. Между собой – смежными (соединенными одной дугой). Дуги, имеющие общую вершину, - смежные. Граф называется ориентированным (орграфом), если - ребро, без направления. Если необходимо представить объекты, связанные несколькими связями, используют мультиграф. Граф, не содержащий кратных дуг и петель называется простым графом. Если дугам или вершинам необходимо приписать числа, то речь идёт о взвешенном графе. Для взвешенного графа : Простой граф, в котором каждая пара вершин является смежной, называется полным графом. Пусть , если , то тогда это множество подмножеств называется покрытием . Граф называется двудольным, если существует такое разбиение множества вершин на два подмножества (доли), что концы каждого ребра принадлежат разным подмножествам (долям), если при этом любые две вершины, входящие в разные дуги, являются смежными, то граф называется полным двудольным графом. Полный двудольный граф, содержащий в одной доле один элемент – звезда. Рассмотрим графы , . Графы называются гомоморфными, если существует отображение (гомоморфизмом) со свойством:
Если , то - изоморфизм, а графы и изоморфные.
Популярное: Почему стероиды повышают давление?: Основных причин три... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (2008)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |