border=0

Foarbyld 7.9

Der is in meardere integer n yn desimaal nûmersystem; bouwe in Turing-masine dy't de berekkening fan de wearde fan n + 1 leart.

Wy brûke it eksterne alfabet A = {0,1, ..., 9, Δ}, wêrby it symboal Δ in lege teken is. It ynterne alfabet, lykas yn it foarige probleem, wurdt foarme troch twa steaten - wurkje (q) en stopjen ( z ) ( Q = { q, z }) . Ynitial nûmer n, en It resultaat n + 1 wurdt ek yn it desimale systeem opnommen, en de nûmers wurde ien nei ien yn 'e buorren fan sellen sûnder spaasjes pleatst. It funksjoneel diagram wurdt fertsjintwurdige troch in tabel (foar komfortens, de snaar sil oerienkomme mei de steat q, en kolommen - tekens fan it eksterne alfabet):

Lit de earste konfiguraasje wurde 21 q 9 .

De slach 1 q 9 → q 0 L, d. 9 sil ferfongen wurde mei 0 en de kop sil nei de tsien sifers ferpleatse - intermediate konfiguraasje 2 q 10.

Beat 2 q 1 → z 2 S , d. 1 sil ferfongen wurde troch 2 en sil stoppe wurde mei de definitive opset 2 z 20, d. It resultaat fan tafoeging is 219 + 1.

Lit de earste konfiguraasje wurde 99 q 9.

De slach 1 q 9 → q 0 L, d. Yntermediate konfiguraasje 9 q 90 sil foarme wurde.

Beat 2 q 9 → q 0 L - de q 900-konfiguraasje sil foarkomme.

De beat 3 q 9 → q 0 L - q Δ000 ferskynt.

De klok 4 q Δ → z 1 S - der sil dan 1000 wêze en it wurk stoppt.

Sa beklammet it beskreaune algoritme de summaat fan ien inkele desimaal nûmer en ien. It is ek dúdlik dat as it nedich is om advertearring net mei in ienheid te meitsjen, mar mei in tal ynteger m, dan moat dizze algoritme m kear werhelle wurde. Multyklingende intekeningen kinne ek reduearre wurde om in nûmer te meitsjen mei himsels. Dêrtroch hawwe Turing-masines in wichtich eigendom - de mooglikheid om in nije masine te bouwen troch besteande op te kombinearjen - sa'n operaasje wurdt komposysje neamd .

Neffens syn ûntwerp is de Turing-masine tige primitive. It is folle ienfâldiger as de earste earste kompjûters. Primitivisme is dat it in tige ienfâldige opset fan elemintêre operaasjes hat troch it haad - lêzen en skriuwen útfierd, en ek dat tagong ta spesjale sellen (tapeabers) dêrtroch net troch adres, lykas yn kompjûters, mar troch opfolgjende beweging lâns de tape. Om dy reden binne sels sokke ienfâldige aksjes as oanfolling of fergeliking fan twa tekeningen Turing masine yn ferskate stappen útfierd, en de gewoane operaasjes fan oanfolling en multiplikaasje freegje in hiel grut tal primêre aksjes. De Turing-masine waard lykwols net útfûn as model (prototype) fan echte kompjûters, mar om de haad (teoretyske) mooglikheid fan it konstruearjen fan in willekeurige kompleet algoritme út tige ienfâldige operaasjes te sjen, makket de masine automatysk de oergong fan ien nei de folgjende út.

De Turing-masine jout ien fan 'e wizen om it begryp fan in algoritme te klarjen. Yn dizze relaasje ûntsteane fragen:

· Hoe algemien is it begryp fan in turing machine?

Is it mooglik om te fytsjen dat de metoade foar it definiearjen fan algoritmen mei de Turing-masine universele is?

· Kin elke algoritme op dizze manier definieare?

De moderne teory fan algoritme biedt in antwurd op dizze fragen yn 'e foarm fan de folgjende hypoteze:





Sjoch ek:

Computer kodearring en ferwurking fan echte nûmers

It algemiene skema fan ynformaasjeferkear yn 'e kommunikaasjegroep

Besykje fragen en taken

Soft-definition algoritme

Probleemintwurding

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ edudocs.fun