Операции на машини на Тюринг. Състав на машината на Тюринг Какво е състав на машината на Тюринг

Машината на Тюринг (MT) е абстрактен изпълнител (абстрактна изчислителна машина).

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

Теоремите за комбинации от алгоритми представляват важен раздел от общата теория на алгоритмите. Веднъж доказани, те правят възможно по-нататъшното потвърждаване на осъществимостта на сложни и тромави алгоритми, без действително да се изписват схемите, които ги дефинират.

Комбинациите от алгоритми за машина на Тюринг се описват чрез операции върху машини на Тюринг.

1. Композиционна операция.

Нека M 1 и M 2 са машини на Тюринг с една и съща външна азбука A« (a 0 ,a 1 ,...,a p ). Нека означим множествата от техните състояния съответно като Q1 " (q 0 ,q 1 ,...,q n ) и Q2 " (q 0" ,q 1" ,...,q m" ).

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

Композиция от машини M 1 и M 2 е машина, обозначена с M=M 1 ×M 2, чиято програма има азбука A, набор от състояния Q« (q 0,q 1,...,q n,q n+1,... ,q n+m) и се получава от програмите на машините M 1 и M 2 както следва: навсякъде в програмата на машината M 1, където има „тройки“ със символа q 1 ( крайното състояние на машината M 1), той се заменя със символа q 0" (първоначалното състояние на машината M 2); всички други символи в програмите на машините M 1 и M 2 остават непроменени (в крайна сметка всичко това остава да преномерираме всички състояния на машината M: (q 0 ,q 1" ,q 2 ,...,q n ,q 0 " ,q 2" ,...,q m" )).

Композицията започва да "работи" като машина M 1, но в случаите, когато машината M 1 трябва да спре, тя превключва към програмата на машината M 2, поради замяната на q 1 с q 0". Очевидно, композиционната операция е асоциативна, но не комутативна.

Работата му е еквивалентна на последователната работа на машини Т1 и Т2.

Фигурата показва композиция от машини на Тюринг, която прилага оператора на суперпозиция за n=1 и m=1.

Снимка 1.

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

Итерация на машина на Тюринг M ще се нарича машина

2. Операция на разклоняване.

Нека M 1, M 2 и M 3 са машини на Тюринг, имащи една и съща външна азбука A« (a 0,a 1,...,a i,...,a j,...,a p) и, съответно, набори от състояния: Q1 " (q 0 ,q 1 ,...,q n ), Q2 " (q 0 " ,q 1 " ,...,q m " ), Q3 " (q 0 " , q 1 " ,.. .,q l" ).

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

Резултатът от операцията на разклоняване върху машините на Тюринг M 1, M 2 и M3 се нарича машина на Тюринг M, чиято програма се получава от програмите на машините M 1, M 2 и M 3, както следва: програмата на се записва машината M1, след което се задават програмите на машините M 2 и M 3. Ако в крайното състояние q 1 на машина M1 се наблюдава символът a i, тогава управлението се прехвърля на машина M 2, т.е. символ q 1 се заменя със символ q 0" и машината M 2 започва да работи. Ако в крайното състояние q 1 на машината M 1 се наблюдава символът a j, тогава управлението се прехвърля на машината M 3, т.е. символът q 1 се заменя чрез символ q 0" и машина М 3 започва да работи. Всички останали символи в програмите на машини M 1 и M 2 остават непроменени. Машина M завършва работата си в крайното състояние q 1 (в заключение остава да се извърши преномериране от край до край на състоянията на машина M).

Резултатът от разклонителна операция на машини на Тюринг M 1, M 2 и M3 се означава по следния начин:

За двубуквени машини на Тюринг (машини на Тюринг с двубуквена азбука), операцията на разклоняване на произволни машини на Тюринг M1, M2 и M3 се обозначава по следния начин:

тези. ако когато машина M1 работи в състояние q 1, се наблюдава символът a 0, тогава управлението се прехвърля към машина M2, в противен случай - към машина M3.

3. Циклична операция.

Нека M е машина на Тюринг с азбука A« (a 0 ,a 1 ,...,a p ) и набор от състояния Q« (q 0 ,q 1 ,...,q n ).

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

Резултатът от цикъла ще се нарича машина на Тюринг, означена с (i=0,2,3,...,n; j=0,1,2,...,p; s=0,2, 3,..., n)

чиято програма се получава от програмата на машината M чрез замяна на символа q 1 в консеквента на командата q i a j ®q 1 a t r, rО(L,R,L), t=0,1,2,.. .p, със символа q s .

2.4 Варианти на машината на Тюринг

Моделът на машината на Тюринг може да бъде разширен. Може да се разглеждат машини на Тюринг с произволен брой ленти и многоизмерни ленти с различни ограничения. Въпреки това, всички тези машини са завършени на Тюринг и са моделирани от обикновена машина на Тюринг.

Като пример за такава еквивалентност, разгледайте редуцирането на който и да е MT до MT, работещ на полубезкрайна лента.

Теорема:За всяка машина на Тюринг има еквивалентна машина на Тюринг, работеща на полубезкрайна лента.

Доказателство:

Нека разгледаме доказателството на Ю. Г. Карпов. Доказателството на тази теорема е конструктивно, тоест ще дадем алгоритъм, чрез който за всяка машина на Тюринг може да бъде конструирана еквивалентна машина на Тюринг с декларираното свойство. Първо, произволно номерираме клетките на работната лента на MT, т.е. определяме ново местоположение на информацията на лентата:

Снимка 1.

След това преномерираме клетките и ще приемем, че символът „*“ не се съдържа в MT речника:

Снимка 1.

2.5 Изчислимост и разрешимост по Тюринг

По-горе беше доказано, че класовете функции, изчислими с помощта на рекурсивни функции, машини на Тюринг или нормални алгоритми на Марков, съвпадат. Това ни позволява да разгледаме концепцията за „изчислителен алгоритъм“, инвариантна към метода на описание. Разлики се наблюдават само при използването на алгоритмични обекти. Ако за рекурсивните функции обектите са числа и числови функции, а процесът на изчисление се определя от операторите на суперпозиция, рекурсия, минимизиране и итерация, тогава за машините на Тюринг такива обекти са символи на азбуките на външната и вътрешната памет и изчислението процесът се определя от протокол, използващ изход, преход и преместване на главата. За нормален алгоритъм на Марков такива обекти са думи или последователности от символи и процесът на изчисление се определя от правила за заместване или продукти, които променят състава и структурата на оригиналната последователност от символи до желания резултат.

Аритметична (числова) функция е функция, чийто диапазон от стойности е подмножество на множеството N, а нейната област на дефиниране е елемент от множеството N.

За алгоритмични проблеми типична ситуация е, когато трябва да намерите алгоритъм за изчисляване на числена функция f(x 1, x 2, ..., x n), в зависимост от целочислените стойности на аргументите x 1, x 2 , ..., x n.

Наричаме функция f:N n →N изчислима, ако има алгоритъм, който позволява произволен набор от стойности на нейните аргументи да изчисли стойността на функцията (или да посочи, че функцията не е дефинирана в даден набор). Тъй като дефиницията на изчислима функция използва интуитивната концепция за алгоритъм, терминът „интуитивна изчислима функция“ често се използва вместо термина „изчислима функция“. По този начин масов проблем има решение, ако аритметичната функция, съответстваща на проблема, е интуитивно изчислима.

Функция f(x 1, x 2, …, x n) се нарича ефективно изчислима, ако за дадени стойности k 1, k 2, …, k n аргументи може да се намери стойността на функцията f(k 1, k 2, …, k n) с помощта на съществуваща механична процедура (алгоритъм).

Вместо да изясняваме концепцията за алгоритъм, можем да обмислим изясняване на концепцията за „изчислима функция“. Обикновено те протичат по следната схема:

1. Въвежда се точно дефиниран клас функции.

2. Уверете се, че всички функции от този клас са изчислими.

3. Приемете хипотезата (тезата), че класът на изчислимите функции съвпада с въведения клас функции.

Една функция се нарича изчислима, ако има алгоритъм, който я изчислява. „Изчислимост“ е едно от основните понятия на теорията на алгоритмите, инвариантно към функцията и алгоритъма, които се изчисляват. Разликата между изчислима функция и алгоритъм е разликата между описанието на функцията и начина, по който тя изчислява своите стойности, като се имат предвид стойностите на независимите аргументи.

Тезата на Тюринг. Всеки интуитивен алгоритъм може да бъде реализиран с помощта на машина на Тюринг.

От тезата на Тюринг следва, че ако възникнат алгоритмични проблеми, те трябва да бъдат решени въз основа на конструкцията на машини на Тюринг, тоест достатъчно формализирана концепция за алгоритъм. Освен това в алгоритмичните задачи често говорим не за конструиране на алгоритъм, а за изчислимост на някои специално конструирани функции.

Трябва да се отбележи, че в тези случаи е достатъчно да се използва азбуката (0,|), където 0 е празният знак. Например естествените числа, включително 0, са кодирани в тази азбука, както следва: 0 - |; 1 - ||; 2 -

N - ||…| (n + 1 пъти). Частична числова n-локална функция f(x1, x2, ..., xn) се нарича изчислима по Тюринг, ако има машина M, която я изчислява в следния смисъл: 1. Ако наборът от стойности на аргументи принадлежи към областта на дефиниране на функцията f, тогава машината M, започваща работа в конфигурация 0 |x1+1 0 |x2+1 ... 0 |xn q1 |, където |x = ||... | (x пъти) и най-десният символ се възприема, спира, завършвайки в конфигурацията 0|yq0 |, където y = f(x1, x2, …, xn). 2. Ако наборът от стойности на аргумента не принадлежи към областта на дефиниране на функцията f, тогава машината M, започваща работа в първоначалната конфигурация, работи безкрайно, т.е. не достига крайното състояние. Машината на Тюринг е точната формална дефиниция на алгоритъм. Използвайки тази концепция, може да се докаже разрешимостта или неразрешимостта на алгоритмични проблеми. Ако се установи, че изчислителен алгоритъм решава проблем, принадлежащ към един клас проблеми, тогава се казва, че проблемът е алгоритмично разрешим проблем. С други думи, предпоставка за изчислимостта или ефективността на едно изчисление е неговата алгоритмична разрешимост. В този смисъл понятието „разрешимост” също е основно понятие в теорията на алгоритмите. Анализът на три вида модели показва, че основните свойства на дискретност, детерминизъм, масовост и ефективност остават непроменени за различните методи на описание: Свойство на дискретност: алгоритъмът се състои от отделни елементарни действия, изпълнявани на стъпки; наборът от елементарни стъпки, които изграждат един алгоритмичен процес, е краен и изброим. Детерминирано свойство: след всяка стъпка се дават точни инструкции как и в каква последователност да се изпълняват следващите стъпки от алгоритмичния процес. Масово свойство: използването на алгоритъм е допустимо за много алгоритмични обекти от даден тип и даден клас проблеми. Свойство за ефективност: спирането на алгоритмичния процес е задължително след краен брой стъпки, показващи желания резултат. Тезата обаче не може да бъде доказана, тъй като е свързана от точната концепция за изчислимост на Тюринг с неточното понятие за интуитивно изчислима функция.

ПРОБЛЕМЪТ ЗА САМОПРИЛОЖИМОСТТА

Според определението за машина на Тюринг това е тройка Т= , при което а-азбука, В –вътрешни състояния на машината, Q-програма, която разграничава една машина от друга. В общия случай (за всички машини) програмата може да изглежда например така:

П: q iа a jа ® q rа катоа S tа , a = 1, 2, …, k , Където S 1- Р, S 2-Л, S 3- ° С . (*)

В този случай можем да предположим, че има някои общи азбуки А 0И Q 0, в които са написани знаци а И р за всички машини на Тюринг. След това символите q iа, a jа, q rа, катоа, S tаса символи на азбуката А 0И Q 0.

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

Годелска номерация на машини на Тюринг. Позволявам p 1 , p 2 , p 3 , ... - поредица от прости числа, подредени във възходящ ред, например 2, 3, 5, 7, 11, 13, ...

Номер на машината на Тюринг с програма (*)извикан номер

n(T) = .

Пример

Машина, която изпълнява функция С(х)= x + 1 , има програма в азбуката {0,  } . Номерът на тази програма, като се вземе предвид факта, че а 0 = 0 , а 1= | ще има номер:.

n(T)= 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3 .

Очевидно не всички естествени числа са числа на машината на Тюринг. От друга страна, ако н – номерът на определена машина, в общите азбуки, тогава нейната програма може да бъде уникално възстановена от това число.

Кола T, приложимо към думата н(T)(тоест към кода на вашия собствен номер), наречено самоприложимо .

Възможно е да се изградят както самоприложими машини, така и несамоприложими машини. Например машината от дадения пример е самоприложима. Кола T, който няма символ за спиране в десните части на програмата (в тялото на таблицата), не е приложим за никоя дума и следователно за думата н(T).

Проблем със самоприложимосттае както следва: да се посочи алгоритъм, който при дадена машина на Тюринг би определил дали тя е самоприложима или не.

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

Нека, например, тази кола Tприложен към кода н(T * ) . Ако колата T * самоприложима, след това окончателната конфигурация на машината Tизглежда като а" q 0 | Б", а ако колата T * не е самоприложимо, тогава окончателната конфигурация на машината Tизглежда като а" q 0 0 Б ". Тук а", Б", а", Б"- думи.

ТеоремаПроблемът за самоприложимостта е алгоритмично неразрешим, тоест няма машина на Тюринг, която да решава този проблем в горния смисъл.

От теоремата следва, че няма общ алгоритъм, който да решава проблема със самоприложимостта. В специфични специални случаи могат да съществуват такива алгоритми.

Нека използваме резултатите от тази теорема, за да докажем неразрешимостта на проблема за приложимостта към началната дума.

Проблемът за приложимостта към началната дума е както следва: създайте алгоритъм, който според машината Tи думата х ще монтира, приложима машина Tмежду другото х или не (в противен случай има проблем със спирането).

По отношение на машините на Тюринг, подобно на формулировката на проблема за самоприложимостта, този проблем се формулира по следния начин: възможно ли е да се изгради машина, която да е приложима към всички думи от формата н(T)0 х , Където Tпроизволна машина, х – произволна дума, а ако машината Tприложимо към думата х а" q 0 |Б" , и ако колата Tнеприложимо към думата х , ще доведе до окончателната конфигурация а" q 0 0 Б" . Тук а", Б"И а", Б"- произволни думи.

ТеоремаПроблемът с приложимостта към началната дума е алгоритмично неразрешим, тоест няма машина на Тюринг, която да решава този проблем в горния смисъл.

Както беше посочено по-горе за проблема със самоприложимостта, първата предварителна стъпка е номерирането. Ето защо по-долу този проблем се разглежда последователно и се решава за алгоритми и неговите три основни типа алгоритмични модели.

Номериране на алгоритми

Номерирането на алгоритмите играе важна роля при тяхното изследване и анализ. Тъй като всеки алгоритъм може да бъде определен като крайна дума (представена като крайна последователност от символи на някаква азбука) и множеството от всички крайни думи в крайна азбука е изброимо, тогава множеството от всички алгоритми също е изброимо. Това означава съществуването на съпоставяне едно към едно между набора от естествени числа и набора от алгоритми, тоест възможността да се присвои номер на всеки алгоритъм.

Номерирането на алгоритмите е и номерирането на всички алгоритмично изчислими функции и всяка функция може да има безкраен брой числа.

Наличието на номериране ви позволява да работите с алгоритми по същия начин, както с числа. Номерирането е особено полезно при изучаването на алгоритми, които работят с други алгоритми.

Нека има определен проблем с масата с набор от начални обекти X и набор от желани обекти Y. За да съществува решение на проблема с масата, е необходимо елементите на множествата X и Y да бъдат конструктивни обекти. Следователно елементите на тези множества могат да бъдат номерирани с естествени числа. Нека x∈ X е някакъв начален обект, нека означим номера му с n(x). Ако в масова задача за оригиналния обект x се изисква да се получи желаният обект y∈ Y с номер n(y), тогава дефинираме аритметична функция f: Nn →N така, че f(n(x))=n (y).

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

1. Ако е даден масив ] от естествени числа, тогава на него може да се присвои естественото число 2x1, 3x2,... p(n)xn, където p(n) е n-тото просто число. Да вземем пример за масив с дължина 5:

] 2x13x25x37x411x5.

Това номериране дефинира аритметичната функция f (например f(73500) = f(22315372110) = 20315272113 = 4891425).

2. Всяко рационално число има някакво естествено число. Номерирането на набора от необходими обекти на проблема е тривиално:

(„да“, „не“) a (1, 0). За даден масов проблем можете да конструирате аритметична функция от един аргумент, като използвате техниката от предишния пример, или можете да разгледате функция от три аргумента (три числа от елементи на оригиналната тройка).

3. Номерирането на програмни текстове може да се извърши по следния начин: всяка програма може да се възприема като запис на число в 256-арната бройна система (ако за запис на програмата са използвани символи от ASCII таблица).

Преходът от масов проблем към аритметична функция ни позволява да намалим въпроса за съществуването на решение на масов проблем до въпроса за съществуването на ефективен начин за изчисляване на стойностите на аритметична функция от нейния аргумент ( аргументи).

Номериране на набори от числа

В теорията на алгоритмите е широко разпространена техника, която позволява да се намали изучаването на функции на няколко променливи до изследване на функции на една променлива. Базира се на номерирането на набори от числа, така че да има двустранно съответствие между набори от числа и техните числа, а функциите, които определят от набор от числа неговия номер и от числото самия набор от числа, обикновено са рекурсивни. Например, за функция, съдържаща две независими променливи (x, y), това преобразуване h(x, y) може да бъде така:

Снимка 1.

Нека двойки (x, y) образуват частично подредено множество N(2). Ако е дадено h(x, y) = n, тогава има обратно преобразуване: x = h -1 1 (n) и y= h -1 2 (n), т.е. h(h -1 1 (n), h -1 2 (n)) = n. Това ви позволява да изчислите числото n за всяка двойка (x, y) и, обратно, да използвате числото n, за да изчислите стойностите на x и y:

Използвайки тези правила, можете да изчислите номерирането на тройките h 2 (x, y, z) = h(h(x, y), z) = n и, обратно, по броя на тройката - стойностите на x, y, z. Например, ако h 2 (x, y, z) = n, тогава z= h -1 2 (n), y= h -1 2 (h -1 1 (n)), x= h -1 1 ( h -1 1 (n)), h 2 (x, y, z) = h (h (h -1 1 (h -1 1 (n)), h -1 2 (h -1 1 (n)) ), h -1 2 (n)). Тройките (x, y, z) образуват частично подредено множество N(3). По същия начин за произволен брой числа имаме:

h n-1 (x1, x2,…, xn)=h(h…h(h(x1, x2), x3)… x n-1), xn). Ако h n-1 (x1, x2,…, xn)=m, тогава xn = h -1 2 (m), x n-1 =h -1 2 (h -1 1 (m)), ... ..................................., x2 = h -1 2 (h -1 1 (. .. h -1 1 (m)...)), x1 = h -1 2 (h (...h (m)...)).

Имайки номерирането на набори от набори N (1) , N (2) ,..., N (i) ,..., N(n, където N (i) е наборът от набори (i) от числа, възможно е да се установи комбинирано номериране на произволни множества числа M = N (1) N (2) ... N (i) .. N(n) , където M N. За всяко n N имаме h(x1, x2,..., xn )= h(h n −1 (x1,x2,..., xn), n −1).

Ако h(x ,1x ,2..., x)n = m, тогава h n−1 (x ,1x ,2..., x)n = h -1 1 (m), n= h -1 2 (m)+1. Използвайки горните формули, можете да възстановите стойностите на x1, x2,…, xn.

Свързана информация.

В предишния параграф разгледахме как „дадена машина на Тюринг изчислява функцията f (, …,).“ За целта е необходимо всяко от числата, ..., да бъде записано на лентата на машината като непрекъснат масив от съответния брой единици, а самите масиви да бъдат разделени със символа 0. Ако функцията f (, ..., е дефиниран на даден набор от стойности на аргумент, тогава резултатът на лентата трябва да бъде записан в ред f (, ...,) единици. В същото време не бяхме много стриктни по отношение на начална позиция, в която машината започва да работи (често това е стандартната начална позиция), в която завършва работата и как протича тази работа.

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

Определение 5.1:Ще кажем, че машина на Тюринг изчислява правилно функцията f (, ...,), ако преобразува началната дума 0...0 в думата 0...0 и в същото време, в процеса на работа, не добавя нови клетки към началната дума на лентата нито отляво, нито отдясно. Ако функцията f не е дефинирана за даден набор от стойности на аргументи, тогава, започвайки да работи от посочената позиция, тя никога няма да добави към лентата отляво по време на своята работа.

Пример 5.1.Нека представим програми на машини на Тюринг, които изчисляват правилно функциите S(x) = x+1 и O(x) = 0. Функцията S(x) = x+1 извършва транслацията: 0 => . Неговата програма: 0 > P, 1 > 1P, 0 > 1, 1 > 1L, 0 > 0. Функцията O(x) = 0 извършва преобразуването: 0 => . Програмата му е: 0 > 0П, 1 > 1П, 0 > 0Л, 1 > 0, 0 > 0Л, 0 > 0. Съответната машина на Тюринг се обозначава с О.

Пример 5.2.Изградете две машини „лява смяна“ и „дясна смяна“. Първият, от първоначалната стандартна позиция, обработва дума 0 в същата дума и спира, гледайки най-лявата клетка с нула. Втората машина от първоначалното състояние, в което се вижда лявата клетка с нула, дума 0 се обработва в същата дума и спира, като вижда най-дясната клетка с нула.

Машинна програма: 0 > 0Л, 1 > 1Л, 0 > 0. Ясно е, че машинната програма се получава от програмата на предходната машина чрез замяна на символа “L” със символа “P”.

Състав на машините на Тюринг

Определение 6.1:Нека са дадени машини на Тюринг и , имащи обща външна азбука (, …,) и азбуки на вътрешни състояния (, …,) и (, …, ) съответно. Композиция (или продукт) от машина върху машина е нова машина със същата външна азбука (, ...,), вътрешна азбука (, ..., ...,) и програма, получена както следва. Във всички команди от, които съдържат знак за спиране, заменете последния с. Всички други символи в командите from остават непроменени. В командите от символът остава непроменен, а всички останали състояния (i = 1, ..., t) се заменят със съответно. Съвкупността от всички така получени команди образува програмата на композиционната машина.

Въведената концепция е удобен инструмент за конструиране на машини на Тюринг. Нека покажем това с пример.

Пример 6.1.Нека конструираме машини на Тюринг, които правилно изчисляват функциите на проектора (, …,) = (1? m ? n).

Нека първо разгледаме конкретния случай n=3, m=2, т.е. функция (,) = . Трябва да обработим дума 0 в дума 0. Ще приложим предварително конструираните машини на Тюринг, B, O, към първоначалната конфигурация:

Така функцията (,) = се изчислява от следната композиция от машини: BOO = B.

Сега можем да си представим алгоритъм за конструиране на композиция от машини, B, O за изчисляване на всяка функция от формата (, ...,) = . Използвайки десен отместване, прилагайки го m-1 пъти, първо трябва да достигнете до масива:

След това, движейки се наляво, транспонирайте (използвайки B) масива с всеки съседен отляво масив, докато масивът излезе отгоре:

Сега трябва да стигнете до най-десния масив, като използвате (n-1) - множество приложения на дясното преместване:

И накрая, трябва да изтриете последователно отдясно наляво всички масиви от единици с изключение на първия:

И така, тази функция е (правилно) изчислена от следната машина на Тюринг.

Работа на машината на Тюринг:

От трите основни понятия на алгоритъм, второто определение е свързано с машинната математика. Алгоритъмът се счита за най-простото детерминистично устройство, способно да изпълнява най-простите операции във всеки даден момент. Основният модел е машина на Тюринг.

Машината на Тюринг работи с три азбуки:

1. въвеждане на азбука А={а 0…и н), с помощта на които се записва входна, междинна и изходна информация. а 0– празен знак (незначителна нула, Ù, IN, #), а 1– 1 или |

2. вътрешна азбука, или азбука на държавите Q={q 0…q m}, q 0- крайно състояние р 1- Първоначално състояние q 0 …q n- работно състояние

3. смяна на азбуката (L, V, N) или (-1, +1, 0) (ляво, дясно, на място)

Машината на Тюринг се състои от следните части:

1) панделка, потенциално безкраен и в двете посоки. Потенциалната безкрайност означава, че във всеки момент на лентата се записва ограничена дума, но ако е необходимо, необходимият брой клетки могат да бъдат добавени отляво и отдясно на думата. Лентата е разделена на клетки, всяка от които съдържа само един знак от въведената азбука. Празните клетки съдържат празен знак. Ако информацията в клетка трябва да бъде изтрита, тогава е достатъчно да напишете празен знак в нея.

2) контролно устройство(CU), който използва програма за управление на машина на Тюринг. Във всеки един момент контролното устройство може да бъде само в едно от състоянията на азбуката Q.

3) глава(четец и писател) изпълнява следните действия във всеки момент от време

· чете знака, изписан в клетката

· замества го с друг знак от азбуката Аили го оставя същото

· се движи по лентата надясно, наляво с една клетка или остава на място

Правилото на машината на Тюринг:

Машина на Тюринг, намирайки се в състояние q iи четене на героя a j, записва знак в тази клетка и к, преминава в състояние q e, извършва смяна. В този случай се казва, че машината е изпълнила една команда: a j q i® a k q e S SО(L, P, N)

Набор от команди се нарича MT програма.

a j q i– изходните символи на командите трябва да са различни. Ако това условие е изпълнено, машината се извиква детерминистичен , в противен случай - недетерминиран . Машината работи в отделни часове.

По този начин пълното описание на машината на Тюринг във всеки момент от времето, от което може да се определи нейното по-нататъшно поведение, съдържа информация за:

вътрешното състояние, в което се намира машината, думата, която е написана на лентата, и знака, който се чете в даден момент. Ще наричаме пълното състояние на машина на Тюринг конфигурация.

Работата на машината на Тюринг може да бъде представена като последователност от конфигурации к 1® к 2®…® k n.

Стандартната първоначална конфигурация е да прочете най-левия непразен знак в състоянието р 1

Стандартна окончателна конфигурация - машината е в окончателно състояние:

Ако машината е влязла в крайно състояние, тя е приложима към дадената входна дума; ако работи безкрайно, тогава машината не е приложима към дадената дума.

MT е колекция, състояща се от входна азбука, азбука на състоянията и програма. М = . A – входна азбука Q – вътрешна азбука P – програма

Програмата на машината може да бъде зададена както следва:

1) списък с команди: a j q i® a k q n S

2) с помощта на таблица

3) използване на предикатна графа (върхове - състояния, всяка команда съответства на дъга)

Конструкция на машини на Тюринг:

Да се ​​конструира машина на Тюринг означава да се изгради нейната програма. Провежда се на два етапа:

1) устно описание на алгоритъма на решавания проблем

2) превод на словесното описание на алгоритъма на езика на машината на Тюринг (за това задайте А, Q, П)

Пример: изградете машина на Тюринг, която изчислява функцията f(n)=n+1, където n е дадено в двоична форма.

А={0,1,а 0), множеството Q се определя по време на процеса на изграждане на програмата.

Алгоритъм:

1. преместете главата от крайно дясно състояние в крайно ляво

2. ако в крайна дясна позиция машината чете 0, тогава я поставете в клетка 1 и спрете, ако главата чете 1, поставете я в клетка 0 и преместете една стъпка наляво.

Повторете стъпка 2

Пример: Лентата съдържа естествено десетично число. Необходимо е да се конструира машина на Тюринг, която увеличава това число с 1. Първоначално главата сочи първата цифра на числото. Получаваме: A = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a 0), Q = (q 1, q 2, q 0). P – виж таблицата.

Главна идея – преместете главата до последната цифра на числото и ако тази цифра не е 9, увеличете я с единица, в противен случай я завъртете на нула и преминете към предишната клетка.

Състав на автомобили:

Машинната композиция е последователното изпълнение на две машини.

Т 1=(A 1, Въпрос 1, П 1) Т 2=(А 2, Въпрос 2, П 2) Въпрос 1Ç Въпрос 2=Æ

Състававтомобили Т 1° Т 2кола се казва T(А, Q, П), Където А=A 1È А 2; Q=(Въпрос 1È Въпрос 2)\{р 10} (р 10– крайно състояние Т 1). Кола Tработи по следното правило: U- някаква дума T(U)=Т 1° Т 2(U)=Т 2(Т 1(U))

Теорема.Състав на автомобили Т 1° Т 2съществува.

Въпрос 1={р 10, р 1,…, qn}

Въпрос 2={q 20, q` 1 , …, q`n), тогава, за да конструираме Q, премахваме състоянието q 10 , преозначавайки го като р n +1, което съвпада с началното състояние на втората машина, а всички останали състояния са в q`аз = qn + 1 .

Изчислими функции на Тюринг:

Извиква се функцията f(x 1 …x n). Изчислим по Тюринг, ако има машина на Тюринг, която изчислява стойността на тази функция, когато са дадени стойностите на аргументите. Функцията f(x 1 …x n) е дадена върху множеството от естествени числа, но теорията на алгоритмите разглежда разширеното множество от естествени числа NÈ(0).

Аргументите на функцията f(x 1 ...x n) на лентата са представени като следната дума:

Всеки аргумент отговаря на толкова пръчки, колкото е стойността на този аргумент. Ако функцията f е дефинирана върху даден набор от стойности на променливата x 1 ...x n, тогава в резултат на работата на машината на Тюринг на лентата трябва да остане броят на пръчките, записани в един ред, който е равно на стойността на функцията в това множество. Ако функцията f не е дефинирана на дадено множество, тогава машината на Тюринг трябва да работи неограничено време.

Първоначална конфигурация – четене на най-лявата пръчка.

Диаграмата изглежда като графика:

Стойност на таблицата на машината

маса 1

1. Някои операции на машини на Тюринг

Работата на машината на Тюринг се определя изцяло от входните данни и командната система. Въпреки това, за да се разбере как дадена машина решава даден проблем, като правило има нужда от смислени обяснения от типа, който е даден за машината . Тези обяснения често могат да бъдат направени по-формални и точни чрез използване на блок-схеми и някои операции на машината на Тюринг. Спомнете си, че съставът на функциите
И
наречена функция
, който се получава при използване към резултата от изчислението . За да
беше решен при това , е необходимо и достатъчно за беше определено на
, А беше определено на .

Теорема 1. Ако
И
са изчислими по Тюринг, тогава техният състав
също е изчислим по Тюринг.

Позволявам - машина, която изчислява , А - машина, която изчислява и набор от техните състояния, съответно
И
.

Нека изградим диаграма на прехода на автомобила от диаграми И както следва: идентифицираме началния връх
машинни схеми с краен връх
машинни схеми (за командните системи това е еквивалентно на факта, че командната система присвоени на командната система и за това
в екипи замени с
). Получаваме диаграма с (
) заявява. Първоначално състояние ще обявим
и окончателно
. За по-лесно записване ще приемем И числени функции на една променлива.

Позволявам
определен. Тогава
И

. Кола ще премине през същата последователност от конфигурации с тази разлика, че вместо
ще се проведе в
. Тази конфигурация е стандартната първоначална конфигурация за машината , Ето защо
. Но тъй като всички отбори съдържано в , Че

и следователно
. Ако
тогава не е дефинирано или не спира и следователно колата няма да спра. Значи колата изчислява
.

Така построената машина ще го наречем композиция от машини И и посочете
(или ()), а също и изобразени на блокова диаграма:

1. Състав на машините на Тюринг

Позволявам ,,- три машини на Тюринг с една и съща външна азбука
, с азбуки на вътрешните състояния
,
,
и програми ,
,
съответно.

Състав
автомобили И Наречен колаT , чиято програма е обединението на множества
И

, Където
обозначава набор от команди, получени от замяна на всички На .

1. Разклоняване на машините на Тюринг

Разклонителни машини,,от
, символично

Наречен колаT , чиято програма се получава както следва: от отборите са изключени
И
За
, полученият набор ще бъде извикан ; Тогава.

1. Универсална машина на Тюринг

Командната система на машина на Тюринг може да се тълкува както като описание на работата на конкретно устройство, така и като програма, т.е. набор от инструкции, които ясно водят до резултат. При анализиране на примери неволно се приема втората интерпретация, т.е. ние действаме като механизъм, който може да възпроизведе работата на всяка машина на Тюринг. Увереността, че всеки ще направи това по един и същи начин (ако не прави грешки, което между другото също се предполага, когато работи машина на Тюринг), по същество е увереност в съществуването на алгоритъм за възпроизвеждане на работата на машина на Тюринг машина по зададена програма, т.е. командна система. Наистина не е трудно да се даде словесно описание на такъв алгоритъм. Основното му действие се повтаря циклично и се състои в следното: „За текущата конфигурация
намерете командата с лявата страна в командната система
. Ако дясната страна на тази команда е от формата
, след което заменете в текущата конфигурация
На
(оказва се конфигурацията
); ако дясната страна има формата
, след което сменете
На
. Словесното описание на алгоритъма може да е неточно и трябва да бъде формализирано. Тъй като машината на Тюринг в момента се обсъжда като формализиране на концепцията за алгоритъм, естествено е да се постави проблемът за конструиране на машина на Тюринг, която реализира описания алгоритъм за възпроизвеждане. За машини на Тюринг, които изчисляват функции на една променлива, формулировката на този проблем е както следва: изградете машина на Тюринг , изчисляване на функция на две променливи и такава, че за всяка машина с командна система
, Ако
дефинирани (т.е. ако машината спира при първоначални данни ) И
не спира, ако
не спира. Ще наричаме всяка машина, която има това свойство универсална машина на Тюринг. Не е трудно тази формулировка да се обобщи за произволен брой променливи.

Първият проблем, който възниква при изграждането на универсална машина , се дължи на факта, че като всяка друга машина на Тюринг, трябва да има фиксирана азбука
и фиксиран набор от състояния
. Следователно командната система
и началните данни на произволна машина не можете просто да го прехвърлите на колана на машината (винаги има кола , азбуки
И
който превъзхожда по мощност
И
или просто не съвпадат с него).

Решението е да имате героите от
И
кодирани със символи в азбуката
. Позволявам
,
. Винаги ще приемаме това
И
(тези два символа винаги са в азбуката на всяка машина, която работи с числа). Нека обозначим кодовете И през
И
и ги определи като
; за всеки друг
; за крайно състояние


, Ако

. Код
за тази кола винаги има дължина (формат)
, и кода
- формат . Символи ,
нека влезем
, т.е.
,
,
. Код на символа , образувани от кодовете на знаците, съставляващи тази дума, обозначаваме
. По този начин окончателното усъвършенстване на формулировката на проблема за универсална машина се свежда до това, че за всяка кола и думи азбука
.

Съществуването на универсална машина на Тюринг означава, че системата за инструкции
всяка кола може да се тълкува по два начина: или като описание на работата на оригиналното устройство , или като програма за универсална машина . За съвременния инженер, който проектира система за управление, това обстоятелство е естествено. Той добре знае, че всеки алгоритъм за управление може да бъде реализиран или хардуерно - чрез изграждане на подходяща схема, или софтуерно - чрез написване на универсална управляваща компютърна програма.

Важно е обаче да се разбере, че идеята за универсално алгоритмично устройство е напълно несвързана с развитието на съвременните технически средства за нейното прилагане (електроника, физика на твърдото тяло и др.) И не е технически, а математически факт , описани в абстрактни математически термини, които са независими от технически средства и освен това се основават на изключително малък брой много елементарни първоначални концепции. Характерно е, че основните трудове по теория на алгоритмите (по-специално работата на Тюринг) се появяват през 30-те години, преди създаването на съвременните компютри.

Това двойно тълкуване запазва на абстрактно ниво основните плюсове и минуси на двата варианта за инженерна реализация. Конкретен автомобил работи много по-бързо; в допълнение, устройството за управление на машината доста тромави (т.е. броят на състоянията и командите е голям). Стойността му обаче е постоянна и веднъж конструиран е подходящ за прилагане на произволно големи алгоритми. Всичко, което е необходимо, е голям обем лента, която естествено се счита за по-евтина и по-опростена конструкция от устройството за управление. Освен това, когато променяте алгоритъма, няма да е необходимо да създавате нови устройства, просто трябва да напишете нова програма.

Цел на работата:придобиват практически умения за писане на алгоритми, използвайки състава на машините на Тюринг.

Теоретична информация

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

Нека опишем 4 основни метода за съставяне на МТ:

Последователна композиция (суперпозиция);

Паралелен състав;

Разклоняване

1. Последователна композиция на машини на Тюринг

Последователна композицияили суперпозицияМашини на Тюринг и

И
по азбука а,кола се казва М, изчисляване на функцията
.

Последователната композиция е изобразена по следния начин:

и е обозначен
или
.

2. Паралелна композиция на машини на Тюринг

Паралелен състав автомобили
И
, изчисляване на речникови функции
И
в азбуки АИ IN,съответно се извиква машината М, който оценява речникова функция. Ето знака използвани за разделяне на думи в паралелен MT състав.

Паралелен състав МТ
И
е изобразен както следва:

и се обозначава:
.

Всъщност, паралелна композиция от две МТ получава като вход дума, състояща се от 2 думи в различни азбуки, и извежда дума, състояща се също от 2 думи, т.е. представлява две едновременно и независимо работещи машини. За изпълнение на паралелна композиция се използва машина с двуетажна лента.

Двуетажната лентова машина работи по следния начин:

1) дума пренаписан на втория етаж на лентата и изтрит на първия,

2) изчислени
на първия етаж,

3) изчислени
На втория етаж

4)
преписан на първи етаж, може и с разместване.

Командата MT с двуетажна лента е написана, както следва:

,

Където
– букви, изписани съответно на първи и втори етаж. Нека обозначим дължините на думите
, съответно
.

Нека демонстрираме работата на машина на Тюринг с двуетажна лента. Като цяло дължините на думите
И
не съвпадат един с друг, но за простота на изображението приемаме, че са равни. Тогава изпълнението на точки 1)-4) на МТ с двуетажна лента се извършва по следния начин:

Да се ​​реализира паралелна композиция н Използват се машини на Тюринг н– подова лента.

3. Разклоняване или условен преход в композиции на машини на Тюринг

Ако са дадени машини на Тюринг
И
, изчисляване на речникови функции
И
, и колата
, който оценява някакъв предикат П( ) с възстановяване (т.е. без изтриване на думата  ), тогава може да се изгради машина на Тюринг за прилагане на разклоняване
, изчисляване на функцията:

Разклоняването на машините на Тюринг в композиционните диаграми е изобразено по следния начин:

и е обозначен
, Тук
- резултатът от работата на машината
, приемайки стойностите "1", ако предикатът П( )= ”вярно” и "0", ако предикатът П( )= “невярно” ,
– машина на Тюринг, която реализира копиране на входната дума
.

4 . Цикъл в състава на машините на Тюринг

Цикълпо състав МТ се изпълнява съгласно същите принципи като разклоняването.

" Чао P( )= ”вярно” , изпълни
»,

Където  – дума на лента преди първото изпълнение
и след следващото изпълнение .

За да изобразим цикъла, въвеждаме някои обозначения, нека:

– машина на Тюринг, която реализира изчислението на предикат P( ) ;

–MT, който реализира копиране на въведената дума
;

–MT, изпълнява се в цикъл и се изпълнява
;

–MT, изпълнява се при излизане от цикъла и изпълнение
.

След това цикличният състав на машините на Тюринг или цикълът може да бъде изобразен по следния начин:

Програмиране с машина на Тюринг Композиции:

1) изграждане на блокови схеми на сложни алгоритми с такова ниво на детайлност, че техните блокове съответстват на елементарни MT;

2) изграждане на елементарни МП, които реализират прости блокове;

3) комбиниране на елементарни МТ в МТ композиция.

Пример.Изградете MT композиция, която изпълнява
.

– машина на Тюринг, която осъществява копиране на входната дума;

–MT, който изпълнява функцията за настройка на константата нула;

–MT, изчислителен предикат с възстановяване
;

– MT, който изпълнява функцията за избор - този аргумент от аргументи;

–MT, прилагащ функцията за намаляване на аргумента с 1 в унарен код (изтрива най-левия знак);

– MT, който извършва събиране на две числа в унарен код.

Трябва да се отбележи, че във всеки случай е необходимо да се проверят коректността на входните данни в началото на изпълнението на алгоритъма (например равенството на аргумента на 0 по време на разделянето).