Дәріс №4. Автомат ақпараттық жҥйенің негізгі элементі ретінде. Абстрактылы автоматтар Дәріс жоспары: 4.1 ЭЕМ - бағдарламалық басқарылатын цифрлы автомат
4.2 Тьюринг машинасы
4.3 Пост машинасы
4.1 ЭЕМ - бағдарламалық басқарылатын цифрлы автомат Абстрактылы (яғни тек адам қиялында ғана болатын) Пост және Тьюринг
машиналары бағдарламалардың қасиеттері туралы әр тҥрлі тҧжырымдарды
дәлелдеу ҥшін ойлап шығарылды. Бҧл бір-біріне тәуелсіз екі есептеу
машиналарының моделін (практикада бір уақытта) 1937 жылы Алан Тьюринг
ҧсынды. Бҧл машиналар толық детерминделген әмбебап орындаушылар болып
табылады. Олар алғашқы деректерді енгізіп, бағдарлама орындалғаннан кейін
нәтижені оқуға мҥмкіндік береді. Тьюринг машинасына қарағанда Пост
машинасы қарапайым болғанымен кең таралмаған.
4.2 Тьюринг машинасы Бҧл елестегі машина - яғни ―қағаз бетіндегі‖ машина немесе машинаның
математикалық моделі.
Тьюринг машинасы - таза абстракция және ешқашан жасалмаған. Оның
пайдасы тҥрлі есептер шешімінің алгоритмі бар немесе жоқ екендігін
дәлелдеуге болады. Машина белгілі бір алгоритмді орындайтын болғандықтан,
бҧл машинаға алгоритмнің қасиеттерінен талаптар қойылады. Біріншіден,
машина толықтай детерминенделген (есептеулер нақты және жалпы тҥсінікті)
болуы қажет және тапсырылған ережелер жҥйесі негізінде әрекет етуі керек.
Екіншіден, ―бастапқы мәліметтерді‖ енгізуге мҥмкіндік беруі қажет.
Ҥшіншіден, берілген машинаның жҧмыс жасау ережелерінің жҥйесі және
шешілетін есептердің класы машина жҧмысы нәтижесін оқи алатындай болып
келістірілуі керек.
Тьюринг тезисі кез-келген алгоритмді Тьюринг машинасына салып
шешуге болатынға негізделген.
