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

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

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

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

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

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

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

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

№	команда	Командалардың жазылуы	Машина әрекетінің сипаттамасы
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.
   

• 
  есептелетін функция ұғымы
  
• 
  Рекурсия ұғымы, рекурсивті функция
  
• 
  Компьютер көмегімен есептелетін функциялар теориясы.
  
• 
  Черч тезисі
  

Анықтама. Әлдебір алгоритм көмегімен есептелетін функцияны есептелетін функция дейді.

Іс жүзінде алгоритм – функцияны беру әдісі. Ал функция таблица, схема, формула түрінде берілуі мүмкін. Бірақ кейбір процестерде бастапқы енгізілген немесе берілген деректер мен алынған нәтижедегі деректер арасындағы байланысты ұйымдастыратын функцияны құру қиын, күрделі.

1 – бағыт Рекурсивті функциялар – есептелетін функциялар ұғымымен байланысты.

X және Y жиындары бар болсын. X жиынының кейбір элементтеріне Y жиынының элементтері сәйкес келсе, онда Y – те X – тен бөлшекті функция берілген дейді.

Y жиынында сәйкес элементтері бар және X элементтерден құралған жиынның элементтер жиыны функцияның анықталу облысы деп аталады.

X жиынында сәйкес элеметтері бар Y жиынының элементтер жиыны функцияның мәндер облысы деп аталады.

Егер X –тен Y-тегі функцияның анықталу облысы X жиынымен беттессе, онда ол функцияны барынша анықталған деп атайды.

Осы ұғымға және рекурсивті функцияға негізделіп алгоритмнің дәл анықтамасын құруға болады.

Кез – келген берілген деректерді (үзілісті, дискретті) әлдебір санау жүйесінде натурал сандармен кодтауға болады, онда