Ы., Баймұсаева А. Б. Информатиканың теориялық негіздері
Тьюринг машинасы. Тьюринг машинасы - құрылымына бос немесе белгіленген алфавиттің символы бар ұяшықтарға бөлінген шексіз таспамен әрекеттесетін шектеулі анықталған автомат кіретін абстракты автомат
жүктеу/скачать 314.17 Kb.
|
Тьюринг машинасы. Тьюринг машинасы - құрылымына бос немесе белгіленген алфавиттің символы бар ұяшықтарға бөлінген шексіз таспамен әрекеттесетін шектеулі анықталған автомат кіретін абстракты автомат.Тьюринг ықтималдық машинасы — бір таспасында символдардың кездейсоқ тізбектігі жазылган (әр адымда осы таспадағы бір символ оқылатын) көп таспалық машина. Тьюринг машинасы Пост машинасына ұқсас, бірақ басқаша жұмыс істейді. Тьюринг машинасы (ТМ) есептеу таспадан (ұяшықтарға бөлінген және оң жақтан емес, сол жақтан шектелген), оқитын және жазатын бүркеншіктен, таспа созылынқы механизмнен және кейбір ақырғы жиынтыққа жататын q0, q1, ..., qs дискретті қалып-күйдін бірінде орналасатын операциондық орындаушы құрылғыдан тұрады. Мұнда q0 бастапқы қалып - күйі деп аталады. Оқылатын және жазылатын бүркеншік A = {a0, a1, ..., at} жұмыс әліпбидің әріптерін оқи алады, оларды өшіре және басып шығара алады. Таспаның әрбір ұяшығы әрбір уақыт мезетте А жиынның әріптерімен бос емес. Жиі a0 – «бос орын» әріпі кездеседі. Бүркеншік әрбір уақыт мезетте таспаның кейбір ұяшығының үстінде – ағымдағы жұмыс ұяшығында орналасады. Таспа созылынқы механизмі бүркеншік таспаның көршілес ұяшығының үстінде болатындай етіп таспаны ауыстыра алады. Бұл кезде таспаның сол жақ шетіне (СЖШ) шығып кетуі мүмкін, оны авариялық (жарамсыз), немесе машина тоқтату туралы ұйғарымды орындайтын машинналық тоқтату (МТ) болып табылады. ТМ жұмыс реті (a0, a1,..., at жұмыс әліпебимен және q0, q1,..., qs қалып-күйлерімен) Тьюринг машинасының кестесімен түсіндіріледі. Бұл кесте төрт бағанасы және (s + 1)(t + 1) жолы бар матрица. Әрбір жолдың келесі түрі бар qi aj vij qij, 0 £ i £ s, 0 £ j £ t, qij Î {q0, q1,..., qs}. Мұнда vij арқылы {a0, a1, ..., at} әліпби біріктіру элементі мен таспа созылынқы механизм үшін ұйғарымдар жиыны Л – таспаны сол жаққа қарай ауыстыру, П – таспаны он жаққа қарай ауыстыру, С – машинаны тоқтату (ТОҚТА) белгіленген; vij –ұяшыққа a0, a1, ..., at әліпбидің таспа символын енгізуден, бүркеншітін жылжуынан, машина тоқтауынан тұратын ТМ-ның әрекеті; qij келесі қалып-күй болады. ТМ келесі ережелерге сәйкес жұмыс істейді: егер ТМ qi қалып-күйде болса, бүркеншік жұмыс торында aj символын оқиды. Кестеде qi aj символдарынан басталатын qi aj vij qij жол бір рет кездеседі дейік. Егер vij – жұмыс әліпбидің әріпі болса, онда бүркеншік жұмыс ұяшығының ішіндегісін өшіріп, онда осы әріпті енгізеді. Егер vij –таспа созылынқы механизм үшін r немесе l командасы болса, онда лента оң жаққа қарай немесе сол жаққа қарай бір ұяшыққа жылжытылады (егер таспаның сол жақ шетіне шығып кетпесе). Егер vij = s, онда машиналық тоқтату болады. Тьюринг машинасы өз жұмысын кейбір бастапқы сырт пішінінен бастайды. Ол өзіне А жұмыс әліпбидің бір символын қамтитын бастапқы жағдай (q0) мен таспаның нақты ұяшығының үстіндегі оқып-жазатын бүркеншіктің орналасуынан тұрады. ТМ ның жұмыс әліпбиінде әр түрлі символдарының бар болуы таспада еркін мәтіндік және сандық ақпаратты көрсетуге мүмкіндік береді, ал ТМ басқарушы ортасының өтетін жерлері әр түрлі жағдайларда жұмыстың ағымдағы нәтижелерін Тьюринг машинасымен есте сақтауға модельдейді. ТМ-ның жұмыс ретін анықтайтын кесте программа болмайды (оның ұйғарымдары бірінің соңында бірі тізбектелінбей орындалады, таспада бар кейбір мәтіндегі символдарды ауыстыруын суреттейді). ТМ-ның кестесін жиі Тьюринг машинасының схемасы деп атайды. Тьюринг машинасының схемасы — ағымдағы әрекетке тәуелді Тьюринг машинасының барлық мүмкін болатын қадамын санау (ақырғы емес қалып-қүй, қабылданатын символ). Комбинация, әдетте, екі кірісі бар кесте түрінде беріледі, кестенің тор көзінде Тьюринг машинасы қадамының коды (машинаның командалары) болады. Тьюринг машинасының схемасы мысалын қарастырайық. Ондық санау жүйесіндегі n санына бірлікті қосу алгоритмі. n санның ондық жазуы берілсін (n натурал санның ондық санау жүйесіндегі өрнектелуі); n+1 санның ондық жазуын алу керек. Айқын, ТМ-ның сыртқы әліпбиі 0,1,2,3,4,5,6,7,8,9 он цифрдан және бос орын_ символынан тұру керек. Бұл цифрларды ұяшыққа бір бірден жазады (қатар, қалдырусыз). Машинаның q1 және q2екі ішкі қалып – күйі бар болса жеткілікті екен. Бастапқы мезетте бүркеншік санның цифрларының бірінің үстінде, ал машина q1 қалып-күйінде орналасқан деп болжайық. Онда есеп екі кезеңмен шығарлуы мүмкін: бүркеншіктін жылжуы санның бірлік цифрына (q1 ішкі қалып-күйінде) және осы цифрды үлкен бірлікке ауыстыру (1 келесі разрядқа көшіруді есепке ала отырып, егер 9 болса, q2 ішкі қалып-күйінде). ТМ сәйкес схемасы келесі түрде болады:
Қазіргі күнде дейін әртүрлі алгоритмдер ішкі және сыртқы әліпбимен, командалар жиынымен айрықшаланатын әртүрлі Тьюринг машиналарында жүзеге асырылады деп есептелген. Бірақта, кез келген Тьюринг машинасының кез келген алгоритмін орындай алатын әмбебап Тьюринг машинасын құруға болады. Бұл әмбебап машинаның сыртқы әліпбидің символы түрінде кез келген Тьюринг машинасының программасын және сырт пішінің кодтау жолымен іске асады. Кодтаудың өзі келесі түрмен орындалу керек: 1) әртүрлі символдар әртүрлі кодтық топтарымен ауыстырылуы керек, бірақ бірдей символ қай жерде кездессе де, сол кодтық топпен ауыстырылуы қажет; 2) кодтық жазулардың жолдары жеке кодтық топтарға бөлінуі керек; 3) Л, П, С командаларына сәйкес келетін кодтық топтарды тануға, сыртқы әліпбидің символдары мен ішкі қалып-күйлеріне сәйкес келетін кодтық топтарды айыра білуге мүмкіншілік болу керек. жүктеу/скачать 314.17 Kb. Достарыңызбен бөлісу:
| |||||||||||||||||||||||||||||||||||||||