Izračunljivost

[mona]

Što sve treba reći u definiciji klase primitivno rekurzivnih funkcija??
Samo izreći definiciju 4. iz predavanja ili treba još nešto dodatno definirati??

[bleki88]

do kud se piše teorija u prvom kolokviju, tj. do kojih slajdova

[Zvjezdica]

Zadnje je P-izračunavanje s x.

Da li bi mi netko riječima objasnio ovaj zadatak: R1=n,R2=m,makro-stroj provjerava je li n>m. Ako da,stroj stane i u Ro napiše 0,ako nije,stroj stane i u Ro zapiše 1.

1.ZERO Ro
2.INC Ro
3.MOVE R1 TO R3
4.MOVE R2 TO R4
5.DEC R3,9
6.DEC R4,8
7.GOTO 5
8.ZERO Ro
9.STOP

(npr korak 5. za n=2, dobijemo n=1i ode na stop,i što onda?)

Hvala!

[C]

@Zvjezdica:
Čini mi se iz tvog pitanja da te buni DEC instrukcija.
Ona radi točno jednu od dvije stvari (ali ne obje):
1) smanji registar (u slučaju da je njegova trenutna vrijednost >0)
2) skoči na neku liniju (u slučaju da je trenutna vrijednost registra =0)

Ugl., 2 primjera izvršavanja programa.

n=2, m=3

1,2. Ro=1 (na početku pretpostavljamo da je m>n)
3,4. (samo premještanje varijabli)
5. n=1
6. m=2
7. (idemo opet na pet, pisat ću linije redom kako se izvršavaju)
5. n=0
6. m=1
7. (opet na 5)
5. (sada je n=0, pa ga ne smanjimo, nego skočimo na liniju označenu drugim parametrom, što je u ovom slučaju 9)
9. Kraj programa
U Ro se nalazi 1, što smo i trebali dobiti (jer nije n>m)

*
Sada pogledaš primjer n=2, m=1
1,2. Ro=1 (na početku pretpostavljamo da je m>n)
3,4. (samo premještanje varijabli)
5. n=1
6. m=0
7. (idemo na 5)
5. n=0
6. (kako je m=0, skačemo na 8 )
8. Ro=0
9. Kraj programa

U Ro se nalazi 0, što smo i trebali dobiti (jer je n>m)

[Zvjezdica]

HVALA!!!!!!!!!!!!!!!!!!!! Sad je sve jasnije

Ali ako bi još netko napisao rješenje ovog zadatka, bila bi još sretnija!
0<x<y, napisati prog za ram stroj koji izračunava f(x,y)=x-1

[dosed_girl]

mene zanima kako definirati sljedeće:

a) klasa rekurzivnih funkcija
b) klasa parcijalno rekurzivnih skupova

e i da:

c) rekurzivnost funkcije definirane kontrakcijom

zna li netko?

_________________
a part of me gets sick / a part of me gets sore

[insane_raver]

[Blockflöte]

[dosed_girl]

[insane_raver]

valjda samo modificiramo...
tako ja barem mislim sutra ako dobijem takvo pitanje

[glava]

Zna li se kada će rezultati kolokvija?

[frances]

Sta je zadnje obradjeno na predavanjima?

[Charmed]

7. cjelina(nisam sigurna da li je ista oznaka od lani i sad).

Btw. da li ima netko dobar ko bi stavio na net vježbe koje smo imali nakon kolokvija...

[frances]

7.cjelina od lani(oni slajdovi sa stranice) ili 7.cjelina od ove godine? Zbunjena sam, ali hvala u svakom slucaju:)

[Charmed]

7. cjelina od ove godine (tak je pisalo na projektoru)

[Charmed]

Jel se netko sjeća,do kada moramo predati seminarski rad?

[pifka]

da li mozda netko ima kakve informacije o usmenom?

[Charmed]

Ima koja dobra duša koja je rješavala zadatke za vježbu iz izračunljivosti, da mi ih pošalje? Bila bi neizmjerno zahvalna!

[Atomised]

Vrijedi li onaj popis pitanja s profesorove stranice i za ovu godinu? Vidim da su 2009. i 2010. godine bila samo pitanja s tog popisa, a ne sjećam se da je to ove godine itko uopće spominjao.

[kkarlo]

Profesor najavio slijedeće:
Teorija standardno:
definicije - 3 boda
iskazi teorema - 3 boda
dokaz - 4 boda

Zadaci:
2 su programi(pretpostavljam RAM stroj)
2 su primitivne rekurzivnosti funkcija i skupova
1 zadatak je nešto po izboru profesora...

Ne znam koliko pomaže, al eto... čisto da se zna.