zadaci iz turingovog stroja

[GauSs_]

stavljeni su na sluzbenu stranicu

_________________
The purpose of life is to end


Prosle su godine kolokviji bili laksi, zar ne?

[Gost]

@ Turingov stroj:
po mom misljenju dosta slabo smo prosli te zadatk(e), "e" je u zagradi jer smo prosli samo jedan?!
Ne znam zasto su fizicari iz prvih redova rekli da ne treba vise, ali to nije bilo u redu prema ostalima koji to nikad nisu radili.

hvala fizicarima

[Milojko]

@Gost:
otiđi danas (ak već nisi, a nadam se da jesi) kod kolege Banellija na demonstrature, traju od tri do sedam sati. siguran sam da će bit spreman riješiti i pokojeg turinga. a uostalom, daj zadatak ovamo kad budeš rješavo i imao problema, ispetljat ćemo ga mi koji smo radili turinga pa da radi kak spada

_________________
Sedam je prost broj

Bolonja je smeće i to pod hitno treba mijenjat

[GauSs_]

[Gost]

ono u prvom redu nisu bili fizičari.
ekipa koja je izlazila na ploču, a kasnije i rekla da se može dalje stvarno jest iz prvog reda, ali to denfinitivno nisu bili fizičari.

dakle, ispravak netočnog navoda:
hvala matematičarima

čini se da ćemo svi zajedno morat koristiti "snađi se druže" metodu (izuzev ekipe iz prvog reda). prema tome, bilo bi uputno da ne pljujemo jedni po drugima.

[GauSs_]

ok. od sada pa nadalje ako netko spomene fizicari/matematicari u negativnom kontekstu biti ce izbacen s foruma na neko vrijeme, a gostima ce se zatvoriti pristup !!!

a sto se tice TSa, imate rijesene primjere i zadatke za vjezbu na sluzbenoj stranici. Zadatak u kolokviju nece biti nista tezi od tih zadataka, a mozda bude i jedan od njih.

_________________
The purpose of life is to end


Prosle su godine kolokviji bili laksi, zar ne?

[Gino]

[Milojko]

@gost:
jesi otišo jučer na one demonstrature što su se održavale?

_________________
Sedam je prost broj

Bolonja je smeće i to pod hitno treba mijenjat

[mona]

Jel bi netko riješio 11. zadatak iz Turingovog stroja sa vježbi? Kak se to točno "pomoću stanja pamti 1 dalje/0 dalje"?

Hvala

[Crazylamb1]

Ne znam je li to to sa pamcenjem 1/0, ali evo objasnjenja mog rjesenja:

Zadnjoj znamenci dodamo 2 ako je ta znamenka 0, 1 ili 2, i onda idemo lijevo u stanje q2, koje dodaje 2 trenutnoj znamenci (ukoliko je ta trenutna znamenka 0, 1 ili 2) i stajemo, a ukoliko je prazno polje, stavlja 2 i staje, a ukoliko je ta trenutna znamenka 3 ili 4 onda stavljamo 0 ili 1 (jer je 3+2=10, a 4+2=11), i idemo lijevo u stanje q1, koje ce trenutnoj znamenci dodati 1 (opet, za prazno polje, stavi 1 i staje, za 0, 1, 2, 3 doda 1 i staje, a za 4 stavlja 0, ide lijevo i ostaje u stanju q1, jer treba prenijeti onu jedinicu).
E sad, ako je u pocetnom stanju q0 bilo 3 ili 4, dodavajuci 2 pojavit ce se tu 0 ili 1, a moramo pamtiti dodatnih 1 (3+2=10, 4+1=11), pa necemo otici u q2 (stanje koje dodaje 2 trenutnoj znamenci) kao u prvom slucaju, vec u novo stanje q3, koje ce dodati 3 trenutnoj znamenci (onih 2 sto treba, plus ovih 1 sto smo upamtili), i tu naravno, ako je prazno polje, stavimo 3 i stanemo, ako je 0 ili 1, dodamo 3 i stajemo, a ako je 2, 3 ili 4, dodajemo 3, ali cemo morati "pamtiti 1", iliti otici lijevo u stanje q1 (koje ce znamenci dodati 1 kojeg smo "upamtili").

I to je ukratko (?) to.

[ante c]

prvo se pozicioniraš na krajnju desnu znamenku i kao da zbrajaš dva broja u bazi 10 potpisivanjem uzmeš 2 i zbrojiš zadnjoj znamenci ako je zbroj jednak 0,1,2,3,4 zapišeš ga a ako je 5 to je kao da u bazi 10 imaš 10 pa pišeš 0 a 1 prenosiš dalje tj ako je 6 to ti je kao da u bazi 10 imaš 11 tj 1 pišeš 1 dalje i tako za svaki sljedeći broj do prve praznine tj na tu prvu će trebati upisati ako smo u zadnjem zbrajanju prenjeli nešto

[ivicasb]

evo ako netko ima voljan /zna rijesiti ovaj zadatak sa turingom
Napisite prog.za Turingov stroj koji broj predocen u pozicijskom brojevnom sustavu s bazom 6 inkrementira za 30(baza 5).
U pocetnoj konfiguraciji stroj je u stanju q0 i glava je na najmanje znacajnoj znamenci.
Odredite 3.konfiguraciju za 345.
hvala unaprijed!

[fejky]

Prvo: .

Kako je TS u na najmanje znacajnoj znamenci, mozemo odmah poceti sa inkrementiranjem:

razlikujemo dva slucaja:
1) zadnja znamenka je 0, 1, 2.
2) zadnja znamenka je 3, 4, 5.

1) povecaj broj za 3, pomakni glavu lijevo. Sada opet imamo dva slucaja
1.1) znamenka je 0,1,2,3.
1.2) znamenka je 4,5.

1.1) povecaj broj za 2 i zavrsi
1.2) umjesto 4 upisi 0, umjesto 5 upisi jedan, predji u novo stanje . Ako je zadnja znamenka 5, upisi nulu, pomakni glavu u lijevo i predji u , ako je zadnja znamenka b,1,2,3,4, upisi 1,2,3,4,5 i zavrsi:

2) analogno kao gore.

[simon11]

Jel moze netko dati samo hint za 10.zad ?

http://brale.math.hr/nastava/gr/materijali/v06/turingov_stroj-vjezbe.pdf

Prvo algoritmom za trazenje znakova nadjem x,ali je problem kada dodjem do znaka x ne znam je li on lijevi ili desni i jos me muci situacija kada je glava bila izmedju znakova.

_________________

getting recognized

[Gino]

-nalazis se negdje, ako je to mjesto prazno, oznacis ga s y i ides lijevo
-dodes tamo, ako je i tamo prazno, stavis y i ides desno sve dok ne dodes do praznine ili x-a
-kad dodes do praznine ili x; ako je to praznina, oznacis s y i krenes desno sve dok ne dodes do praznine ili x
-sad ces od tamo ic nazad...

dakle seces se ljevo-desno

kad nades prvi x, predes u nova stanja, koja rade isti posao, ali preskacu taj x-ako te taj konkretno muci, oznaci ga s a kad ga nades i preskaci a i y dok ne nades drugi x

kad si nasao drugi x predes u zavrsnu fazu, ako si taj x nasao tako da si se pomaknuo u desno, onda kreni lijevo, sve dok ne dodes do a, kad dodes do a, promijeni ga u x i nastavi lijevo mijenjati sve y u praznine dok ne dodes do prve praznine

analogno ako si taj x nasao pomaknuvsi se u lijevo

mislim da bi to trebalo radit, ako nije potpuno jasno mogu sastavit tablicu pa ce bit jasnije...

_________________
Mario Berljafa

[simon11]

ah necu si nikad razviti nacin razmisljanja ako budem dobivao konacna rjesenja hvala puno,ispricavam se na malo zakasnjelom odg.

_________________

getting recognized

[pravipurger]

"Početni položaj glave može biti bilo gdje na traci." u zadatku iz prošlogodišnjeg kolokvija s Turingom. Da li to znači da si ga mi samo možemo zadati ili da moramo "došetati" do željenog mjesta?

[GauSs_]

[pravipurger]

Tog sam se i bojao
A onda glavu kod prve konfiguracije stroja smještamo proizvoljno za određivanje sedme ili?

[GauSs_]