Moment, asi tomu nerozumim, ale podle http://mathworld.wolfram.com/BusyBeaver.html by sestistavovy busy beaver mel zapsat Sigma(6) jednicek, coz je > 1,29x10^865.
V te souvislosti me zaujalo, ze to je stroj, ktery zapise maximalni mozny pocet jednicek a zastavi se. Z toho by vyplyvalo, ze pokud mam n-stavovy TS, ktery uz zapsal vic, nez Sigma(n) jednicek, tak mam dokazano, ze se nezastavi?? [Fakt, ze to je 1. velke cislo, 2. nevycislitelna funkce pomijim.] Nebo v cem tomu nerozumim (myslim v teto konkretni malickosti, obecne do toho moc nevidim, ale to vim i bez vas :) ).
> Z toho by vyplyvalo, ze pokud mam n-stavovy TS, ktery
> uz zapsal vic, nez Sigma(n) jednicek, tak mam
> dokazano, ze se nezastavi??
Obavam se, ze ne. Do \Sigma(n) se pocitaji jednicky, ktere zbydou na pasce _po zastaveni stroje_, ne behem vypoctu. Vas n-stavovy TS muze vsechny zapsane jednicky zase smazat, a vesele skoncit.
Teda, abych rekl pravdu, ani jsem nedoufal ze na to nekdo prijde, muzu vedet jak ses k tomu dobral? :-)
Btw, odmena je tvoje, napis cislo uctu me, pripadne johance a odmena bude na tebe presmerovana. Btw. v clanku jsem sliboval i pifo, bude-li prilezitost, urcite ti ho rad koupim :-)
Pocet jednicek:
ve skutecnosti jsem vygoogloval jen BB 'k', pro ktery cisla patri. Nejak jsem nemel cas hledat dal, prece jenom prace obcas nepocka.
Nalezeni:
Asi nejlip podle google query:
turing machine halting problem example
turing machine halting problem seven
six state busy beaver
six state "busy beaver"
"busy beaver"
BB je zminen nekde u turing machine, vhodny kandidat kvuli zamereni clanku(trivialne vypadajici problem), odpovedi v diskuzi(algoritmus se zastavi, nerealnost nalezeni reseni vypoctem). Podobnost teto TM s BB je celkem zrejma.
No a pak jsem se uz jen stazil najit prislusny BB, ale trosku jsem si to zkomplikoval tim, ze jsem predpokladal, ze jsi zlomyslne prehazel stavy.
Odmena:
Myslim, ze honorar za tento clanek ti pravem nalezi(a urcite si to nemyslim sam ... ctenost, pocet reakci).
Ale piva se nevzdam, jen nevim, kdy bude prilezitost.
