Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Алгоритмична машина на Тюринг

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

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

Както в Пощенската машина, лентата е разделена на отделни клетки, но в машината на Тюринг главата е неподвижна и лентата се движи спрямо нея надясно или наляво. Друга разлика е, че тя не работи в двоичното, а в някаква произволна крайна азбука A = {∆, и 1 , ... но n } - тази азбука се нарича външна. В него се откроява специален символ - ∆, наречен празен символ - изпращането му в клетка изтрива предишния символ и оставя клетката празна. Във всяка клетка на лентата може да бъде записан само един знак. Информацията, която се съхранява на лентата, е изобразена с крайна поредица от символи на външна азбука, различни от празния символ.

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

J = i - това означава, че в наблюдаваната клетка знакът не се е променил;

· I, 0, j = 0 означава, че запаметеният в клетката знак се заменя с празен, т.е. изтриват;

· I = 0, j means 0 означава, че празният символ се заменя с непразен (с число j в азбуката), т.е. Маркировката е поставена;

· Ij correspond 0 съответства на замяната на един знак с друг.

Така машината на Тюринг реализира система от изключително прости команди за обработка на информация, които бяха обсъдени в Раздел 7.3.1. Тази система от команди за обработка също се допълва от изключително проста система от команди за преместване на лентата: към клетката вляво, към клетката надясно и остава на място, т.е. адресът на наблюдаваната клетка в резултат на изпълнението на командата може да се промени на 1 или да остане непроменен. Въпреки това, въпреки че лентата всъщност се движи, обикновено се смята за изместване на главата спрямо наблюдаваната секция - поради тази причина командата за преместване на лентата вляво е обозначена с R („дясно“), преместване надясно - L („ляво“) и без промяна - S („стоп“). Най- Отсега нататък ще говорим за преместването на главата и ще разглеждаме R, L и S като екипи на неговото движение. Елементарният характер на тези команди означава, че когато е необходимо да се отнася до съдържанието на дадена клетка, то се търси само чрез верига от отделни смени на клетка. Разбира се, това значително удължава процеса на обработка, но позволява да се направи без номерирането на клетките и използването на командите за получаване на адрес, т.е. намалява броя на наистина елементарните стъпки, което е важно в теоретичен план.

Обработката на информация и издаването на команди за записване на маркировката, както и смяна на лентата в машината на Тюринг, се извършва от логическо устройство (LU). Тя може да бъде в едно от състоянията, които образуват крайно множество и са означени с Q = { q 1 ... q m , z } , още повече, че състоянието z съответства на завършването на работата, а q 1 е първоначалното (първоначалното). Q заедно със знаците R, L, S образуват вътрешната азбука на машината. LU има два входни канала ( a i , q i ) и три изхода (a i + 1 , q i + 1, D i +1 ) (виж фигурата):

Схемата трябва да се разбира по следния начин: при цикъл i , знак от текущо гледаната клетка ( a i ) се изпраща на един вход на LU и на друг вход, знак, показващ състоянието на LU в момента ( q i ). В зависимост от получената комбинация от символи ( a i , q i ) и съществуващите правила за обработка, LU генерира и изпраща нов знак ( a i +1 ) към първия изходящ канал (D i + 1) от R, L и S ), а също така дава команда за извикване на следващия контролен знак (q i + 1 ). По този начин, елементарната стъпка (цикъл) на операцията на машината на Тюринг е следната: главата чете знак от наблюдаваната клетка и, в зависимост от неговото състояние и прочетения символ, изпълнява команда, която показва кой символ да пише (или изтрива) и какво движение да изпълнява , В този случай главата преминава в ново състояние. Схемата на функциониране на такава машина е показана на фиг. 7.2.

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

Общото правило, с което работи машината на Тюринг, може да бъде представено със следния запис: q i a jq i ' a j ' D k , т.е. след преглед на знака a j с главата в състояние a i , знакът a j 'се записва в клетката, главата преминава в състоянието q i ', а лентата прави движението D k . За всяка комбинация q i a j има едно единствено правило за преобразуване (няма правила само за z , тъй като веднъж в това състояние машината спира). Това означава, че логическата единица изпълнява функция, която свързва всяка двойка входни сигнали q i a j с един и само един трикратен изход q i a a j ' D k - той се нарича логическа функция на машината и обикновено се представя като таблица (функционална схема на машината), колони от които са обозначени със символи на състояния, а редовете - със знаци на външната азбука. Ако символите на външната азбука са n, а броят на състоянията на dL е , тогава очевидно общият брой на правилата за преобразуване ще бъде n. T.

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

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

Съвкупността от състоянията на всички клетки на лентата, състоянието на Linac и положението на главата се нарича конфигурация на машината.

Конфигурацията може да бъде записана по следния начин: 1 a 1 q i a j ... и k means, което означава, че раздел j се разглежда в дума от k символа и устройството за управление е в състояние q i . Ясно е, че конфигурацията на машината може да съдържа произволен брой знаци във външната азбука и само един символ във вътрешната. Често конфигурацията се записва като α 1 q i α 2 , където α 1 е думата на лентата вляво от главата, а 2 е думата на лентата отдясно на главата, включително и знака, който трябва да се види. Вляво от α 1 и отдясно на α2 , лентата е празна. Конфигурацията, показана на фиг. 7.1., Може да се запише както следва: a 1 2 a 2qa 3 a 4 a k , на фиг. 7.2.-1 q 1111.

Преди започване на работа оригиналната дума α на крайната дължина в азбуката А се изписва на празна лента ; главата е поставена над първия знак на думата а, LL се прехвърля в състоянието q 1 (т.е. първоначалната конфигурация е q 1 a ). Тъй като във всяка конфигурация е приложено само едно правило за преобразуване, първоначалната конфигурация уникално определя цялата следваща операция на машината, т.е. цялата последователност от конфигурации до приключване на работата.

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

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

· Стоп не се случва.

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





Вижте също:

Компютърно кодиране и обработка на неподписани числа

Еквивалентни автомати

Пример 4.13

Пример 7.8

Общата схема на предаване на информация в комуникационната линия

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru