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

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

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

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

Машини на Тюринг: определение

Машина на Тюрингима безкрайност в двете посоки лента, разделен на квадрати ( клетки). Всяка клетка може да съдържа някакъв символ от фиксиран (за дадена машина) краен набор, наречен азбукана тази машина. Един от знаците на азбуката е подчертан и се нарича „интервал“; предполага се, че първоначално цялата лента е празна, тоест изпълнена с интервали.

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

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

Таблицата за преход е подредена по следния начин: за всяка двойка е посочена тройка. Тук преместването е едно от числата -1 (наляво), 0 (на място) и 1 (надясно). По този начин таблицата на прехода е функция от типа S x A -> S x A x (-1,0,1), дефинирана върху онези двойки, в които състоянието не е окончателно.

Остава да опишем поведението на машината на Тюринг. Във всеки момент има някои конфигурация, състоящ се от съдържанието на лентата (формално казано, съдържанието на лентата е произволно преобразуване Z -> A), текущата позиция на главата (някое цяло число) и текущото състояние на машината (елемент S). Трансформацията на конфигурацията в следващата става по естествени правила: гледаме в таблицата какво трябва да се направи за дадено състояние и за даден символ, т.е. намираме новото състояние на машината, променяме символ към посочения и след това преместете главата наляво, надясно или я оставете на място. Освен това, ако новото състояние е едно от последните, работата на машината приключва. Остава да се споразумеем как подаваме информация на входа на машината и какво се счита за резултат от нейната работа. Ще приемем, че азбуката на машината, в допълнение към интервала, съдържа знаците 0 и 1 (и евентуално някои други знаци). Входът и изходът на машината ще бъдат крайни последователности от нули и единици (двоични думи). Въведената дума се записва на празна лента, главата на машината се поставя в първата й клетка, машината се привежда в първоначално състояние и се стартира. Ако машината спре, резултатът е двоична дума, която може да се прочете, като се започне от позицията на главата и се движи надясно (докато се появи символ, различен от 0 и 1).

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

Машини на Тюринг: дискусия

Разбира се, нашата дефиниция съдържа много конкретни подробности, които могат да бъдат променени. Например една лента може да бъде безкрайна само в една посока. Можете да дадете на колата две панделки. Можем да считаме, че машината може или да напише нов знак, или да се движи, но не и двете. Можете да ограничите азбуката, като имате предвид, да речем, че тя трябва да има точно 10 знака. Можете да поискате в края на лентата да няма нищо освен резултата от работата (останалите клетки трябва да са празни). Всички горепосочени и много други промени не променят класа на функциите, изчислими на машините на Тюринг. Разбира се, има и някои безвредни промени. Например, ако забраните на кола да се движи наляво, това коренно ще промени нещата; по същество касетата ще стане безполезна, тъй като вече няма да е възможно да се върнете към старите записи.

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

Ако машината види интервал (въведената дума е празна), тя спира да работи. Ако не, запомня текущия знак и поставя знак (в азбуката, освен знаците 0 и 1, ще има и техните „маркирани варианти“ и ). След това тя се премества надясно до празна клетка, след което пише копие на запаметения символ там. След това тя се движи наляво, докато бъде маркирана; След като се е заровил в знака, той се връща назад и си спомня следващия знак и така нататък, докато копира цялата дума.

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

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

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

Друг пример за неформално разсъждение: нека обясним защо е възможно да не се използват допълнителни знаци, различни от 0, 1 и празния знак. Нека има машина с голяма азбука от N знака. Нека изградим нова машина, която ще симулира работата на старата, но всяка клетка от старата ще съответства на блок от k клетки от новата. Размерът на блока (числото k) ще бъде фиксиран, така че в рамките на блока всички знаци от голяма азбука да могат да бъдат кодирани с нули и единици. Оригиналните символи 0, 1 и празно място ще бъдат кодирани като 0, последвано от (k-1) празни знака, 1, последвано от (k-1) празни знака и група от k празни знака. Първо трябва да раздалечите буквите на въведената дума на разстояние k, което може да стане без допълнителни символи (когато стигнете до външната буква, я отдалечете, а когато стигнете до следващата, преместете нея и най-външната един и така нататък); просто трябва да разберете, че можете да идентифицирате края на дума като позиция, последвана от повече от k празни знака. Ясно е, че в този процес трябва да съхраняваме някакво крайно количество информация в паметта, така че това е възможно. След това вече е възможно да се симулира работата на оригиналната машина стъпка по стъпка и за това е достатъчна и ограничена памет (e краен брой състояния), тъй като само малък квартал на главата на симулираната машина е важни за нас. Накрая трябва да компресираме резултата обратно.

За да завършим дискусията, представяме обещания по-горе аргумент в полза на факта, че всяка изчислима функция е изчислима на машина на Тюринг. Нека има функция, която човек може да изчисли. В същото време той естествено трябва да използва молив и хартия, тъй като количество информацияколичеството, което той може да съхранява „в ума си“, е ограничено. Ще приемем, че той пише на отделни листове. В допълнение към текущия лист има купчина документи отдясно и купчина отляво; Можете да поставите текущия лист във всеки от тях, след като сте приключили работата с него, и да вземете следващия от другата купчина. Човек има молив и гумичка. Тъй като много малки букви не се виждат, броят на ясно различимите състояния на листа е краен и можем да приемем, че във всеки момент върху листа е написана една буква от някаква крайна (макар и много голяма) азбука. Човек също има ограничена памет, така че неговото състояние е елемент от някакво крайно множество. В този случай можете да съставите някаква таблица, в която да е записано как ще завърши работата му върху лист с дадено съдържание, започната в дадено състояние (какво ще има на листа, в какво състояние ще бъде човекът и от кой пакет ще бъде взет следващият лист). Сега е ясно, че човешките действия точно съответстват на работата на машина на Тюринг с голяма (но ограничена) азбука и голям (но ограничен) брой вътрешни състояния.

Въведение

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

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

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

Основни положения на машината на Тюринг

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

Машината на Тюринг се състои от три части: лента, глава за четене (запис) и логическо устройство, както е ясно показано на фигура 1.

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

Фигура 1 - Верига на машината на Тюринг

Машината на Тюринг работи в някаква произволна крайна азбука A = (_, a1…an) - тази азбука се нарича външна. Той съдържа специален знак - _, наречен празен знак - изпращането му до която и да е клетка изтрива знака, който преди е бил там, и оставя клетката празна. Във всяка клетка на лентата може да бъде записан само един знак. Информацията, съхранена на лентата, е представена от крайна последователност от знаци от външната азбука, различни от празния знак.

Главата винаги е разположена над една от клетките на лентата. Работата се извършва на цикли (стъпки). Системата от команди, изпълнявани от главата, е изключително проста: при всеки такт той заменя знака в наблюдаваната клетка ai със знака aj. В този случай са възможни комбинации:

1) аj = аi - означава, че знакът в наблюдаваната клетка не е променен;

2) ai? _, аj = _ - записаният в клетката знак се заменя с празен, т.е. изтрит;

3) аi = _, аj ? _ - празен знак се заменя с непразен (с номер j в азбуката), т.е. поставен е знак;

4) ai? аj ? _ - съответства на замяна на един знак с друг.

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

Въпреки това, въпреки че се случва действителното движение на лентата, обикновено се взема предвид движението на главата спрямо гледания участък. Поради тази причина командата за изместване на лентата наляво е обозначена с R (надясно), изместването надясно е L (наляво), а без изместване е обозначено със S (Стоп). Ще говорим конкретно за преместването на главата и ще считаме R, L и S за команди за нейното движение.

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

Обработката на информация и издаването на команди за писане на знак, както и преместване на лентата в машина на Тюринг, се извършва от логическо устройство (LU). LU може да бъде в едно от състоянията, които образуват краен набор и се обозначават с Q =(q1...qm, q0), а състоянието q0 съответства на завършване на работата, а q1 е началното (първоначално) състояние . Q заедно със знаците R, L, S образуват вътрешната азбука на машината. LU има два входни канала (ai, qi) и три изходни канала (ai+1, qi+1, Di+1). LU диаграмата на машина на Тюринг е показана на фигура 2.

Фигура 2 - LU диаграма на машина на Тюринг

Необходимо е да се разбере веригата, както следва: в цикъл i, знак от текущо гледаната клетка (ai) се подава към един вход на LU и се подава знак, показващ състоянието на LU в момента (qi). към другия вход. В зависимост от получената комбинация от знаци (ai, qi) и съществуващите правила за обработка, LU генерира и изпраща нов знак (ai+1) към наблюдаваната клетка през първия изходен канал, издава команда за преместване на главата (Di +1 от R, L и S), а също така дава команда за преминаване към следващото състояние (qi+1). Така елементарната стъпка (цикъл) на работата на машината на Тюринг е следната: главата чете символ от наблюдаваната клетка и в зависимост от нейното състояние и прочетения символ изпълнява команда, която указва кой символ да се запише ( или изтриване) и какво движение да направите. В същото време главата преминава в ново състояние. Работната схема на такава машина е показана на фигура 3.

Фигура 3 - Диаграма на функционирането на машина на Тюринг

Тази диаграма отразява разделението на паметта на външна и вътрешна. Външният е представен, както е посочено, под формата на безкрайна лента - предназначен е да съхранява информация, кодирана в символите на външната азбука. Вътрешната памет е представена от две клетки за съхраняване на следващата команда по време на текущия тактов цикъл: следващото състояние (qi+1) се прехвърля към Q от LU и се съхранява, а командата за смяна (Di+1) се съхранява в D . От Q, по линията за обратна връзка, qi+1 влиза в LU, а от D се изпраща командата към изпълнителния механизъм, който при необходимост премества лентата с една позиция надясно или наляво.

Общото правило, по което работи машината на Тюринг, може да бъде представено със следната нотация: qi aj > qi" aj" Dk, т.е. след като видите символа aj от главата в състояние qi, символът aj се записва в клетката, главата преминава в състояние qi и лентата прави движение Dk. За всяка комбинация qi aj има точно едно правило за трансформация (няма правила само за q0, тъй като машината спира, щом влезе в това състояние). Това означава, че логическият блок изпълнява функция, която свързва всяка двойка входни сигнали qi aj с една и само една тройка изходни сигнали qi "aj" Dk - тя се нарича логическа функция на машината и обикновено се представя под формата на таблица (функционална схема на машината), чиито колони са обозначени с държавни символи, а линиите са знаци на външната азбука. Ако има n знака на външната азбука и броят на състоянията на LU е m, тогава, очевидно, общият брой на правилата за трансформация ще бъде n×m.

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

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

Преди започване на работа на празна лента се записва начална дума a с крайна дължина в азбуката A; главата е инсталирана над първия знак на думата a, LU се прехвърля в състояние q1 (т.е. първоначалната конфигурация изглежда като q1a). Тъй като във всяка конфигурация се прилага само едно правило за трансформация, първоначалната конфигурация еднозначно определя всички последващи операции на машината, т.е. цялата последователност от конфигурации до прекратяване на експлоатацията.

В зависимост от първоначалната конфигурация са възможни два сценария:

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

2) няма спиране.

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

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

симулатор за обучение на универсалния изпълнител

Какво е?

Симулаторът на машината на Тюринг е модел за обучение на универсален изпълнител (абстрактна изчислителна машина), предложен през 1936 г. от А. Тюринг за изясняване на концепцията за алгоритъм. Според тезата на Тюринг всеки алгоритъм може да бъде написан като програма за машина на Тюринг. Доказано е, че машината на Тюринг е еквивалентна по своите възможности на машината на Пост и нормалните алгоритми на Марков.

Машината на Тюринг се състои от каретка (глава за четене и запис) и безкрайна лента, разделена на клетки. Всяка клетка от лентата може да съдържа знак от някаква азбука A=(a 0 ,a 1 ,…,a N ) . Всяка азбука съдържа знак за интервал, който се обозначава като 0 или Λ. При въвеждане на команди интервалът се заменя с долна черта "_".

Машината на Тюринг е автомат, който се управлява от маса. Редовете в таблицата отговарят на знаците от избраната азбука A, а колоните отговарят на състоянията на машината Q=(q 0 ,q 1 ,…,q M ) . В началото на своята работа машината на Тюринг е в състояние q 1 . Състояние q 0 е крайното състояние: веднъж в него машината прекратява своята работа.

Във всяка клетка от таблицата, съответстваща на някакъв символ a i и някакво състояние q j, има команда, състояща се от три части:

1. знак от азбуката А;
2. посока на движение: > (надясно),
3. ново състояние на машината

Новини

1. Фалина И.Н.Темата „Машина на Тюринг“ в училищния курс по информатика (inf.1september.ru).
2. Майер Р.В.Машини на Пост и Тюринг (komp-model.narod.ru).
3. Пилщиков В.Н., Абрамов В.Г., Вилиток А.А., Горячая И.В.Машина на Тюринг и алгоритми на Марков. Решаване на проблеми, М.: MSU, 2006.
4. Бекман И.Н.Информатика. Лекция 7. Алгоритми (profbeckman.narod.ru)
5. Соловьов А.Дискретна математика без формули (lib.rus.ec)
6. Ершов С.С.Елементи на теорията на алгоритмите, Челябинск, Издателски център SUSU, 2009 г.
7. Варпаховски Ф.Л.Елементи на теорията на алгоритмите, М: Просвещение, 1970 г.
8. Верещагин Н.К., Шен А.Изчислими функции, М: МЦНМО, 1999.

Какво да правим по въпроса?

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

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

Използване на менюто Панделкаможете да съхранявате състоянието на лентата във вътрешния буфер и да възстановите лентата от буфера.

В полето АзбукаПосочват се знаците от избраната азбука. Автоматично се добавя интервал към въведените знаци.

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

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

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

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

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

Ако забележите грешка или имате предложения, коментари, оплаквания, искания или становища, пишете.

Технически изисквания

Програмата работи под операционните системи на линията Windowsна всеки модерен компютър.

Разрешително

Програмата е безплатна за некомерсиална употреба. Изходният код на програмата не се разпространява.

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

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

1. 1) публикуване на материали под всякаква форма, включително публикуване на материали на други уеб сайтове;
2. 2) разпространение на непълни или променени материали;
3. 3) включване на материали в колекции на всякакви носители;
4. 4) получаване на търговски ползи от продажбата или друго използване на материали.

Изтеглянето на материали означава, че приемате условията на това лицензно споразумение.

Изтегли

След разопаковане на архива програмата е в изправност и не изисква допълнителни инсталации.

1. Описание на машината на Тюринг. 3

1.1 Свойства на машината на Тюринг като алгоритъм. 5

2. Сложност на алгоритмите. 7

2.1 Сложност на проблемите... 9

3. Машина на Тюринг и алгоритмично неразрешими проблеми.. 12

Заключение. 16

Използвана литература.. 18

Въведение

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

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

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

1. Описание на машината на Тюринг

Предисторията на създаването на тази работа е свързана с формулирането на нерешени математически проблеми от Дейвид Хилберт на Международния математически конгрес в Париж през 1900 г. Един от тях беше проблемът за доказване на последователността на система от аксиоми на обикновената аритметика, която Хилберт по-късно изясни като „проблем с разрешимостта“ - намиране на общ метод за определяне на удовлетворимостта на дадено твърдение на езика на формалната логика.

Статията на Тюринг дава точно отговор на този проблем - вторият проблем на Хилберт се оказва неразрешим. Но значението на статията на Тюринг надхвърля проблема, за който е написана.

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

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

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

краен набор от състояния – Q, в които може да се намира машина на Тюринг;

краен набор от лентови символи – Г;

функция δ (преходна функция или програма), която се определя чрез картографиране на двойка от декартовия продукт Q x Г (машината е в състояние qi и разглежда символа gi) в тройка от декартовия продукт Q x Г x (L ,R) (машината преминава в състояние qi, замества символа gi със символа gj и премества наляво или надясно един символ на лента) – Q x Г-->Q x Г x (L,R)

един знак от Г-->е (празно);

подмножеството Σ є Г - -> се определя като подмножество на входните символи на лентата, а е є (Г - Σ);

едно от състоянията – q0 є Q е началното състояние на машината.

Проблемът, който трябва да се реши, се уточнява чрез записване на краен брой символи от множеството Σ є Г – Si є Σ върху лента:

eS1S2S3S4... ... ...Sne

след което машината се прехвърля в изходно състояние и главата се монтира в най-левия непразен символ (q0,w) –, след което в съответствие със зададената преходна функция (qi,Si) - ->(qj, Sk, L или R), машината започва да замества гледаните символи, премества главата надясно или наляво и преминава към други състояния, предписани от функциите за преход.

Машината спира, ако преходната функция за двойката (qi,Si) не е дефинирана.

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

1.1 Свойства на машината на Тюринг като алгоритъм

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

Дискретност. Машината на Тюринг може да премине към (k + 1)-та стъпка само след завършване на всяка стъпка, тъй като всяка стъпка определя каква ще бъде (k + 1)-та стъпка.

Яснота. На всяка стъпка в клетката се записва символ от азбуката, автоматът прави едно движение (L, P, N) и машината на Тюринг преминава в едно от описаните състояния.

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

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

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

2. Сложност на алгоритмите

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

Обикновено изчислителната сложност на даден алгоритъм се изразява с помощта на нотацията „Голямо О“, тоест тя се описва от порядъка на големината на изчислителната сложност. Това е просто членът в разширението на функцията за сложност, който расте най-бързо с увеличаване на n, всички членове от по-нисък ред се игнорират. Например, ако времевата сложност на даден алгоритъм е 4n2+7n+12, тогава изчислителната сложност е от порядъка на n2, записана като O(n2).

Времевата сложност, измерена по този начин, не зависи от изпълнението. Не е необходимо да знаете точното време за изпълнение на различни инструкции, нито броя на битовете, използвани за представяне на различни променливи, нито дори скоростта на процесора. Един компютър може да е с 50 процента по-бърз от друг, а трети може да има два пъти по-широка шина за данни, но сложността на алгоритъма, измерена с порядък, няма да се промени. Това не е измама; когато работите с алгоритми, толкова сложни като тези, описани в тази книга, всичко останало може да бъде пренебрегнато (до постоянен фактор) в сравнение с порядъка на сложност.

Тази нотация ви позволява да видите как размерът на входните данни влияе върху изискванията за време и памет. Например, ако T = O(n), тогава удвояването на входните данни ще удвои времето за изпълнение на алгоритъма. Ако T=O(2n), тогава добавянето на един бит към входните данни ще удвои времето за изпълнение на алгоритъма.

Обикновено алгоритмите се класифицират според тяхната времева или пространствена сложност. Един алгоритъм се нарича постоянен, ако неговата сложност не зависи от n: 0(1). Един алгоритъм е линеен, ако времевата му сложност е O(n). Алгоритмите могат да бъдат квадратни, кубични и др. Всички тези алгоритми са полиномиални, тяхната сложност е O(m), където m е константа. Алгоритмите с полиномиална времева сложност се наричат ​​полиномиални времеви алгоритми

Алгоритми, чиято сложност е равна на O(tf(n)), където t е константа, по-голяма от 1, а f(n) е някаква полиномна функция от n, се наричат ​​експоненциални. Подгрупата от експоненциални алгоритми, чиято сложност е O(cf(n)), където c е константа и f(n) нараства по-бързо от константа, но по-бавно от линейна функция, се нарича суперполином.

В идеалния случай един криптограф би искал да твърди, че най-добрият алгоритъм за разбиване на проектиран алгоритъм за криптиране има експоненциална времева сложност. На практика най-силните твърдения, които могат да бъдат направени предвид текущото състояние на теорията за изчислителната сложност, са под формата на „всички известни алгоритми за атака за дадена криптосистема имат суперполиномиална времева сложност“. Тоест известните ни алгоритми за атака имат суперполиномиална времева сложност, но все още не е възможно да се докаже, че алгоритъм за атака с полиномиална времева сложност не може да бъде открит. Развитието на теорията за изчислителната сложност може някой ден да направи възможно създаването на алгоритми, за които съществуването на алгоритми с полиномно време на отваряне може да бъде изключено с математическа точност.

Машината на Тюринг е едно от най-интригуващите и вълнуващи интелектуални открития на 20 век. Това е прост и полезен абстрактен модел на изчисления (компютърни и цифрови), който е достатъчно общ, за да реализира всяка изчислителна задача. Благодарение на своето просто описание и математически анализ, той формира основата на теоретичната компютърна наука. Това изследване доведе до по-добро разбиране на цифровите изчисления и смятането, включително разбирането, че има някои компютърни проблеми, които не могат да бъдат решени на мейнфрейм компютри.

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

Машината на Тюринг е изчислително устройство, състоящо се от глава за четене/запис (или "скенер") с хартиена лента, преминаваща през нея. Лентата е разделена на квадрати, всеки от които носи един символ - "0" или "1". Целта на механизма е той да действа както като средство за въвеждане и извеждане, така и като работна памет за съхраняване на резултатите от междинните етапи на изчисленията. От какво се състои устройството Всяка такава машина се състои от два компонента: Неограничена лента. Тя е безкрайна в двете посоки и е разделена на клетки. Автоматично - управлявана програма, скенерна глава за четене и запис на данни. Може да бъде в едно от много състояния във всеки един момент.

Всяка машина свързва две крайни серии от данни: азбука от входящи символи A = (a0, a1, ..., am) и азбука от състояния Q = (q0, q1, ..., qp). Състоянието q0 се нарича пасивно. Смята се, че устройството прекратява работата си, когато го удари. Състоянието q1 се нарича начално - машината започва своите изчисления, докато е в началото в него. Въведената дума се намира на лентата, по една буква в ред на всяка позиция. От двете му страни има само празни клетки.

Как работи механизмът

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

Свойства на механизма

Машината на Тюринг, подобно на други изчислителни системи, има присъщи характеристики и те са подобни на свойствата на алгоритмите: Дискретност. Дигиталната машина преминава към следващата стъпка n+1 само след завършване на предходната. Всяка изпълнена стъпка задава какво ще бъде n+1. Яснота. Устройството извършва само едно действие за една клетка. Въвежда знак от азбуката и прави едно движение: наляво или надясно. Детерминизъм. Всяка позиция в механизма отговаря на един единствен вариант за изпълнение на дадена схема, като на всеки етап действията и последователността на тяхното изпълнение са еднозначни. Производителност. Точният резултат за всеки етап се определя от машина на Тюринг. Програмата изпълнява алгоритъма и в краен брой стъпки преминава в състояние q0. Масов характер. Всяко устройство е дефинирано върху валидните думи, включени в азбуката. Функции на машината на Тюринг Алгоритмите за решаване често изискват внедряването на функция. В зависимост от възможността за записване на верига за изчисление, функцията се нарича алгоритмично разрешима или неразрешима. Като набор от естествени или рационални числа, думи в крайна азбука N за машината, се разглежда последователността на множеството B - думи в рамките на азбуката на двоичния код B = (0.1). Освен това резултатът от изчислението взема предвид „недефинираната“ стойност, която възниква, когато алгоритъмът замръзне. За да се приложи функцията, е важно да има формален език в крайната азбука и да се реши проблемът с разпознаването на правилните описания.-

Програма на устройството

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

Компоненти за изчисления

За да изградите машина на Тюринг за решаване на конкретен проблем, трябва да дефинирате следните параметри за нея. Външна азбука. Това е определен краен набор от символи, обозначени със знака А, съставните елементи на който се наричат ​​букви. Един от тях - a0 - трябва да е празен. Например, азбуката на устройство на Тюринг, работещо с двоични числа, изглежда така: A = (0, 1, a0). Непрекъсната верига от букви и символи, записани на лента, се нарича дума. Автоматично устройство е устройство, което работи без човешка намеса. В машината на Тюринг тя има няколко различни състояния за решаване на проблеми и при определени условия, които възникват, преминава от една позиция в друга. Наборът от такива състояния на каретка е вътрешната азбука. Има буквено обозначение под формата Q=(q1, q2...). Една от тези позиции - q1 - трябва да бъде началната, тоест тази, която стартира програмата. Друг необходим елемент е състоянието q0, което е крайното състояние, тоест това, което завършва програмата и довежда устройството до позиция за спиране.

Преходна маса.

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

Алгоритъм за машината

По време на работа каретката на устройството Turing се управлява от програма, която по време на всяка стъпка изпълнява последователност от следните действия: Записване на символ от външната азбука на позиция, включително празна, замяна на елемента, който е бил в то, включително празен. Преместване на една клетка наляво или надясно. Промяна на вашето вътрешно състояние. По този начин, когато пишете програми за всяка двойка знаци или позиции, е необходимо да се опишат точно три параметъра: ai - елемент от избраната азбука A, посоката на изместване на каретката („←“ наляво, „→“ към дясно, "точка" - без движение) и qk - ново състояние на устройството. Например команда 1 “←” q2 има значението “заменете знака с 1, преместете главата на каретката наляво с една стъпка-клетка и направете преход към състояние q2”.