Лекции по теории алгоритмов. Лекция Интуитивное представление об алгоритме Интуитивное определение алгоритма. Примеры алгоритмов
 Скачать 2.84 Mb.
|
|
2. Нормальные алгорифмы Маркова
Пусть имеется произвольный алфавит A={a1, a2, a3,…am}, не содержащий пустой буквы1 и символов →, . Через A* будем обозначать множество слов над алфавитом A. Считается, что пустое слово входит в любое слово перед каждой его буквой. Это означает, например, что a1a2a3a5 и a1a2a3a5 – две записи одного и того же слова. Тот факт, что слово A* входит в слово A*2, фиксируется так: . В теории нормальных алгоритмов над словами определяются, операции, именуемые подстановками, в общем виде записываемыми в виде: → (,A*) (1) (,A*) (2) При этом подстановка (1) называется простой, подстановка (2) – заключительной. Результатом применения подстановки → к слову A* называют слово A*, полученное путем замены в слове первого вхождения слова на слово (в этом случае говорят, что подстановка → является активной на слове ). Если слово не входит в слово , то говорят, что подстановка → не является активной на слове . Например, если =a1a2a3a5, =a2a3, =a5, то результатом подстановки → на слове будет слово =a1a5a5. Определение 2.2.1. Линейно упорядоченная конечная последовательность подстановок вида (1) – (2) называется функциональной схемой нормального алгорифма. Таким образом, нормальный алгорифм M задается алфавитом и списком подстановок. Обычно этот список записывают в «столбик», считая упорядоченным сверху вниз. Применение нормального алгорифма Mкслову предполагает следующий порядок действий. 1. Задается исходное слово 0. 2. Полагается, что =0. 3. Просматривается сверху вниз список подстановок в поиске первой из них, активной на слове . 4. Если подстановок, активных на слове нет, то результатом работы нормального алгорифма над словом считается слово (M()=). Процесс применения алгорифма M к слову оканчивается. 5. Если найденная активная на слове подстановка оказывается заключительной, то она применяется к слову . Результат ее применения считается результатом применения всего алгорифма M к слову . Процесс применения алгорифма M к слову оканчивается. 6. Если найденная активная на слове подстановка оказывается простой, то она применяется к слову (результат применения обозначается как ). 7. Полагается, что = и осуществляется возврат к пункту 3. Если нормальный алгорифм оканчивается в пунктах 4 – 5, то говорят, что он применим к слову 0. В противном случае, если процесс никогда не оканчивается, говорят, что нормальный алгорифм Mне применим к слову 0. При этом возможны различные варианты. Так, например алгорифм M1 в алфавите A={0,1} c функциональной схемой: 010 1 10 → 00 1→ 11, применим к словам: а) 0=00 (M1(00)=00 – в функциональной схеме нет ни одной активной подстановки); б) 0=110 (M1(110)=000 – дважды применяется вторая подстановка); в) 0=010 (M1(010)=1 – применяется заключительная подстановка. Этот же алгорифм не применим к словам: 0=01; 0=1; 0=11 и т.д. Вот еще два примера, заимствованных нами из [ ]. Пример 2.2.1. Алгорифм M2 вычисления суммы чисел, записанных в унарной системе счисления в алфавите A1={1,+} в виде 11+1 или 111+11+1 и т.п., работающий в алфавите A2=A1{}, определяется следующей функциональной схемой: + → 1 → 1 → . Пример 2.2.2. Алгорифм M3, работающий над алфавитом A1={0,1} в алфавите A2=A1{, } и прибавляющий 1 к двоичному числу, имеет следующую функциональную схему: 1 → 1 0 → 0 → 1 → 0 0 1 1 → . Лекция № 3. Машины Тьюринга 1. Машины Тьюринга 2. Не распознаваемость самоприменимости машины Тьюринга
В состав любой машины Тьюринга входит бесконечная в обе стороны лента, разделенная на ячейки, и головка, способная передвигаться вдоль ленты вправо и влево (см. рис. 4).
– головка Рис. 4. Представление машины Тьюринга. В ячейку ленты может быть записана буква из алфавита A={a0, a1, a2, … an}. Для каждой машины Тьюринга этот алфавит, называемый внешним, вообще говоря, свой. Но принято резервировать символ a0 для обозначения пустой ячейки при определении внешнего алфавита любой машины. Будем также считать, что непустое слово в алфавите A–{a0} воспринимается любой машиной в стандартном положении, если головка находится напротив крайней справа ячейки ленты из тех, в которых записано слово1 (см. рис. 5).
– головка Рис. 3. Стандартное положение в машине Тьюринга (внешний алфавит A={a0, 0,1}) Работа любой машины Тьюринга осуществляется дискретным образом – шагами (тактами). В каждом такте головка располагается напротив какой-либо ячейки, «обозревая» ее. При этом она может «читать», имеющуюся в ячейке букву; записать в ячейку букву (из алфавита A),предварительно стерев старую; сдвигаться на одну ячейку влево или вправо. Полагается, что при каждом такте работы машина находится в каком-то состоянии, обозначаемом буквой qi из алфавита внутренних состояний – Q={q0, q1, q2, ….qm}. Каждая машина Тьюринга имеет свой собственный алфавит внутренних состояний, но принято считать, что символом q0 в таком алфавите обозначается состояние остановки, а символом q1 – начальное состояние. Из состояния q1 машина начинает работать, а попав в состояние q0,прекращает работу. Работа любой машины Тьюринга осуществляется по своей собственной программе или в соответствии с функциональной схемой, представляющей собой совокупность выражений T(i, j) (1im, 0jn, i,jZ), именуемыми командами, каждаяиз которыхможет иметь следующий вид (см. таблицу 1). Функциональная схема машины Тьюринга (программа) может быть записана в виде последовательности команд или в виде таблицы (см. пример 3.1.1). Таким образом, та или иная машина Тьюринга полностью определяется: а) внешним алфавитом A={a0, a1, a2, … an}; б) алфавитом внутренних состояний Q={q0, q1, q2, ….qm}; в) программой (функциональной схемой). Таблица 1
Говорят, что слово перерабатывается машиной Тьюринга в слово , если от слова , воспринимаемого в начальном состоянии q1, машина после выполнения конечного числа команд программы приходит к слову , воспринимаемому в положении остановки. Пример 3.1.1. Машина Тьюринга определяется функциональной схемой в виде следующей таблицы:
Слово, воспринимаемое в начальном состоянии q1 имеет вид:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
