border=0

Foarbyld 7.8

Besykje de oplossing fan it probleem oan tafoeging 1 oant in unaryn nûmer, besprutsen yn 'e foarige paragraaf, troch in Turing-masine. It eksterne alfabet kin bepaald wurde troch de set A = {Δ, 1}, wêrby't 1 de folsleine paragraaf entspricht en Δ nei it lege karakter, en de folken folje inoar yn rige. It ynterne alfabet is jûn troch de set Q = { q, z }, dêr't q oerienkomt mei de operaasjestân fan de Linac , en z is in set. In set fan alle transformaasje regels (in logyske funksje) kin fertsjintwurdige wurde troch in funksjoneel diagram:

In funksjoneel diagram wurdt opset yn 'e foarm fan in tabel op sa'n manier wêrop de tekens oanjûn fan kolommen en rigels de ynputparameters fan' e linaas, en yn 'e tabellen foar it útfierkommando is by har krúspunt. Benammen as de masjinekop in sekte fan tape befettet mei it teken 1 en de masine is yn wurksitewaasje (q), dan moat it resultaat fan syn wurk oer dizze kloksyklus in werhelling fan 1 wurde yn dit paragraaf en in ien ûnderdiel rjochtsôf rjochts R (wylst sa as oanjûn is de tape wurdt nei 't ferpleatst) - dit kommando wurdt skreaun as q 1 R. As yn 'e ûndersochte paragraaf Δ, en de steat fan' e linac q , dan sil Δ wurdt ferfongen troch 1, sil der gjin bandwizer wêze en de masine stopet - z 1 S. Mei de kombinaasje yn 'e ynfier Δz , lykas 1 z , is de masine yn in net-wurksitewaasje - gjin konfiguraasjewiziging is noch in beweging - dêrom wurde sokke kombinaasjes net werjûn yn' e funksjonele diagrams yn 'e takomst.

Lit de earste konfiguraasje is 1 q 1111 *. Dan sil it wurk fan 'e masine neffens de beskreaune logyske funksje folgje:

* As hjirboppe neamd is, lytse lege ôfdielingen op 'e linker en rjochter fan' e konfiguraasje binne net opnommen; sûnt op dizze taak ferskillende ôfdielingen sille folge yn suksesje, allinich wurde se oanjûn yn 'e konfiguraasje.

Tact 1 beoardield 1, yn 'e LU-bestân q. It útfierkommando q 1 R , wat lykweardich is om de kop te ferpleatsen relatyf oan it lint troch 1 stap nei rjochts. Dêrtroch wurdt in tuskenynkonfiguraasje 11 q 111 foarme.

Beat 2 - de oergong nei de 111 q 11-konfiguraasje wurdt op deselde wize dien.

Tact 3 - gean nei konfiguraasje 1111 q 1.

Tact 4 is in oergong nei de 11111-konfiguraasje q Δ (hjir, foar in better begryp, de rjochter Δ wurdt eksplisyt oanjûn).

Tact 5 bewarre Δ, yn 'e LU-staat q. Utfierkommando z 1 S - ynstee fan Δ, 1 is skreaun yn 'e sel, der is gjin skeakel, it wurk wurdt stoppe. De definitive opset is 111111z .

Problem is besluten.

Sjoch ek:

Foarbyld 9.5

Formale grammatika

Foarbyld 4.8

Foarbyld 7.11

Seksje 2. ALGORITHMS. MODELS. SYSTEMS

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

2019 @ edudocs.fun