Universaali Turingin kone (tai vastaava) aiheena kysymykselleni.
Jos aakkostona käytetään vain joukkoa {0,1} ja koodi koodataan siten, että se on prefix-free ja koodi rajoittaa itse pituutensa. Eli kun koodia luetaan tiedetään milloin se päättyy ilman erillistä ylimääräistä lopetusmerkkiä X.
Mikä on lyhin turingin kone siinä mielessä, että kun kone koodataan itsekseen, niin mikä on lyhin bittimäärä (ennätys)?
Jos aakkostona käytetään vain joukkoa {0,1} ja koodi koodataan siten, että se on prefix-free ja koodi rajoittaa itse pituutensa. Eli kun koodia luetaan tiedetään milloin se päättyy ilman erillistä ylimääräistä lopetusmerkkiä X.
Mikä on lyhin turingin kone siinä mielessä, että kun kone koodataan itsekseen, niin mikä on lyhin bittimäärä (ennätys)?
Vastaukset 3
Vanhimmat
Vasta eräs matematiikan opiskelija todisti erään minimaaliseen Turingin koneeseen liittyvän käsitteen. http://www.wolframscience.com/prizes/tm23/background.html
http://www.wolframscience.com/prizes/tm23/solution_news.html
Haetkohan tätä takaa?
Todistuksessa oli jotain epämääräisyyksiä, joita puitiin eräällä postilistalla. Ks. esim.
http://groups.google.com/group/sfnet.tiede.tietotekniikka/browse_frm/thread/22caa539295539da/f6d6a01fe8e19494?lnk=gst&q=wolfram#f6d6a01fe8e19494
ja siellä viitatut linkit.
Itse turingin kone saa olla "monimutkainen" eli värien määrällä ja tiloilla ei ole merkitystä, siis kysymys on siitä, että se simuloi ohjelmia jotka koostuvat 0 ja 1. Ja kun kone joka tietysti on itsessänkin ohjelma koodataan 0 ja 1:ksi niin kuinka lyhyt on enntäys eli tyyliin: Turingin kone A koodattuna on 0101010111011
(Nyt on itse asiassa aivan sama mikä universaali tietokone on kyseessä postin kone käy ihan hyvin, idea on siinä, että se tunnistaa 0 ja 1 muodostuvan kielen)
Että se voidaan näillä ehdoin koodata yhdeksi merkiksi.
Keksitkö todistuksen?