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

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

Всъщност Post, за разлика от Тюринг, не използва термина “машина”, а нарече модела си алгоритмична система. Както е обичайно в литературата, ние все още ще говорим за Пощенската машина, като по този начин подчертаваме единството на подходите на двамата автори [41].

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

Ние ще се съгласим да определим главата със знака “С” над проучваната секция, а етикетът - със знака “М” в секцията. Празният раздел не съдържа никакъв знак. В една мярка (нарича се стъпка), главата може да премести един участък надясно или наляво и да постави или изтрие марка. Работата на пощенската машина обхваща прехода от едно състояние на машината към друго в съответствие с дадена програма, която е изградена от индивидуални команди. Всяка команда има следната структура: xKu, където x е номерът на изпълняваната команда; K - индикация за извършеното действие; y е номерът на следващата команда (наследник). Системата от команди на машината, включваща шест действия, е представена в табл. 7.1.

Таблица 7.1.

Този списък трябва да бъде допълнен със следните условия:

· Командата <xMy> може да се изпълни само в празен раздел;

· Командата <хСу> може да се приложи само към запълнената секция;

· Броят на наследника на всеки отбор (и) трябва да съответства на номера на екипа, който се изисква в тази програма.

Ако тези условия не са изпълнени, настъпва неефективно спиране на машината, т.е. спрете до планирания резултат. За разлика от тази ситуация, спирането при командата <x stop> е ефективно, т.е. това се случва след получаване на резултата от алгоритъма. Освен това е възможна ситуация, когато машината никога не спира - това се случва, ако нито една от командите не съдържа командния номер на стоп като последовател или програмата не преминава към тази команда.

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

Целото число k се записва на лентата на пощенската машина посредством k + 1 последователно маркирани секции, т.е. използва се унарната система с номера (виж § 4.1). Съседни записи на номера на лентата са разделени от една или повече празни секции. По-долу е даден пример за писане на цифри 0, 2 и 3.

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





Вижте също:

Пример 4.1

Изпълнител на алгоритъм

Тестови въпроси и задачи

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

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

2019 @ ailback.ru