Информатика пә
жүктеу/скачать 1,41 Mb.
|
МК-Лекция
- Бұл бет үшін навигация:
- Қолданылған әде б иеттер [4], [7], [25], [34], [33]. Бақылау сұрақта р ы
| 2. Тъюринг машинасы
Тьюринг машинасы – абстрактілі орындаушы (абстрактілі есептеуіш машина). Оны 1936 жылы алгоритм түсінігін бейнелеу үшін Алан Тъюринг ұсынды. Тьюринг машинасы ақырлы автоматтың кеңейтілген түрі болып табылады және Чёрч-Тъюринг тезисіне сәйкес қандай да бір әдіспен процесті қадамдап есептеуді жүзеге асыра-тын барлық басқа да орындаушыларды бейнелей алады. Бұл құрылғының ұяшықтарға бөлінген шексіз ұзын таспасы бар. Әрбір ұяшық бос болуы немесе ақырлы тізімнен таңдалған символдан тұруы мүмкін. Сонымен қатар Тъюринг машинасының таспа бойымен қозғалып, символды жазып немесе оқи алатын головкасы бар. Машинаның ішкі күйі болады, ол тоқтатылған күйде немесе 0 мен қандай да бір максималды шама аралығында көрсетілуі мүмкін. Машина тоқтатылған күйге көшкенде ол есептеуді тоқтатады. Тъюринг машинасы қарапайым, дегенмен қазіргі компьютерде орындалатын есептер Тъюринг машинасында орындала алады. Тъюринг машинасы орындайтын әрекет машина күйінен және головка үстінде тұрған ұяшықтағы символдан тәуелді. Осы ақпарат негізінде (күйі немесе головканың астындағы символ) Тъюринг машинасы төмендегі үш әрекеттің бірін орындай алады: Ұяшыққа символды жазу (өзінде жазулы тұрған символ болуы да мүмкін); бір ұяшық оңға немесе солға қозғалту; ішкі күйін орнату (мүмкін машинанің қазіргі күйі). Тьюринг машинасы таспадан оқылған әртүрлі ағымдық күйлер мен символдар комбинациясы болған жағдайда анықталатын кесте немесе ережеге сәйкес жұмыс жасайды. Қолданылған әдебиеттер [4], [7], [25], [34], [33]. Бақылау сұрақтары: 1. Ақырлы автомат деген не? 2. Басқару құрылғысы 3. Тъюринг машинасы деген не? 4. Тъюринг машинасының жұмыс істеу принципі. жүктеу/скачать 1,41 Mb. Достарыңызбен бөлісу:
|