Izračunljivost - druga studentska zadaća

[mdoko]

Zadaci su u donjoj listi. Ako ponestane zadataka, javite se (mailom ili postajte ovdje), pa cu smisliti jos zadataka.

1. Definirajte regularne jezike. Kako se dokazuje ekvivalencija končnih automata i regularnih izraza. Pronađite primjer izračunljivog jezika koji nije regularan. Kako se (njačešće) dokazuje neregularnost nekog jezika? [Goran Repinc]

2. Definirajte konačne automate i nedeterminističke konačne automate. Dokažite ekvivalenciju konačnih automata i nedeterminističkih konačnih automata. [Ksenija Hodak]

3. Definirajte kontekstno slobodne jezike. Pronađite primjer izračunljivog jezika koji nije kontekstno slobodan. Kako se (najčešće) dokazuje neregularnost nekog jezika? [Zoran Gaćeša]

4. Definirajte kontekstno slobodne gramatike i Chomskyjevu normalnu formu. Dokažite da se svaka kontekstno slobodna gramatika može prikazati u Chomskyjevoj normalnoj formi. [Ilija Pavlic]

5. Definirajte višetračni Turingov stroj. Kako se dokazuje ekvivalencija višetračnog Turingovog stroja i "običng" Turingovog stroja? [Antonija Malenica]

6. Definirajte nedeterministički Turingov stroj. Kako se dokazuje ekvivalencija nedeterminističkog Turingovog stroja i "običng" Turingovog stroja? [Jurica Levatić]

7. Definirajte pojmove izračunljivih i definabilnih realnih brojeva. Koja je veza među tim dvama klasama brojeva? [Marija Bajić]

8. Dokažite da je RAM-stroj s tri instrukcije (INC, DEC, GOTO) ekvivalentan RAM-stroju s dvije instrukcije (INC, DEK). [Jelena Kovačić]

9. Postov stroj je sličan Turingovom, s jednom razlikom, a to je da Postov stroj ne može u jednom koraku pisati po traci i pomicati se, nego samo jedno od to dvoje. Dajte formalnu definiciju Postovog stroja i dokažite ekvivalenciju Postovih i Turingovih strojeva (ili barem opišite ideju dokaza). [Jurica Bradarić]

10. Dajte intuitivni opis i formalnu definiciju Turingovog stoja koji ima dvodimenzionalnu "traku" (nešto kao beskonačna šahovska ploča). Dajte ideju dokaza ekvivalencije s (običnim) Turingovim strojem. [Goran Ljubej]

11. Dajte intuitivni opis i formalnu definiciju "višeglavog" Turingovog stoja (više glava koje čitaju i pišu po jednoj traci). Dajte ideju dokaza ekvivalencije s (običnim) Turingovim strojem. [Danijel Mandić]

12. Da li za svaku RAM-izračunljivu funkciju postoji RAM-program koji ne koristi niti jedan registar s indeksom većim od ?

13. Dajte formalnu definiciju Turing-izračunljive funkcije. Dokažite da su po toj definiciji zbrajanje i množenje Turing-izračunljive funkcije. [Andreja Jerešić]

U uglatim zagradama su imena studenata koji su već na vježbama u ponedjeljak rezervirali svoje zadatke.

Rezervacija 9. zadatka, kao i dodatnih zadataka (ako ih bude) ide po principu "tko se prvi javi" tj. tko prvi posta na ovom topicu rezervaciju zadatka.

Za većinu zadataka odgovore i upute možete pronaći u knjizi Michaela Sipsera Introduction to the Theory of Computation (knjiga postoji u našoj knjižnici), također, nije na odmet prokopati po Internetu za dodatnim izvorom informacija


EDIT: dodan 10. i 11. zadatak

_________________
Extraordinary claims require extraordinary evidence. – Carl Sagan

[m00nblade]

Ja uzimam 9.zadatak
Jurica Bradarić

_________________
Real programmers don't comment their code. If it was hard to write, it should be hard to read.

[Gogs]

Može meni zadatak br. 10
Goran Ljubej

_________________
Dvije stvari su beskonacne, svemir i ljudska glupost, ali sto se svemira tice nisam posve siguran.

[DanijelM]

11. zad.
Danijel Mandić

_________________
If the truth can be told so as to be understood, it will be believed.

[iuppiter]

Može jedan zadatak za mene?
Andreja Jerešić

_________________
Stultorum plena sunt omnia.

/Ciceron/

[mdoko]

[iuppiter]

13

_________________
Stultorum plena sunt omnia.

/Ciceron/

[Gost]

12. zadatak
Vedrana Kezele

[pero]

Pazi, čini mi se da mdoko ne vidi postove gostiju

[mdoko]

[Gost]

demokratsko pravo na komentar!:
Luka Ritz!
svašta..