Нормальные алгорифмы Маркова

Пусть А – произвольное непустое конечное множество, называемое алфавитом, и - два символа, не входящие в алфавит А. Множество A^* является множеством D_A возможных исходных данных нормального алгорифма Маркова A.

Определение. Нормальным алгорифмом Маркова (или просто алгорифмом) в алфавите А называется конечный линейно упорядоченный список A формул подстановок слов следующих двух типов:

(i) , (ii) , где .

Область применения алгоритма A:

1) если левая часть u хотя бы одной формулы из A является подсловом слова w, то выбираем первую такую формулу j в списке A и заменяем первое вхождение слова u в слово w на слово v, стоящее в правой части формулы j, и ставим точку перед полученным словом , если формула j содержит точку, т.е. является формулой типа (ii) . Если при этом j -типа (i), то пишем w |- и говорим, что A просто переводит w в , а если j -типа (ii), то пишем w |-× и говорим, что A заключительно переводит w в ;

2) если же никакая левая часть формул из A не является подсловом слова w, то слово не поддается алгорифму A;

Будем писать A(w)= в том и только том случае, если существует такая конечная последовательность слов , что

(1) ,

(2) алгорифм Aпросто переводит w_i в w_i₊₁для всех и

(3) w_n_-₁ |-× w_n.

Алгорифм A в алфавите называется алгорифмом над A.

Определение. Частичная словарная функция над алфавитом называется нормально вычислимой, если существует такой алгорифм A над алфавитом , что A( )=w тогда и только тогда, когда значение функции определено и выполняется равенство .

Понятие нормально вычислимой словарной функции удовлетворяет всем свойствам вычислимых функций, т.е. является адекватной моделью вычислений.

Рекурсивные функции

Пусть – множество неотрицательных целых чисел и F – множество всех частичных функций нескольких числовых переменных из со значениями в .

0-функция, функция следования, n–местная функция проекции на m–ую координату и определяются по формулам:

для любых значений .

Функции , , называются также простейшими примитивно рекурсивными функциями.

На множестве F всех частичных функций нескольких числовых переменных рассмотрим следующих два оператора:

- оператор суперпозиции S ставит в соответствие каждой функции m переменных fÎF и m функциям n переменных ÎF функцию n переменных , определяемую равенством:

;

- оператор примитивной рекурсии R ставит в соответствие каждой функции п+2 переменных fÎF и функции n переменных gÎF функцию n+1переменных , удовлетворяющую следующей схеме примитивной рекурсии:

В частности, при п = 0 схема примитивной рекурсии имеет следующий вид:

где а — постоянная одноместная функция, равная числу а.

Определение.

Функция fÎF называется примитивно рекурсивной (сокращенно ПРФ), если существует последовательность функций ÎF, в которой и всякая функция является простейшей ПРФ или получается из предыдущих функций с помощью оператора суперпозиции S или оператора примитивной рекурсии R.

Примеры.

1. Функция сложения х+у примитивно рекурсивна в силу схемы примитивной рекурсии:

2. Функция умножения примитивно рекурсивна в силу схемы примитивной рекурсии:

Определение.n-арное отношение называется примитивно рекурсивным (сокращенно ПРО), если примитивно рекурсивна его характеристическая функция

где - произвольный элемент множества .

Примеры. Отношения равенства х = у и делимости х|у примитивно рекурсивны, т.к. функции и примитивно рекурсивны.

Теорема 1.

Если отношения и примитивно рекурсивны, то отношения

, , ,

также примитивно рекурсивны.

Теорема 2.

Если отношение примитивно рекурсивно, то примитивно рекурсивными являются также отношения

, .

Примеры.

1. Так как , то отношение примитивно рекурсивно.

2. Так как , то отношение примитивно рекурсивно.

3. Множество всех простых чисел совпадает с примитивно рекурсивным унарным отношением

На множестве F всех частичных функций нескольких числовых переменных рассмотрим еще один оператор m, который называется оператором ограниченной минимизации:

каждой функции m переменных gÎF оператор m ставит в соответствие функцию m переменных f=m(g), определяемую равенством:

где правая часть равенства обозначает наименьшее решение уравнения относительно y.

Определение. Функция fÎF называется частично рекурсивной (сокращенно ЧРФ), если существует последовательность функций ÎF, в которой и всякая функция является простейшей ПРФ или получается из предыдущих функций с помощью оператора суперпозиции S, оператора примитивной рекурсии R или оператора ограниченной минимизации m.

При этом частично рекурсивная функция называется рекурсивной (сокращенно РФ), если она всюду определена, и общерекурсивной, если в определяющей ее последовательности ÎF все функции являются всюду определенными.

Множества всех рекурсивных, общерекурсивных, частично рекурсивных и примитивно рекурсивных функций из множества F обозначим соответственно F_РФ, F_ЧРФ, F_ОРФиF_ПРФ .

Из определений следуют включения множеств:

F_ПРФÌ F_ОРФÌ F_РФ ÌF_ЧРФ .

Известно, что F_ОРФ= F_РФ,

но все остальные включения являются собственными, т.е. F_ПРФ ¹ F_ОРФ, F_РФ ¹F_ЧРФ.

Определение.Подмножество A множества называется рекурсивным (или разрешимым), если его характеристическая функция частично рекурсивна.

Определение.Подмножество A множества называется рекурсивно перечислимым, если A является множеством значений некоторой частично рекурсивной функции.

Конечные пересечения и конечные объединения рекурсивно перечислимых множеств являются рекурсивно перечислимыми множествами, а дополнения рекурсивно перечислимых множеств в общем случае не будут рекурсивно перечислимыми.

Теорема об универсальной функции.

Пусть F₁ - множество всех частично рекурсивных функций f из N в N. Тогда найдется такая вычислимая функция G изN´Nв N, что для любой функции F₁ найдется такое nÎN, что f совпадает с частично рекурсивной функцией изNв N.

При этом уравнение определяет вычислимую функцию из N в N определяет частично рекурсивную функцию f из N в N, которая не имеет всюду определенного рекурсивного продолжения на все множество N.

Следствие. Существует рекурсивно перечислимое нерекурсивное множество.

Понятия рекурсивной функции и частично рекурсивной функции, а также рекурсивного множества и рекурсивно перечислимого множества естественно переносятся на словарные функции и языки над любым конечным алфавитом с помощью биекции l множества A^* на множество N,которая определяется по правилам:

и

для непустого слова .

Такая биекция l называется лексикографической функцией для алфавита A.

Лексикографическая функция l естественно продолжается на множество всех частичных словарных функций по правилу:

есть числовая функция из со значениями в , которая определяется уравнением

для значений .

Определение.

Частичная словарная функция называется частично рекурсивной (соответственно, рекурсивной или примитивно рекурсивной), если числовая функция частично рекурсивна (соответственно, рекурсивна или примитивно рекурсивна).

Определение.

Язык называется рекурсивным (соответственно, рекурсивно перечислимым), если числовое множество рекурсивно (соответственно, рекурсивно перечислимо).

Машины Тьюринга

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

Такие машины строго математически определяются следующим образом.

Определение.Машина Тьюринга Т - система, работающая в дискретные моменты времени t=0,1,2,... и состоящая из следующих частей:

1. Конечная лента, разбитая на конечное число ячеек, - внешня память машины. В каждый момент времени t в ячейках записаны буквы из алфавита - внешний алфавит машины. Ячейки, в которых записан символ 0, называются пустыми. В процессе работы машины: (1) ячейки ленты могут менять свои состояния путем замены записанных в них букв алфавита A на его другие буквы и (2) к существующим ячейкам ленты может пристраиваться неограниченное число дополнительных ячеек, которые изначально считаются пустыми.

Лента считается направленной и ее ячейки просматриваются слева направо. Таким образом, если в какой-то момент времени лента имеет r ячеек, то состояние ленты полностью описывается словом , где – состояние первой (слева) ячейки, – состояние второй ячейки и т.д.

2. Управляющая головка - устройство, которое может перемещаться вдоль ленты так, что в каждый рассматриваемый момент времени t оно находится напротив определенной ячейки и имеет некоторое состояние q_j из конечного множества внутренних состояний машины , Q∩А = Æ. Состояние q₀называется заключительным и означает завершение работы машины, а состояние q₁называется начальным и означает начало работы машины. Если головка в состоянии q_j находится напротив ячейки в состоянии a_i, то говорят, что машина просматривает эту ячейку или наблюдает ее состояние q_j.

В процессе работы машины управляющая головка: (1) может смещаться для просмотра соседних ячеек и (2) менять свои состояния путем замены записанных в ней букв алфавита Q на его другие буквы.

3. Список команд или программа P, представляющая собой последовательность выражений T(i,j)(где , ) вида:

- – означает сдвиг управляющей головки, находящейся в состоянии q_i напротив ячейки с буквой a_j, на одну ячейку влево с заменой состояния управляющей головки q_i на состояние q_l;

- – означает сдвиг управляющей головки, находящейся в состоянии q_i напротив ячейки с буквой a_j, на одну ячейку вправо с заменой состояния управляющей головки q_i на состояние q_l;

- – означает замену буквы a_j в ячейке, напротив которой находится управляющая головка в состоянии q_i, на букву a_k с одновременной заменой состояния управляющей головки q_i на состояние q_l .

Выражения T(i,j)называются командами.

При этом предполагается, что команды не могут начинаться со слов q₀a_j, содержащих символ заключительного состояния q₀, и что символы L,R не принадлежат множеству .

Машина Тьюринга Т - упорядоченная пятерка объектов Т=(A,Q,P,q₀,q₁).

Работа машины Т происходит под действием команд из множества P и заключается в изменении ее конфигураций, описывающих состояния ленты и управляющей головки, а также положение управляющей головки.

Если лента находится в состоянии, которое описывается словом над алфавитом A, и управляющая головка в состоянии q_i просматривает на ленте j-ую ячейку с состоянием a_j, то соответствующая конфигурация K машины Т описывается выражением , которое называется машинным словом.

Описывающие конфигурации K машинные слова являются словами над алфавитом , содержащие единственный символ алфавита , правее которого в слове непременно есть символ алфавита .

К называется начальной конфигурацией, если описывающее ее машинное слово содержит символ начального состояния q₁,и заключительной конфигурацией, если ее машинное слово содержит символ заключительного состояния q₀.

Изменение конфигураций К₀,К₁,К₂,… машины Т под действием команд из множества P происходит в дискретные моменты времени t = 0,1,2,... и описывается преобразованием соответствующих машинных слов M₀,M₁,M₂,…по следующему правилу.

За один шаг работы машины Т ее машинное слово под действием команды T(i,j) преобразуется в новое машинное слово М' по формулам:

, если и α=L,

, если и ,

, если и β=L,

, если и ,

, если .

Символически такое одношаговое преобразование машинных слов обозначается .

Если существует такая последовательность преобразований машинных слов (где ), для которой и , то пишут и говорят, что машинное слово М' получается из машинного слова М с помощью машины Т .

Если при этом во всех преобразованиях не достраиваются ячейки слева (соответственно, не достраиваются ячейки ни слева, ни справа), то пишут также (соответственно, ).

Для машинного слова М обозначим слово в редуцированном алфавите , которое получается из М вычеркиванием единственного вхождения буквы алфавита и всех вхождений пустого символа a₀=0.

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

В этом случае будем говорить, что машина Т применима к слову a, и результат переработки машиной Т такого слова a будем обозначать .

Если же машина Т слово не переводит в слово заключительной конфигурации, то будем говорить, что машина Т неприменима к слову a .

Пример.

Пусть машина Тьюринга Sимеет внешний алфавит , внутренний алфавит и программу P:

q₁0 → Rq₂, q₂0 → q₀1, q₁1 → Rq₁, q₂1 → Rq₂.

Тогда редуцированный алфавит имеет вид: и слово a=11машиной S перерабатываетсяв слово b=111, так как

и .

Машина S к любому слову над алфавитом приписывает справа символ 1.

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

Определение.

Частичная словарная функция f из в , зависящая от n переменных, называется вычислимой по Тьюрингу, если существует машина Тьюринга Т с внешним алфавитом , для которой при любых условие равносильно тому, что машина Т применима к слову и результат переработки машиной Т такого слова равен значению функции .

Теорема. Частичная словарная функция в том и только том случае будет вычислимой по Тьюрингу, если она является частично рекурсивной функцией.

Следствие.

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

Сложность вычислений

В качестве модели алгоритма рассматривается машина Тьюринга T, вычисляющая числовую функцию

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

Ленточной сложностью машины T называется функция значение которой равно числу ячеек машины T, используемых при вычислении значения и не определено, если не определено.

Если внешний алфавит A машины T состоит из m символов, множество внутренних состояний Q состоит из n элементов и значение определено, то справедливы неравенства:

Теорема Блюма об ускорении. Для любой рекурсивной функции существует такая рекурсивная функция с множеством значений что для любой машины Тьюринга T, вычисляющей функцию найдется такая машина Тьюринга , вычисляющая функцию что начиная с некоторого номера выполняется неравенство

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

Сложность алгоритмов

В качестве модели алгоритма рассматривается машина Тьюринга T, вычисляющая словарную функцию

Входное слово называется допустимым машиной M, если обрабатывая это слово машина M завершает работу в заключительном состоянии, и недопустимым в противном случае. Множество всех допустимых слов образует язык , который допускается (или распознается) машиной T.

В общем случае машина Тьюринга T допускает рекурсивно-перечислимый язык , который является областью определения рекурсивной функции

Язык называется рекурсивным, если рекурсивна его характеристическая функция , т.е. для некоторой машины Тьюринга T с функцией Такая машина удовлетворяет условиям:

1) если , то x – допустимое слово и, значит, при входе x машина T попадает в заключительное состояние, останавливается и выдает значение

2) если , то при входе x машина T останавливается в состоянии, не являющемся заключительным, и выдает значение

Если язык L рассматривается как кодировка проблемы P, то проблема P называется разрешимой, если она является рекурсивным языком, и неразрешимой в противном случае.

Машины такого типа соответствуют понятию «алгоритма» и применяются при решении распознавательных задач типа «да/нет».

Примеры.

1. Является ли выполнимым булев многочлен?

2. Изоморфны ли данные графы?

3. Имеет ли граф независимое множество вершин мощности k?

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

Для исследования сложности распознавательных задач далее рассматриваются машины Тьюринга T с рекурсивными языками

Говорят, что машина Тьюринга T имеет временную сложность (или «время работы »), если, обрабатывая вход длины п, T делает не более переходов и останавливается независимо от того, допущен вход или нет.

Определение. Говорят, что язык принадлежит классу P, если существует полином , при котором для некоторой детерминированной машины Тьюринга T с временной сложностью .

В частности, распознавательная задача принадлежит классу P, если ее язык принадлежит классу P, т.е. эта задача решается с помощью полиномиального алгоритма - некоторой детерминированной машины Тьюринга T с полиномиальной временной сложностью .

Пример. Задача существования для графа остова с весом не более числа k принадлежит классу P.

Определение. Язык принадлежит классу NP, если существует полином , при котором для некоторой недетерминированной машины Тьюринга T с временной сложностью .

В частности, распознавательная задача принадлежит классу NP, если ее язык принадлежит классу NP, т.е. эта задача решается с помощью полиномиального недетерминированного алгоритма - некоторой недетерминированной машины Тьюринга T с полиномиальной временной сложностью .

Пример. Задача выполнимости булева многочлена принадлежит классу NP.

Предыдущая 1 2 3 4 5 6 7 8 910Следующая

Не нашли, что искали? Воспользуйтесь поиском по сайту:

©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.