1. Prvi kolokvij 2009. (PDF)
2. Prvi kolokvij 2010. (PDF)
3. Napišite program za RAM stroj koji izračunava funkciju
   • f: {x∈ℕ | x<5} → ℕ, zadanu sa f(x) = x + 2;
   • f: {(x,y)∈ℕ×ℕ | x≠y} → ℕ, zadanu sa f(x,y) = 1;
   • f: ℕ×ℕ → ℕ, zadanu sa f(x,y) = max{x,y};
   • f: {(x,y)∈ℕ×ℕ | x+y=5} → ℕ, zadanu sa f(x,y) = y;
   • f: {(x,y,z)∈ℕ×ℕ×ℕ | xy=z} → ℕ, zadanu sa f(x,y,z) = 0;
   • f: {(x,y,z)∈ℕ×ℕ | z=1} → ℕ, zadanu sa f(x,y,z) = x+y;
4. Napišite program za makro stroj koji izračunava funkciju
   • f: ℕ×ℕ → ℕ, pri čemu je f(x,y) = log_yx, ako je taj izraz dobro definiran, a x+y inače;
   • f: ℕ → ℕ, pri čemu je f(x) najveće cijelo od drugog korijena iz x.
5. Dokažite da su sljedeće funkcije primitivno rekurzivne:
   • f: ℕ×ℕ → ℕ, pri čemu je f(x,y)=⌊x/y⌋ ako je y>0, a inače je f(x)=x;
   • ost: ℕ → ℕ, gdje je ost(x,y) ostatak pri dijeljenju x sa y ako je y>0, a x inače;
   • min,max: ℕ^k → ℕ.
6. Dokažite da su sljedeći skupovi primitivno rekurzivni:
   • skup uređenih parova relativno prostih prirodnih brojeva;
   • skup prirodnih brojeva koji se mogu prikazati kao zbroj kvadrata dvaju prirodnih brojeva;
   • {(x,y,z)∈ℕ×ℕ×ℕ | y>0 i broj djelitelja od y je veći od x, a manji od z }
7. Drugi kolokvij 2009. (PDF)
8. Drugi kolokvij 2010. (PDF)
9. Popravni kolokvij 2010. (PDF)
10. Neka je n=2¹⁸¹3⁷. Odredite domenu i sliku jednomjesne funkcije {n}.
11. Neka je S rekurzivan podskup od ℕ. Mora li funkcija f: S → ℕ, definirana sa f(x)=x² biti parcijalno rekurzivna?
12. Neka je f: ℕ³ → ℕ definirana sa f(m,n,k)=⌊ ((m+1)/(n+1))^1/(k+1)⌋. Dokažite da je f rekurzivna funkcija.
13. Neka je A={e∈ℕ | {e}¹ je totalna funkcija}. Dokažite da ne postoji rekurzivna funkcija f: ℕ → ℕ čija je slika skup A.
14. Postoji li racionalni broj q za koji funkcija f: ℕ → ℕ definirana sa f(n)=⌊|nq|⌋ nije rekurzivna?
15. PDF sa zadcima vezanima za primjenu Riceovog teorema i teorema rekurzije.