Теория автоматов. Лупал А.М. - 22 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

22
q
2
α → q
2
α R (2) q
1
α → q
4
α L (5) q
5
α → q
5
α E (7)
q
2
1 → q
1
β E (3)
Ïðè çàäàííîé âõîäíîé èíôîðìàöèè (11111) è íà÷àëüíîé ÿ÷åéêå (4-é)
ïîëó÷èì ñëåäóþùóþ ïîñëåäîâàòåëüíîñòü êîíôèãóðàöèé ìàøèíû Òüþ-
ðèíãà:
1q
1
1111 → 1q
2
α111→ 1α
q
2
111→ 1αq
1
β11→
Ê1Ê2Ê3Ê4-
→ 1q
1
αβ11→ q
4
1αβ11→ λq
5
αβ11→λq
5
αβ11
Ê5Ê6Ê7 !
ñòîï-ñîñòîÿíèå
Ñëåäîâàòåëüíî, 1q
1
1111
T
⇒
λq
5
αβ11 .
3.5. Òüþðèíãîâî âû÷èñëåíèå
Ðàññìîòðèì, êàê ñòðîèòñÿ ìàøèíà Òüþðèíãà, ðåàëèçóþùàÿ íåêîòî-
ðûå ïðîñòûå àëãîðèòìû.
Àëãîðèòì îïåðàöèè Ñëîæåíèå.
Èñõîäíûå äàííûå è ðåçóëüòàòû îïåðàöèè ñëîæåíèÿ ÿâëÿþòñÿ íàòó-
ðàëüíûìè ÷èñëàìè.
Ñ÷èòàåì, ÷òî â ìàøèíå Òüþðèíãà êàæäîå íàòóðàëüíîå ÷èñëî çàäàíî
â âèäå íàáîðà 1 è îòäåëÿåòñÿ îò äðóãîãî ÷èñëà ñèìâîëîì *. Òàêèì
îáðàçîì, àëôàâèò ìàøèíû Òüþðèíãà áóäåò S = {1,*,λ}. Ñîñòîÿíèÿ çàäà-
íû ìíîæåñòâîì Q = {q
0
, q
1
, q
2
, q
3
, q
4
, q
5
}.
Ðàññìîòðèì ïðèìåð.
Íà÷àëüíûå óñëîâèÿ: â íà÷àëüíîì ñîñòîÿíèè q
0
íà ëåíòó ìàøèíû Òüþ-
ðèíãà ïîäàåòñÿ ïàðà ÷èñåë 6 è 4 è â ïîëå çðåíèÿ ìàøèíû íàõîäèòñÿ
ëåâàÿ åäèíèöà.
G
0
: 111111* 1111
↑
Íåîáõîäèìî íàéòè èõ ñóììó, ò. å. çàïèñàòü ïîäðÿä 10 åäèíèö, ïîëó-
÷èâ

Ïðîñòî óáðàòü * íåëüçÿ, òàê êàê íà åå ìåñòå áóäåò ïóñòàÿ ÿ÷åéêà, à
ñîâîêóïíîñòü åäèíèö ñ ïðîáåëîì íå ÿâëÿåòñÿ çàäàíèåì ÷èñëà íàòóðàëü-

Страницы