Машина посты

жүктеу 43,71 Kb.

Дата	27.10.2022
өлшемі	43,71 Kb.
	#39877
түрі	Дерексіз

Машина посты 3 СРСП

Орындаған:Мұратұлы Қ.

Тексерген:Алиева A.

Машина посты

Пост машинасы-алгоритм ұғымын нақтылау (формализациялау) үшін жасалған дерексіз (нақты емес) есептеу машинасы. Бұл бастапқы деректерді енгізуге және бағдарламаның нәтижесін оқуға мүмкіндік беретін әмбебап Орындаушы.

1936 жылы американдық математик Эмиль Пост мақалада алгоритмдік қарапайымдылыққа ие және бір немесе басқа есептің алгоритмдік түрде шешілетінін анықтауға қабілетті жүйені сипаттады. Егер тапсырмада алгоритмдік шешім болса, онда ол пост машинасына арналған командалар түрінде ұсынылады.

Пост машинасы мыналардан тұрады бірдей ұяшықтарға (бөлімдерге) бөлінген шексіз таспа. Ұяшық бос болуы мүмкін (0 немесе бос) немесе жапсырманы (1 немесе кез келген басқа белгі) қамтуы мүмкін,

таспамен бір ұяшыққа бір немесе басқа бағытта қозғалуға қабілетті, сондай-ақ белгінің бар-жоғын тексеруге, белгіні өшіруге және жазуға қабілетті бастар (кареткалар).

Пост машинасының ағымдағы күйі таспаның күйімен және вагонның орналасуымен сипатталады. Таспа күйі-туралы ақпарат,

Пост машинасы үшін командалардың барлығы алты түрі бар:

V j-белгіні қойыңыз, бағдарламаның j-ші жолына өтіңіз.
X j-жапсырманы өшіріңіз, бағдарламаның j-ші жолына өтіңіз.
< - j-солға жылжып, бағдарламаның j-ші жолына өтіңіз.
- >j-оңға жылжу, бағдарламаның j-ші жолына өту.
? j1; j2-егер ұяшықта белгі болмаса, онда бағдарламаның j1-ші жолына өтіңіз, әйтпесе бағдарламаның j2-ші жолына өтіңіз.
! - бағдарламаның соңы (тоқтату).
"Тоқтату" командасының сілтемесі жоқ.

Пост машинасында бағдарламаны аяқтаудың нұсқалары:

"Тоқтату" командасы-дұрыс аялдама. Бұл дұрыс жазылған алгоритмді орындау нәтижесінде пайда болады.
Жарамсыз команданы орындау-нәтижесіз тоқтату. Бас белгіні бұрыннан бар жерде жазуы керек немесе ол жоқ жерде белгіні өшіруі керек жағдайлар төтенше жағдай болып табылады (жарамсыз).
Шексіздікке, циклге кету. Алгоритм жұмысының нәтижесінде пост машинасы мүлдем тоқтамауы мүмкін (ешқашан "тоқтату" пәрменіне жетпеңіз және төтенше жағдаймен аяқталмаңыз).
Қарапайым әрекеттер (командалар) пост машинасы Тьюринг машинасының командаларына қарағанда қарапайым. Сондықтан пост машинасының бағдарламаларында ұқсас Тьюринг машинасының бағдарламаларына қарағанда командалар саны көп.
Неліктен екі түрлі таңба жеткілікті (белгі бар, белгі жоқ)? Мәселе мынада, кез-келген алфавитті екі таңбамен кодтауға болады; алфавитке байланысты алфавит әрпіндегі екілік таңбалардың саны ғана артуы мүмкін.

жүктеу 43,71 Kb.

Достарыңызбен бөлісу: