Э. А. Абдыкеримова

 
35 
Тьюринг машинасының жҧмыс істеу принципі, сипаттамасы 
Бір  ленталы  Тьюринг  машинасын  кибернетикалық  қҧрылғы  ретінде 
қарастырады және ол келесі элементтерден тҧрады: 
- ҧяшықтарға бӛлінген шексіз лента;  
-  лента  ҧяшықтарында  болатын  символдарды  оқи  алатын  басқарушы 
головка; 
-  Тьюринг  машинасының  жағдайын  кӛрсететін  ішкі  алфавит  символы  бар 
жадының ҧяшығы.  
-  лента  бойымен  головканың  қозғалысын  қамтамасыз  ететін  басқарудың 
механикалық қҧрылғысы 
-  тек  оқуға  болатын  Тьюринг  машинасының  бҧйрықтарынан  тҧратын 
функционалды схема - жады аймағы.  
Әдетте, Тьюринг машинасы схемалық тҥрде мынадай тҥрде кӛрсетіледі:  
 
 
 
1
i
a
 
2
i
a
 
 
ik
a
 
 
ir
a
 
 
Лентаны магниттік жол немесе баспаның қағаз лентасы деп қарастырайық, 
ол  бірнеше  ҧяшыққа  бӛлінген.  Жҧмыс  барысында  машина  бар  ҧяшықтарға 
жаңа  ҧяшықтарды  қоса  алады,  сондықтан  лента  екі  жағынан  да  шексіз  деп 
айтуға болады. Лентаның әрбір ҧяшығы кӛп жағдайдың бірінде болуы мҥмкін. 
Бҧл  жағдайларды  біз  а
0
,  а
1
,...,а
m 
символдарымен  немесе  басқа  символдармен 
белгілейміз.  Осы  символдар  лента  ҧяшықтарында  жазылған.  Мҧндай 
символдардың  жиынтығы  машинаның  сыртқы  алфавиті  деп,  ал  лентаның  ӛзі 
машинаның  сыртқы  жадысы  деп    аталады.  Егер  ҧяшық  бос  болса,  ол  жерде 

шарты  символы  орналасқан  деп  есептейміз.  Машинаның  жҧмысы  кезінде 
лентаның  ҧяшықтары  ӛздерінің  жағдайын  ӛзгертуі  де,  ӛзгертпеуі  де  мҥмкін. 
Жаңа  қосылатын  барлық  ҧяшықтар  бос  болады.  Сонымен,  егер  қандай  да  бір 
уақытта лентаның r ҧяшығы болса және машинаның сыртқы алфавиті мынадай 
символдардан  тҧрса  а
0
, а
1
, ...,а
m
,  онда лентаның жағдайы былай жазылады: 
 a
і0
, а
і1
, ...,а
іm
. а
і1
-солдан бастап орналасқан бірінші ҧяшықтың жағдайы, а
і2
-
екіншісінің жағдайы, т.с.с. 
Басқару  головкасы.
  Бҧл  лентаның  бетімен  қозғалатын  және  белгілі  бір 
уақытта  лентаның  белгілі  бір  ҧяшығында  тҧрады.  Кейде  керісінше  басқару 
головкасы  қозғалмайды,  оған  сәйкес  лента  қозғалады  деп  есептеледі.  Ондай 
кезде  головкаға  лентаның  ҧяшығының  біреуі  әлде  келесісі  кіреді  деп 
есептеледі.  Егер  лентаның  ҧяшығы  головкада  болса,  машина  бҧл  ҧяшықты 
оқып немесе қабылдап жатыр деп есептеледі. 
Машинаның  ішкі  жадысы  -  әрбір  қараған  уақытта  белгілі  бір  жағдайда 
болатын  қҧрылғы.  Ішкі  жадының  жағдайының  саны  машинамен  есептеліп 
отырады. Ішкі жадының жағдайын мынадай символдармен кӛрсетеміз S
0
, S
1
,…, 
S
n
  ,  олар  машинаның  сыртқы  алфавитіне  кірмейді.  Ішкі  жадының  жағдайының 
символдарының жиынтығы машинаның ішкі алфавиті деп аталады. 
Si 

 
36 
Ішкі  жадының  жағдайын  кӛбінесе  машинаның  ішкі  жағдайлары  деп 
атайды. Бҧл жағдайлардың біреуі бастапқы деп аталады, бҧл жағдайдан машина 
ӛз  жҧмысын  бастайды,  ол  S
0 
жағдайы  болсын.  Тағы  да  бір  арнайы  жағдай  - 
аяқтаушы  соңғы  жағдай.  Соңғы  жағдайды  кӛрсететін  символ  стоп-символ  деп 
аталады.  Стоп-символ 

  ӛрнектеледі.  Егер  қандай  да  бір  уақытта  машинаның 
ішкі жадысы 

 келсе, ол жҧмысын тоқтатқан болып есептеледі. Машинаның S
і 
қандай да бір ішкі жағдайында ешқандай ӛзгеріс болмауы мҥмкін, олай болса, 
машина шексіз жасайды деп есептеледі. 
Машина  ерекше  механизммен  жабдықталған  деп  есептеледі.  Ол 
қабылданатын  ҧяшық  пен  ішкі  жады  жағдайына  қарай  ішкі  жады  жағдайын, 
ҧяшық орнын ӛзгерте алады деп есептеледі. 
Машинаның  (Тьюринг)  ағымдағы  жағдайы  немесе  оның  конфигурациясы 
деп  ағымдағы  ҧяшық  а
j
  және  ішкі  жады  S
1
  жағдайларының  жиынтығын 
айтамыз. 
Тьюринг  машинасының  командасы,  яғни  машина  жҧмысы  бір  жағдайдан 
белгілі  бір  уақытта  механикалық  қҧрылғының  бір  такті  жҧмысынан  соң  жаңа 
бір жағдайға ӛтуіне негізделген, содан соң тағы бір такті жҧмысынан жаңа бір 
жағдайға  ӛтуі  т.с.с.  Егер  машина    S
і
  ішкі  жағдайында  а
і
  символды  лентаның 
ҧяшығын  қабылдап,  ішкі  жады  жағдайын  келесіге  S
b
  аударып  сонымен  бірге 
қабылданған ҧяшықтың мазмҧнын а
r
 символына аударып, ал басқару головкасы 
(H) орнында тҧрып, бір ҧяшыққа оңға қарай (R), солға қарай (L) қозғалса, онда 
машина мынадай команда орындап жатыр деп айтады: 
S
і
 а
і               
а
s
 S
b
 H 
S
і
 а
і               
а
s
 S
b
 R 
S
і
 а
і               
а
s
 S
b
 L 
Машина  орындай  алатын  барлық  командалардың  жиынтығы  бағдарлама 
деп аталады. Машина жҧмысы шарт бойынша толықтай оның ішкі жадысының 
S  және  қабылданатын  ҧяшықтың  a
j
  жағдайымен  анықталатын  болғандықтан, 
барлық S
і
 a
j
 (і=1, …, n; j=0, 1, …, m) ҥшін машина бағдарламасы тек қана бір a
і
a
j
 
сӛзінен  басталатын  командадан  тҧруы  қажет.  Сонымен  {a
0
,

жүктеу/скачать 1,31 Mb.

Достарыңызбен бөлісу: