Natural sonlami qo 'shish. Evklid algoritmı

7. 6. Tyuring mashinasında algoritmdı realizatsiya qılıw

A/goritm Realizatslya qılıw. 0 'nlik sistemada n den n + 1 ge 0 'tish. A/goritm.

Natural sonlami qo 'shish. Evklid algoritmı.

Ayırım ápiwayı arifmetik algoritmlami realizatslya etetuǵın (ámelge asıratuǵın ) Tyuring mashinasın soǵıwdı mısallarda úyrenemiz.

7. 6. 1. Tyuring mashinasında onlıq sistemada n den n + 1 ge ótiw algoritmın realizatsiya qılıw. Onlıq sanaq sistemasında n sannıń jazıwı berilgen bolsın hám 11 + 1 sannıń onlıq sisteması daǵı jazıwın kO'rsatish, yaǵnıy fen) = 11 + 1 funksiyanı esaplaw talap etilsin.

Ayqınki, mashinanıń sırtqı alfaviti 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 nomerlerden hám bos ketekshe Go den ibarat bolıwı kerek. Lentaga onlıq sistemada

sanın jazamız. Bul jerde qatarasiga bos jaysız hár bir ketekshege bir nomer jazıladı.

Qoyılǵan máseleni sheshiw ushın jumıstıń birinshi taktida mashina 11 sannıń aqırǵı nomerin óshirip, onı bir birlik úlken sanǵa almastırıp hám eger aqırǵı nomer 9 sanınan kishi bolsa, ol hold a toqtap qalıw jaǵdayına ótiwi kerek.

Eger 11 sannıń aqırǵı nomeri 9 bolsa, ol halda mashina 9 nomerdi óshirip, bos qalǵan ketekshege 0 nomerdi jazıp, sol jaǵdayda qalǵan halda shepke joqarılaw razryadlı qońsılassına jılısıwı kerek. Bul jerde

Jumıstıń ekinshi taktida mashina yuqonroq razryadlı nomerge I somm qosıwı kerek.

Tuwrısıda, shepke jılısıw waqtında joqarılaw razryadlı nomer bolmasa, ol halda mashinanıń basqarıwshı gellegi bos ketekshege shıǵıwı múmkin. Bul jaǵdayda bos ketekshege mashina I nomerin jazadı.

Aytılǵanlardan sol zat kelip shıǵadıki, fen) = n + 1 funksiyanı esaplaw algoritmın realizatsiya qılıw waqtında mashina bar yo'g'i eki q, hám qo jaǵdaylarda boladı.

Sonday etip, onlıq sistcmada n den n + 1 ge ótiw algoritmın realizatsiya etetuǵın Tyuring mashinası tómendegi kóriniste boladı :

ao

0

1

2

3

4

5

6

7

8

9

q,

IJqo

IJqu

2 Jqo

3 Jqo

4 Jqll

5 Jqo

6 Jqo

7 Jqo

8 Jqll

9 JqIJ

OChq,

Tómende

n = 183 hám

n = 399

sanlar

ushın

uyqas

túrde

olardıń

konfiguratsiyalari keltirilgen:

ao 183 aD

ao 399 ao

'I,

'I,

ao 184 aD

aD 390 ao

'III

q,

7. 6. 2. Natural sanlardı qosıw algoritmı. Mashina lentasiga tayaq -shalar kompleksi formasında eki san berilgen bolsın. Mısalı, 2 hám 3 san-lari. Bul sanlardı qO'shish talap etilsin. QO'shish simvolini (belgisin ) yul-duzcha menen belgileymiz. Sonday etip, mashina lentasiga tómendegi sóz jazıladı.

(1) (I) so 'zga qollanıw qılıw nátiyjesinde 2 hám 3 sanlarınıń yig' indisini, ya 'ni

aol I I I I

ao

(2)

sózdi beretuǵın funksional sxemanı tabıw talap etiledi.

Qo 'yilgan máseleni sheshiw procesin anıqlama berb beraylik. Dáslepki

momentte mashinanıń gellegi eń chapdagi tayaqshanı kórip tursın. Onı tap birinshi bos ketekshege eriwgenge shekem hámme tayaqsha hám yul-

Duzchalami sheklep 0 'ngga jıljıtıw kerek. Bul bos ketekshege birinshi tayaqsha jazıladı. Odan keyin ekinshi tayaqchaga qaytıp keliw kerek jáne onı óshirip toqtap qalıw kerek. Mashina jumısınıń hámme taktini tómendegi uyqas konfiguratsiyalarda ańlatpalap beremiz:

a o II * III a o

q]

a o I * I II a o

q2

a o I * III a o

q2

ao1* 1111 ao

q3

ao! *I i Ilao

q3

aoao*lllloo

q2

a o* 1111 a o

q,

a o* 111 I1 a o

q3

ao* 1 I111 Go

q3

ao* 11111 ao

q,

2)

a o I * III a o

3)

aoi * III a o

q2

q2

5)

ao! * III ao

6 )

a o I * III a o

q,

q2

8)

aoI * 1111 ao

9 )

a o 1* 1111 ao

q}

q3

11) a o! * III! 00

12) aol*llllao

q3

q3

14)

a o! *! 11100

15) aoI * 1111 ao

q3

ql

17)

ao* 1111 a o

18) ao* 1111 ao

q2

q2

20 )

a o* iii II ao

21)

ao* 1111 ao

q2

q2

23) ao* 111 I1 ap

24) ao*! 1111 ao

q1

q3

26 )

ao* 11111 ao

27) Go * II i II ao

q,

q3

ao* 1111 I Go30 ) aoao* 11111 ao

(h qo

Bul process máseleniń sheshiw algoritmın eki ólshewli 1- keste

Formasında jazıwǵa múmkinshilik jaratadı.

Sonday etip, bul jerde < ao' *, I >-sırtqı alfavit hám qo' ql' q2' q3 - mashina jaǵdaylarınan paydalanildi.

Evklid algoritmı. Evklid

algoritmı berilgen eki natural san ushın olardıń eń úlken ulıwma bóliwshisin tabıw sıyaqlı máselelerdi sheshiwde qollanıladı. Ekenin aytıw kerek, Evklid algoritmı qu-yidagi kamayuvchi sanlar ketma-

ketligini dúziwge keltiriledi:

1- keste

ao

*

I

q)

aoJ qo

aoO'q2

q2

I J q3

*O'q2

IO'q2

q3

aoO'ql

*Ghq3

I Chql

birinshisi berilgen eki sannıń eń úlkeni boladı, ekinshisi - kichigi, úshinshisi - birinshi sannı ikinchisiga bolıwdan payda bolǵan qaldıq, tórtinshisi - ekinshi sannı úshinshisine bolıwdan payda bolǵan qaldıq hám taǵı basqa, bul process qaldıqsız bolıńuncha dawam ettiriledi. Aqırǵı bolıw daǵı bóliwshi másele sheshiminiń nátiyjesi boladı.

Evklid algoritmın Tyuring mashinasınıń programması retinde ańlatıw talap etilgen bolsın. Bul programma sanlardı salıstırıwlaw hám ayırıw sikIlarining gezekpe-gezek (gezeklesip) keliwin támiyinlewi kerek.

Tórtew háripten ibarat < ao' I, a, f3 > sırtqı alfavitten paydalanamız. Bul jerde a o - bos ketekshe simvoli, I - tayaqsha, a hám f3 - tayaqsha rolin waqtınshalıq atqaratuǵın háripler.

Máseleniń yechilishini baslanǵısh konfiguratsiyasi

o 11 I1 II1111 ao

ql

bolǵan hoI ushın 4 hám 6 sanlardıń eń úlken ulıwma bóliwshisin tabıw mısalında kórip óteylik.

Birinshi náwbette mash ina lentada jazılǵan sanlardı salıstırıwlashi kerek. Sol maqsetke erisiw ushın mashina birinshi sannı ańlatiwshı tayaqchalarni a hárıbi menen hám ekinshi sannı ańlatiwshı sanlardı f3 hárıbi

menen almastırıwı kerek. Mashina jumısınıń birinshi tórt taktiga uyqas keliwshi onıń konfiguratsiyasi tómendegishe boladı :

o o

1) a " " " " " a

q)

2)

ao Ilia 1 III11 ao

q,

a o II lall II II a o

q1

4)

ao Illaf311111 ao

ql

94

Usınıń menen dáslepki sanlardı salıstırıwlaw sikli tamam bolıp, ayırıw sikli baslanadı. Bul cikl dawamında kishi san lentadan pútkilleyine óshiriledi, f3 hárıbi menen belgilengen ekinshi san tayaqshalar menen almasinadi hám, sonday eken, úlken 6 sanı eki 4 hám 2 sanlarına bólinedi.

Bul operatsiyalarǵa bir qatar konfiguratsiyalar tuwrı keledi. Usılardan ayırımların jazamız :

oaaaaf3 f3 f3 f3 II an

q,

aoaaaaf3 f3 f3 f3 II a o

q3

oooaaaf3 f3 f3 f3 II 0 0

q3

ooooooaooof3 f3 f3 f3 II ao

q3

aoooooaooo I f3 f3 f3! 100

q1

0 oooooooao 1111 i! 00

q,

ooooooooaol I I I I 100

q,

Usınıń menen birinshi ayırıw sikli tamam boladı.

Endi mashina 4 hám 2 sanların salıstırıwlashi kerek. Bul sanlardı salıstırıwlaw sikli tómendegi

konfiguratsiyaga hám ayırıw sikli

konfiguratsiyaga alıp keledi.

95

Úshinshi salıstırıwlaw sikli 2 hám 2 sanlarım

aoaa{3{3 ao

q3

konfiguratsiyaga hám ayırıw sikli

aqırǵı konfiguratsiyaga alıp keledi.

Sonday etip, Tyuring funksional sxeması 2- keste kOrınishida boladı.

2- ladval

ao

I

a

{3

q,

auO'q3

aJ q2

aChq,

{3 Chq,

q2

aoChq4

{3 J q,

aO'q2

O'Q2

q3

aoJ qo

I J q2

aoO'Q3

IO'Q3

q4

aoJ Qo

I Jq,

IGhQ4

aoCh q4

7. 7. Algoritmlar teoriyasınıń tiykarǵı gipotezasi

Universalusul. TYlIring tezisi Tyuring. Chyorch. Gyodel, Klini hám Markov

o/gan nátiyje/arning ekviva/entligi

7. 7. 1. Tynring tezisi. Tyuring mashinası algoritm túsinigin anıqlawdıń bir jolin kórsetedi. Sol sebepli bir neshe sorawlar payda boladı :

Tyuring mashinası túsinigi qansha ulıwmalıq ózgeshelikine iye?

algoritmlami Tyuring mashinası quralı menen beriw usılın universal usıl dep bola ma?

hámme algoritmlami sol usıl menen beriw múmkinbe?

Bul sorawlarǵa házirgi waqıtta ámeldegi bolǵan algoritmlar teoriyası tómendegi gipoteza menen juwap beredi: hár qanday afgoritmni Tyuring

funksional sxeması arqalı beriw hám mas Tyuring mashinasında realizatsiya etiw (ámelge asırıw ) múmkin.

96

Bul gipoteza Tyuring tezisi dep ataladı. Onı tastıyıqlaw múmkin em as, sebebi bul tezis qatań ta'ritlanmagan algoritm túsinigin qatań anıqlanǵan Tyuring mashinası túsinigi menen baylanıstıradı.

Bu tezisni rad etish uchun Tyuring mashinasida realizatsiyalan-maydigan (amalga oshirilmaydigan) algoritm mavjudligini ko'rsatish kerak. Ammo hozirgacha aniqlangan hamma algoritmlarni Tyuring funksional sxemasi orqali realizatsiya etish mumkin.

7.7.2. Ekvivalent tushunchalar. Shuni ham ta'kidlab o'tamizh Markovning normal algoritm tushunchasi hamda Chyorch, Gyodel va Klini tomonidan kiritilgan rekursi" algoritm va rekursiv funksiya tushunchalari, mos ravishda, Tyuring tomonidan kiritilgan algoritm tushunchasi va Tyuring funksional sxemasi bilan ekvivalentligi is-botlangan.

Bu dalil o'z navbatida Tyuring gipotezasming to'g'riligini yana blr marta tasdiqlaydi.

Muammoli masala va topshiriqlar

Quyidagi funksiyalarni hisoblo\'chi algoritmlarni Tyuring mashi-nasining dasturlari sifatida ifodalang:

a) cp(n)=n+2; b) cp(n)=n+4; d) cp(n)=O.

Quyidagi funksiyalami funksiyani hisoblovchi Tyuring mashi-nasmi tuzing:

O, agar x = 0 bo'lsa,

sgnx ={ 1, agar x :f. 0 bo'lsa, -- {I, agar x = 0bo'lsa,

sgnx =

0, agar x :f. 0 bo'lsa,

3. Ushbu cp(n) = 211 funksiyani hisoblovchi Tyuring mashinasini

tuzing.

Ushbu

f,(n) = I, agar n son p songa qoldiqsiz bo'linsa, funksiyani

{ 0, aks holda,

hisoblovchi Tyuring mashinasining dasturlarini {ao,l} alfavitda Y07ing.

97

Funksional sxemalari 1- va 2-jadvallarda berilgan Tyuring mashinasi qanday funksiyalami hisoblashi mumkinligini aniqlang

1- iadval

ao

I

ql

a oO'ql'+l

IChq2

q2

aoO' ql'+3

IChq3

...

...

...

qp-l

aoO'qp+3

I Chqp

qp

aoO'ql'+l

IChql

qp+l

I J qo

aoJ qp+2

ql'+2

aoO'Ql'+l

ql'+3

aoJ qo

aoJ q 1'+4

qp+4

aoO'Qp+3

2- iadval

ao

I

ql

IO'q4

IChq2

q2

aoO'q6

IChq3

Q3

aoO'q6

IChql

q4

I J qo

aoJ Q5

qs

aoO'q4

q6

aoJ qo

I J q7

q7

aoO'q6

aoO'q6

Dasturi 3- jadvaldagi funksional sxema orqali berilgan Tyuring mashinasi qanday ko'rinishdagi funksiyani hisoblashi mumkinligini aniqlang.

3- jam'al

ao

I

a

/3

ql

ao Ch q2

IO'ql

aO'ql

/30'ql

q2

f3 Chq3

aChq2

f3 Chq2

q3

aoO'q4

I J ql

q4

ao J qo

IO'q4

IO'q4

Ko'rsatma. Misollami yechishda L.M.Lixtamikov va T.G.Suka-chevaning (JIMxTapHliKOB JI.M., CYKaqeBa T.r. MaTeMamqeCKajf JlOrHKa. Kypc JleKUHH. 3a,ll,a4HliK-npaKTHKYM Ii perneHHH. CaHKT-neTep6ypr. JIaHb. 1999.) kitobidan foydalanishni tavsiya etamiz, 248-250- va 275-281- sahifalar.

98