Абстрактно (т.е., не е реално, но само във въображението) Post машина и Тюринг предназначен за доказване на различните твърденията за програми за тези имоти са били предложени независимо една от друга (и почти едновременно) през 1936 г., американският математик Емил Пост и английския математик Алън Тюринг. Тези машини са разнообразни изпълнители, които са напълно решени да позволи "влиза" По първоначални данни, както и след приключване на програмата, за да "четат" резултата. Мнение машина е по-малко популярен, въпреки че е много по-лесно да Тюринг машини. Можете да го използвате за провеждане на обучението на първите умения на програмиране за компютри.
Абстрактната машината Великия пост е безконечна лента, която е разделена на две равни клетки, всяка от които могат да бъдат или пълни или празни Tagged «V», и глава, която може да се движи по протежение на лентата в една клетка надясно или наляво, за да предизвика етикета клетъчната лента, ако този етикет не е бил там преди, изтриване на марката, ако е било, или с отметка в клетка. Информация за PLACEHOLDERS клетки ленти характеризира състоянието на лентата, която може да се променя по време на работа на машината. По всяко време на главата ( "-") се намира на една от лентите и клетките се казва, че го пренебрегват. Информация за местоположението на главата със състоянието на лентата описва състоянието на машината Post, фиг. 1.16.
Фиг. 1.16. Абстрактната машината заговезни
Екип Мнение машина има следната структура:
където п - брой отбори, K е извършено действие от страна на главата, която е - броят на следващата инструкция, която да бъде изпълнена.
Има само шест отбора Мнение машина, фиг. 1.17:
Фиг. 1.17. Публикувайте машинни команди
Ситуации, в които глава трябва да бъде за прилагане на етикета, когато е наличен, или обратно, за изтриване на етикета, когато не е налице, са ненормално (недопустими).
Програма за машината Post ще се нарича който не е празен списък от команди, така че 1) на н-о място отбор с броя н; 2) броя на тона на всеки екип на същите, както на броя на списък от команди.
По отношение на свойствата на алгоритмите се изучават с помощта на машината Post, най-интересните са причините за спиране на машината, когато програмата е:
1) спиране на команда "Стоп"; този стоп се нарича точкуване и точки за правилността на алгоритъма (програма);
2), когато спре нелегалната инструкция; в този случай, на спирка се нарича без резултат;
3) Машината никога не спира; в този и в предишния случай, ние се занимаваме с една дефектна алгоритъм (програма).
Ние ще разберем от първоначалното състояние на главата срещу празните клетки в ляво от най-лявата маркировка на лентата.
Помислете за изпълнението на някои от най-характерните елементи на програмата за публикация машина.
1. Нека първоначално състояние на главата и е необходимо да се напише празна лента два етикета: едната в участъка под главата, а вторият от дясно на него. Можете да направите това, като следвате програмата (от дясно на командата показва резултата от изпълнението му):
Фиг. 1.18. Пример публикация машина програма елемент
2. Ние ще покажем как можете да използвате инструкция за условно отклонение за организацията на цикличен процес. Нека лентата има запис на няколко марки в един ред, а главата е над марката в дясно. Вие искате да прехвърлите на главата наляво до първата празна позиция.
Програмата ще бъде, както следва:
Условно клон команда е един от основните инструменти организация циклични процеси, например за намиране на първия етикет отдясно (или ляво) на главата намира над празна клетка; намиране наляво (или надясно) от глава празна клетка, ако тя се намира над етикета, и т.н.
3. Нека разгледаме представянето на числата върху лентата на машината Post и извършване на действия с тях.
К на брой е представена на машината лента пости последователни к + 1 етикети (един етикет показва броя на "О"). Между двете числа е интервал от най-малко един празен участък от лентата. Например, рекорден брой 3 и 5 за поста на магнетофон ще изглеждат по следния начин:
Имайте предвид, че се използва в системата на Пощенска машинни номера запис е nonpositional.
Да се изготви програма за добавяне на произволен брой единици. Да предположим, че на касета, записана само един номер и главата се поставя върху една от клетките, в които етикета принадлежи този брой:
на главата може да бъде преместен за решаване на проблема наляво (или надясно) до първата празна клетка, а след това се прилага на етикета.
Програмата, която води до увеличаване на броя на марката в ляво е:
Програмата, която води до увеличаване на броя на етикета на правото е в следния формат:
(Единствената разлика е, посоката на движение на главата в първия отбор. Проверка на функционирането на тези програми в конкретни примери).
Да приемем, че главата е позиционирана на разстояние от няколко клетки от лявата страна на номера, към който искате да добавите един. В този случай, програмата е сложно. "Търси номерата" - два отбора, които водят главата, обсъдено в предишния пример състояние:
По-долу - пълния текст на програмата, като добави една наляво и надясно, съответно:
В първия случай не е необходимо да се движи главата на най-лявата част на етикета,
4. Ето програма за добавяне на не-отрицателни числа и и пощи машина, когато главата е в сравнение с броя на, и б е броят на правото и на няколко клетки. Тази програма изпълнява следния алгоритъм: първото число е постепенно се навежда до секундата, докато те се сливат, а след това изтрива един етикет (в противен случай резултатът щеше да е с един повече от дясно).
В случай на по-сложни начални условия, когато неизвестното, към дясната или лявата част на главата (и в продължение на няколко клетки) е число, то е възможно да се приложи този принцип търсене на: преместване на главата надясно и наляво, и като отбелязва марка степента на отстраняване на главата от началната позиция, за да намерите броя, и след това се прилага най-известните допълнение програмата. Тя проверява дали главата се намира над един от номерата на етикета и ако е така, проблемът е решен. В противен случай, той се проверява дали секцията е празна дясната страна на главата и да го следва; ако и двете са празни, а след това направи завръщането на главата с една стъпка и да постави етикет, а след това една и съща операция се извършва в ляво и се отправят към маркираната пътека обратно към правото и т.н. толкова дълго, колкото главата е да не се удари редица, а след това можете да приложите по-рано обсъждат по-горе програма:
Мнение машина може да се разглежда като един опростен модел компютър. В действителност, като компютри и машина Великия пост са:
• неделими носители на данни (клетки - бита), които могат да се пълнят или незапълнени;
• ограничен брой елементарни операции - екипи, всяка от които
се извършва в един цикъл (смола).
Свързани статии