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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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