В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций) (1159492), страница 3
Текст из файла (страница 3)
Следовательно и в любойдругой момент времени лента будет иметь лишь конечное число ячеек,содержащих непустые символы.Активной зоной конфигурации назовем минимальную связную частьленты, содержащую обозреваемую ячейку, а также все ячейки, в которыхзаписаны непустые символы.Конфигурацию можно представить в виде машинного слова в алфавитеA Q видаUгдеqiα 1qi α 2(2)- внутреннее состояние ,α 1 - слово из символов алфавита А ,находящеесяв левой части активной зоны от считывающей головки,Конфигурация Кназывается заключительной , есликонфигурация имеет видq1αq i = q1 .Условимся.
что стандартная начальная, а стандартная заключительная имеет видq0α .Конфигурацию в момент времени t обозначим Kt .Машина реализуетпроцесс изменения конфигураций в следующем смысле. ЕслиK0 = q i αиα = аi α′ , ai ∈ A ,то в программе машины имеется точно одна команда видаq1ai → q k al d .Тогда следующая конфигурацияK 1 определяется так :K1 = q k al α ′ ,если d=EK1 = al qkα ′,если d=RK1 = q k a0 al α ′,если d=LЭто обстоятельство записываем в виде: K0→ K1 Если теперь конфигурацияK1 , не является заключителькой, то в соответствии с системой команд,аналогично предыдущему, определима однозначно следующая конфигурацияK2 т.е.
K1 → K2 .Таким образом начальная конфигурация K0 порождаетпоследовательность конфигурацийK0 → K1 → K2 →...→ Kt → Kt +1 →...(3)Если последовательность (3) конечна , т.е. обрывается в заключительнойконфигурации ,то говорят , что машина применима к конфигурации K0 , впротивном случае неприменима кK0 .9К0 = q1α и Kt = α ′q0α ′′ заключительной конфигурация ,то слово β = α ′α ′′ об`является результатомработы машины на слове α . Т.о.
машине Тьюринга соответствует частичнаяЕсли машина применима к конфигурациисловарная функция с областью определения и областью значения , являющейсяконечными словами в алфавите А , которая каждому такому слову ставит всоответствие результат применения машины к данному слову.Потребуем , чтобы заключительные конфигурации машины находились встандартной форме. Этого всегда можно добиться , добавляя к машине Т двановых состояния q ′ , q ′′ и командыq0ai → q ′ai L i=0...mq ′a0 → q ′′a0 RПри этом состояние q ′′ объявим заключительным. Полученная машинаT ′ эквивалентна машине T в следующем смысле:а) Обе машины применимы к одним и тем же начальным конфигурациям.б) Результаты применения обеих машин совпадают.в) Заключительные конфигурации у машины T ′ находятся в стандартной форме.Определим теперь вычисление функций на машине Тьюринга.
Будем**рассматривать словарные частичные функции f типа f: A → A где А* множество всех слов конечной длины в алфавите АГоворят, что машина Тьюринга Т правильно вычисляет частичнуюфункцию f , если для любого p ∈А* выполнено:1) Еслиf ( P)определено иf ( P) =Q, то машина Т применима кначальной конфигурации q1 P и заключительной конфигурацией являетсяKt = q 0 Q.f ( P)конфигурации q1 P .2) Еслине определено, то машина Т неприменима к начальнойФункция f называется правильно вычислимой по Тьюрингу, еслисуществует машина Тьюринга Т , которая ее правильно вычисляет.Аналогичные определения могут быть сделаны и для функций несколькихпеременных.
Для этого достаточно множество слов, являющихся аргументами,записать в виде одного слова, введя знак-разделитель. Ограничимсясоответствующим определением для числовых функций. Рассмотрим частичнуюфункцию f ( x1 ,..., xn ) от n переменных, аргументы которой и ее значенияпринадлежат множеству N0={0,1,2,...}. Будем считать, что алфавит А машины Тсодержит элемент 1 . Условимся произвольное число x ∈ N0 представлять в... 1...1, чтобы запись нуля была непустой.
Будем говорить, чтовиде слов x +1 ={x +1машина Тьюринга Т правильно вычисляет функциюf ( x1 ,..., xn ) , если10конфигурацию q1{... ∗{... ∗ ... ∗{... она переводит в конфигурациюx1 +1 x 2 +1q0{...,если значениеf ( x1 ,...x n )+1x n +1f ( x1 ,..., xn ) определено , и Т неприменима, еслизначение f ( x1 ,..., xn ) неопределено. Здесь * - символ-разделитель из А.
Классфункций, вычислимых по Тьюрингу обозначим через Т.20 )Рассмотрим несколько примеров на построение машин Тьюринга.1) Пусть А= {a0 = λ , a1 = 1} и Q={q0,q1,q2}2) Программа машины T1 : q1λ → q 2 1Eq1 1 → q1 1R(4)q 2 1 → q 2 1Lq 2 λ → q 0λRПусть K0конфигураций := q11x+ 1 .Тогда T1 порождает следующую последовательностьq11x+ 1 → 1q11x →...→ 1x+ 1 q1λ → 1x+ 1 q2 1 →...→ q2 1x+ 2 → q2 λ1x+ 2 → qТаким образом , машина Тьюринга (4) правильно вычисляет функциюf ( x) = x + 1 , x ∈ N0 .2) Пусть A={ λ ,1}, Q={q0,q1,q2}Программа машины T2 :q1λ → q1λRq1 1→ q 2 λRq 2 1 → q 2 λR(5)q2 λ → q 0 1EK0 = q11x+ 1 .
Тогда T2 порождает следующую последовательностьПустьконфигураций:q11x+ 1 → q 2 1x →...→ q 2 λ → q 0 1Значит, машина Тьюринга (5) правильно вычисляет функциюf ( x) = 0, x ∈ N03) Пусть А={ λ ,1,*}, Q={q0,q1,q2,q3}Программа машины Т3 :q11 → q 2 λR11q2 1 → q2 1Rq2 * → q2 1Rq2 λ → q 3λLq3 1→ q 4 λLq 4 λ → q 0λRq 4 1 → q 4 1L(остальные команды не важны для вычисления).x+ 1y+1*1 . Тогда машина Т3 порождает следующуюПусть K0 = q11последовательность конфигураций:q11x+ 1 * 1y + 1 → q2 1x * 1y + 1 →...→ 1x q2 * 1y + 1 → 1x+ 1 q2 1y + 1 → 1x+ y + 2 q2→ 1x+ y + 1 q 31 → 1x+ y q 4 1 →...→ q 4 λ1x+ y + 1 → q 0 1x+ y + 1Т.е.
машина T3 правильно вычисляет функцию f ( x) = x + y x, y ∈ N030 ) Прямое построение машин Тьюринга для решения даже простых задачможет оказаться затруднительным. Однако существуют приемы, которыеоблегчают данный процесс, если использовать способы сочетания программнескольких машин в результирующие программы. Дадим некотороепредставление об этих приемах, что позволит говорить о существовании тех илииных машин, на деталях же построения конкретных программ останавливатьсяне будем.1) Суперпозиция машин.
Пусть даны две машины Тьюринга T1 и Т2 , которыевычисляют соответственно словарные функции f1 ( P) и f 2 ( P) в одном и томже алфавите. Тогда существует машина Тьюринга Т , которая вычисляетфункцию f ( P) = f 2 ( f1 ( P)) .При этом для любого слова Р функция f ( P)определена в том и только в том случае, когда f1 ( P) определена иf 2 ( f1 ( P)) определена.
Программа машины Т строится так: Состояниямашины T2 переобозначаем так, чтобы они отличались от состояний машины T1.1Начальное состояние q1 Машины Т1 объявляем начальным q1 для машины Т,заключительное состояние q 0 2 машины T2 объявляем заключительным q 0 длямашины Т. Заключительное состояние q 0 1 машины T1 отождествляем сначальным состоянием q 12 машины Т2. Полученные команды для обеих машинобъединяем в одну программу. Рассмотрим начальную конфигурацию1q1 PПоскольку q1 = q1 - начальное состояние машины T1 , то вначале Т работает какмашина T1 и если T1 применима12q11 P , то на некотором шаге будет получена конфигурация q 10 f1 ( P) ,ноq 10 = q12 - начальное состояние для Т2 и теперь Т действует как машина Т2. Если1Т2 применима к q 0 f1 ( P) , то на некотором шаге будет получена конфигурациякq 02 f 2 ( f1 ( P)) , которая является заключительной для Т , т.к q02 = q2 .
Если Т11неприменима к q1 P или Т2 неприменима кq 10 f1 ( P) , то Т неприменима кq1 P . Машина Т называется суперпозицией машин Т1 и Т2 и обозначается T1T2.Схематически суперпозиция изображается так:P → f1 ( P) → f1 ( f 2 ( P))TT12Соединение машин. Пусть даны машины Тьюринга Т1 и Т2 , вычисляющиесловарные фунции f1 ( P) и f 2 ( P) соответственно. Тогда существует машинаТ , которая начальную конфигурацию q1 P переводит в заключительнуюq 0 f1 ( P) * f 2 ( P) ,если f1 ( P) и f 2 ( P) определены , и неприменима впротивном случае.Здесь * - новый символ, не входящий в алфавиты машин Т1 и Т2 . Машина Тназывается соединением машин и обозначается Т1*Т2.
Существование машины Твытекает из следующих неформально описываемых конструкций. Лента машиныT- является двухэтажной. В качестве внешнего алфавита Т берутся двухэтажные bбуквы , где а и b - буквы алфавита Т1,Т2 .Каждой букве a ставится в a λсоответствие двухэтажная буква . Слову P = a i ...ai ставится вk1 a λ ........λ .
Машина Т будет работать таксоответствие двухэтажное слово a ...a i1 ik (существование машин Тьюринга для реализации каждого шага ясно) λ ........λ ai1 ...aik ai1 ...aik f1 ( P) λ ...λ ...λ → → → → a ...a a ...a f ( P) f ( P) f ( P)* f ( P)i1ik1212 i1 ik З) Ветвление машин. Пусть даны машины Тьюринга Т1 и Т2 вычисляющиесловарные функции f1 ( P) и f 2 ( P) соответственно, заданные в одномалфавите.
Тогда существует машина Тьюринга Т , которая начальную13конфигурациюеслиq1ε * P ,где ε ∈{0,1} , переводит в заключительную q0 f1 ( P) ,ε = 0 и в q0 f 2 ( P) , если ε = 1.Машина T называется разветвлением машин Т1 и Т2 и обозначается Т1vТ2.Схематически разветвление представляется так:ε=0ε∗ PT1 ∨ T2f1( P)ε =1f2 ( P)Существование машины Т вытекает из следующих конструкций.
Пусть q11и q12 - начальные состояния машин Т1 и Т2 соответственно. Считаем, чтомножества внутренних состояний машин не пересекаются. Объединимпрограммы машин Т1 , Т2 , добавим новое начальное состояние q1 и добавимкомандыq1 0 → q11λ Rq11∗→ q11λ Rq11 → q12 λ Rq12 ∗→ q12 λ RТеперь заключительные состояния q01 и q02 машин Т1 и Т2 объединим, аполученное состояние q0 считаем заключительным для Т.
Если q1ε∗ P начальная конфигурация, то Т через 2 шага перейдет в конфигурацию q11 P , еслиε = 0 и в конфигурацию q12 P , если ε = 1 а затем будет работать как Т1 или T2соответственно.4) Реализация цикла. Важным приемом в программировании является разбиениерешаемой задачи на циклы. После выполнения каждого цикла проверяетсявыполнимость некоторого условия. Если условие выполнено, то выдаетсярезультат, если нет, то цикл повторяется. Точнее, процедура задается так.
Пустьимеем словарные функции f1 и f 2 и некоторый предикат Ф на словах (егозначения обозначим 0,1). Для произвольного слова Р проверяемся - верно лиФ(Р)=1 , если да, то выдается ответ f1 ( P ) . Если Ф(Р)=0 , то вычисляетсяP ′ = f 2 ( P ) . Затем проверяется-верно ли Ф( P ′ )=1, если да, то ведается ответf1 ( P ′ ) , если Ф( P ′ )=0 , то вычисляется P ′′ = f 2 ( P ′ ) и т.д, Существует машинаТьюринга Т , реализующая данную процедуру. Пусть существуют машиныТьюринга для вычисления функций f1 , f 2 и предиката Ф. Обозначим их Т1 ,14T2,Тф соответственно.
Пусть Т0-машина, которая оставляет всякое слово Р безизменения.Машина Т строится в соответствии со схемой:f1 ( P )ε =1Pε∗ PТф*Т0 T 1 ∨ T 2ε =0f2 (P )Пояснение: Заключительные состояния q01 и q02 машин Т1 и T2 не объединяются,а считаются различными. Состояние q01 объявляется заключительным для Т1 , аq02 отождествляется с начальным состоянием q1 для T. Заключительноесостояние для машины Тф*Т0 объявляется начальным для T 1 ∨ T 2 .Изизложенного следует, что если T 1 ∨ T 2 работает как T1, то полученное еюзначение является выходом Т , если же T 1 ∨ T 2 работает как T2 , то полученноеею значение снова подается на вход машины Т.Используя данный прием, можно построить машину Тьюринга дляперевода произвольного числа n>0 , заданного в унарной записи, т.е.
в виде 1n+1(n+1 палочка) в его двоичную запись, начинающуюся с 1.Входной алфавит машины есть { ∧,1,1,о) . Вначале стирается одна палочка, затемработа осуществляется t циклами ( 1<=t<=n). К концу каждого цикла t машинанаходится в конфигурацииq1α 2 ...α t 11...1,где 1α 1...α t двоичная запись числа t, 111...11 n-t палочек.В течение цикла t стирается одна палочка и к числу t-1 в двоичной записиприбавляется 1 .Формальное описание машины Тьюринга, однако, требуетбольшого числа технических деталей и поэтому мы их опускаем.Таким образом, язык Тьюрингова программирования содержит основныеоператоры программирования на алгоритмических языках и позволяетустраивать последовательное выполнение программ, параллельное ихсоединение, использовать условные переходы ("если Ф , выполнить f1 , иначеf 2 ”), реализовывать цикл (“ пока Ф , выполнить f1 , иначе f 2 ").
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
