turing

[nitko]

Kada će se na vježbama raditi turingov stroj? Hvala!

[GauSs_]

14.10.

_________________
The purpose of life is to end


Prosle su godine kolokviji bili laksi, zar ne?

[Zvjezdica]

Da li mi netko može objasniti ovaj zadatak:
Binarni zapis na vrpci treba transformirati tako da ga pomnoži sa 4 (dekadskih). Početna konfiguracija q0 je na mjestu najmanje značajne znamenke.

Tablica izgleda ovako
.........q0...q1....q2
0...0Dq1
1...1Dq1
b...........0Dq2...0N!

Zašto su neka polja prazna i ako bi itko to mogao korak po korak raspisati bila bi neizmjerno zahvalna!

[Crazylamb1]

Broj je zapisan binarno. Pomnoziti ga sa 4 zapravo u binarnom smislu znaci pomnoziti ga sa 100, drugim rijecima samo treba na desnu stranu broja staviti jos dvije nule. Pocetna konfiguracija nam je savrseno namjestena (glava je na mjestu najmanje znacajne znamenke, iliti na skroz desnoj znamenci) - samo trebamo otici desno i ubaciti jednu nulu, pa otici desno i ubaciti jos jednu nulu i gotovo.

Zasto su neka polja prazna? Pa, npr. kako smo na pocetku na mjestu najmanje znacajne znamenke, to znaci da u pocetnom stanju q0 mozemo samo vidjeti 0 ili 1, nece sigurno biti b (prazno polje). I u tom pocetnom stanju, stroju kazemo da ostavi broj koji je nasao, ide desno i predje u stanje q1. Kako je ono bila zadnja znamenka, znaci kad se pomaknemo desno ne mozemo nista vidjeti osim praznog polja b. Zato su tu mjesta kod 0 i 1 prazni. I sad stavimo 0 na to prazno mjesto, idemo desno i prelazimo u stanje q2. Opet, mozemo samo vidjeti b, opet stavljamo 0, sad smo gotovi pa se ne micemo (to je N tu, ili S sa vjezbi), a ! oznacava konacno/finalno stanje - cesto oznacavano i sa qF.

Jasno?

[Zvjezdica]

Kristalno! Puuuuuuuno hvala!!!!!