ПӘнін оқыту-әдістемелік кешен


Тьюринг машинасының формальді емес анықтамасы



бет3/57
Дата23.08.2017
өлшемі7,64 Mb.
#25704
1   2   3   4   5   6   7   8   9   ...   57

Тьюринг машинасының формальді емес анықтамасы

Тьюринг машинасы автомат сияқты, екі жақты шексіз лентасы, басы (головкасы) және басқару құрылғысы бар. Басқару құрылғысы бір қалыпты болуы мүмкін, соңғы көпмүше жасайды Q = {q0, q1, ..., qn}. Көпмүше Q Тьюринг машинасының ішкі алфавиті деп аталады.

Тьюринг машинасының есептегіш машинадан принципті айырмашылығы мынада, оның еске сақтау құрылғысы шексіз лентадан тұрады, сондықтан ол шындыққа жанаспайтын қиялдағы машина болып қала береді. Лента ұяшықтарға бөлінген, әрқайсысына алфавиттің бір символы жазылған соңғы алфавит A={a0,a1,...,am}болады, ол Тьюринг машинасының енгізу алфавиті аталады. Тьюринг машинасы функциясын қолдану кезінде ұяшықтардың соңғы саны толтырылмаған болуы мүмкін. Есептегіш (считывающая) басы әр уақытта лентаның ұяшығына шолу, осы ұяшықтағы символға тәуелді және басқару құрылғысының қалпы ұяшыққа жаңа символ жазады немесе оны өзгертусіз қалдырады, ұяшық оңға немесе солға жылжиды немесе орнында қалады. Осыдан барып басқару құрылғысы жаңа күйге ауысады немесе бұрынғысында қалады. Бастапқы құрылғысының қалпы ортасында бастапқы қалып q0 және соңғы қалып qz болып бөлінеді.

Тьюринг машинасының бір тактісі бойынша символды санауға болады, оның орнына жаңасын жазып немесе оны өзгеріссіз қалдырамыз және басын бір ұяшық солға немесе оңға жылжытамыз немесе орнында қалдырамыз.



Тьюринг машинасының формальді анықтамасы

А алфавиті – кейбір соңғы көпмүше символдары.

Алфавит тізбегі деп осы алфавиттің символдарының тізбегін айтамыз. x тізбектің ұзындығы, ол сол тізбектегі символдар санын көрсетеді және | x | болып белгіленеді. Бос тізбек ұзындығы 0-ге тең.

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



Тьюринг машинасына 7 түр енеді:

мұндағы

соңғы жиынның қалпы, басқару құрылғысы бар;

енгізу алфавиті;


Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9   ...   57




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет