Пост алгоритмдік машинасы алгоритм ұғымын дәлелдеуші

Бұл машинаның Тьюрингтен айырмашылығы – ол өзінің теориясында «машина» емес «алгоритмдік жүйе» деген терминді қолданған.

Оның абстрактылы машинасы бірнеше бірдей секцияларға бөлінген, оқу-жазу инесі бар шексіз лентадан тұрады. Әр секция бос немесе толтырылған болуы мүмкін. Лентаға түк жазылмаса секция бос, лентаға жазылып белгі түссе секция толық деп есептеледі.

Лента жағдайы процесс уақытында өзгермелі болды. Осы лента жағдайы мен оқу-жазу инесінің орны туралы ақпарат Пост машинасының жағдайын айқындайды.

Инені «», метка-белгі М болсын. Секция бос болса, ешбір белгі түспейді. Бір қадам жасағанда ине оңға немесе солға 1 қадам жылжып белгіні салады немесе өшіреді. Программадағы командаларға сәйкес машина 1 жағдайдан келесі жағдайға көшіп отырады.

Әрбір команданың структурасы ХКУ болсын,

Х – орындалатын команда нөмірі,

К – орындалатын әрекет туралы нұсқау,

У – келесі команда нөмірі.

№	команда	Командалардың жазылуы	Машина әрекетінің сипаттамасы
1	Оңға қадам	ХУ	Инені оңға қарай 1 секцияға жылжыту
2	Солға қадам	ХУ	Инені солға қарай 1 секцияға жылжыту
3	Белгі салу	Х V У	Секцияға белгі қойылады
4	Белгіні өшіру	Х x У	Секциядан белгі өшіріледі
5	Басқаруды ауыстыру	Х У1 У2	Секцияда белгі жоқ болса басқару у1 командасына, әйтпесе у2 командасына беріледі
6	тоқтату	Х стоп !	Машина жұмысын тоқтатады
7	Тармақты ұйымдастыру	? a; b	Ұяшықты қарау, егер ұяшықта 0 тұрса, онда а номерлі командаға көші, әйтпесе b нөмірлі командаға көшу.

Бұл әрекеттерге қойылатын қосымша шарттар:

• 
  ХМУ командасы бос секцияда орындалмайды
  
• 
  ХсУ командасы толық секцияда орындалады
  
• 
  У командасының нөмірі программадағы бар команда нөмірімен сәйкес болуы керек.
  

Пост машинасы оң бүтін сандарды жазуды қарастырады, себебі кез келген сөз цифр түрінде кодталады.

Лентада К бүтін саны К+1 келесі белгіленген секцияларда, унарлы санау жүйесі қолданылып жазылады.

0,2,3 сандарыныің жазылуы:

Өзін тексеру сұрақтары

1. Алгоритмдік машиналардың шығуына не себеп болды?

2. Пост және Тьринг машиналарының айырмашылықтары?

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.