Matemaatilise loogika praktikum

Teisipäev 10.15-11.45

Turingi masinate lisaülesanne

Cantori perfektne hulk. Kirjutada turingi masin, mis käitub sisendite korral järgnevalt

	  0    --> 1
          1    --> 101
	  11   --> 101000101
          111  --> 101000101000000000101000101
	  1111 --> 101000101000000000101000101....101000101000000000101000101
        

Eesmärgiks on realiseerida see võimalikult väheste käskude arvuga. Iga masinat hinnatakse järgneva funktsiooni alusel

log(ridade arv)+1*(täitmata lahtrite arv)+log(3)*(täidetud lahtrite arv)
See vastab bittide arvule, mida on vaja Turingi masina tabeli kirjeldamiseks. Parimad masinad on lühima kirjeldusega.

Lahendused. Laekus kaks arvestatavat lahendust: Hendrik Nigul (2p) ja Riivo Kolka (1p). Mõlemad kasutasid ülesande lahendamiseks erinevaid meetodeid.

Hendrik lähtus hulkade genereerimisel selle metastruktuurist. Nimelt kordab struktuur ennast rekursiivselt:

	  101000101000000000101000101
	  (101)(000)(101)(000)(000)(000)(101)(000)(101)
	  Esimene kordus
	  101000101
	  (101)(000)(101)
	  Teine kordus
	  101
	  Kolmas kordus
	  1
	

Seega tuleb alustada sümbolist 1 ning teisendada 1 -->101 ja 0-->000 täpselt n korda (Vaata koodi).

Riivo lähtus hulga definitsioonist. Kuna n hulgas on 3^n elementi, siis genereeris 3^n ühte ning seejärel jagas hulga kolmeks. Keskmise osa asendas nullidega ning nii rekursiivselt kahe ülejäänud osaga. Näide

	  111111111111111111111111111 Tase 0
	  111111111000000000111111111 Tase 1
	  111000111000000000111000111 Tase 2
	  101000101000000000101000101 Tase 3
	 

Lahenduses on varjatult realiseeritud funktsiooni rekursiivne väljakutse: q4 vastab rekursiooni põhjale ning q21 rekursiivsele väljakutsele (Vaata koodi).