Pět pilných včeliček

13.6.2008 15:54 | Přečteno: 1825× | GNU | | poslední úprava: 13.6.2008 18:00

Úloha byla formulována v roce 1962. Současný šampión pro 5 stavů (viz program) je z roku 1989. Prohlédněte si jej, a zkuste odhadnout jak velké číslo program asi vypíše. Najdete program, který vypíše větší číslo? Dokážete, že takový program neexistuje? Oboje za 100 bodů a nehynoucí slávu (naked chicks ale asi nebudou). Zadání:

1) Měnit můžete pouze tělo bloku while (1).
2) Nejvýše na 5 místech můžete testovat proměnnou $sym, jiné testy nejsou povoleny.
3) $sym můžete měnit, ovšem pouze na 1 nebo undef.
4) Dále můžete volat left, right, nebo last.
5) Bezprostředně po každém left nebo right musí následovat další test.

#! /usr/bin/perl -w
use strict;

my (@left, $sym, @right, $cnt);
sub left { push @right, $sym; $sym = pop @left; $cnt++; }
sub right { push @left, $sym; $sym = pop @right; $cnt++; }

while (1) {
    # 1
    if ($sym) {
        left;
    } else {
        $sym = 1; right;
        # 2
        while ($sym) { right; }
        $sym = 1; right;
    }
    # 3
    if ($sym) {
        $sym = undef; left;
        # 4
        last unless $sym;
        $sym = undef; left;
    } else {
        $sym = 1; right;
        # 5
        while ($sym) { left; }
        $sym = 1; left;
    }
}
print "$cnt\n";

       

Komentáře

[Kyosuke]

Najdete program, který vypíše větší číslo? Dokážete, že takový program neexistuje?

No nehynoucí slávu by asi nikdo neodmítl, ale rozhodně jsou jednodušší způsoby, než tohle. (Ale kdyby to tu někdo skutečně dokázal, byl by to pro Ábíčko moc pěkný způsob, jak se nesmrtelně zapsat do dějin... "Řešení problému XYZ bylo prvně publikováno v renomovaném...ehm, cože? Komentáři na komunitním linuxovém serveru?" )

[deda.jabko]

spomal, ja jsem treba cast diplomky publikoval na abclinuxu (vcetne podekovani ctenarum)... takze uz zbyva jenom, aby microsoft propustil takove losery jako simon peyton jones, rekl jim, ze haskell je o nicem. a misto toho najal par ,,zkusenych programatoru'', aby vyvinuli microsoft advanced enterprise lisp professional edition a abclinuxu bude slavne... to je muj plan... ale asi bude lepsi, kdyz zkrizim delfiny s ovcemi, na ovce hopkave.... ;-]

[Kyosuke]

Mno znám člověka, co kříží Scheme s Haskellem, proti tomu by i ovce skákavá byla nicka, nechceš do ní ještě vrazit kus chobotnice? Simon PJ mi přijde v pohodě. Aspoň je zábavnej, ne jako Ballmer.

[deda.jabko]

kříží Scheme s Haskellem

vime o tom vic?

nechceš do ní ještě vrazit kus chobotnice?

ja bych tam vrazil spis chameleona... neviditelna ovce hopkava, by byla fakt sila!

[Kyosuke]

vime o tom vic?

Přes společného kamaráda vím jen to, že se nedávno podařilo zkompilovat faktoriál...

ja bych tam vrazil spis chameleona... neviditelna ovce hopkava, by byla fakt sila!

A o čem asi tak mluvím, že? A tohle je taky pěkné. Chobotnice sice umí líp napodobit hrubozrnnou texturu povrchu, ale sépie, jak vidno zhruba kolem 3:25, má zase větší "obnovovací frekvenci". (Škoda, že těch opravdu dobrých videí barvoměny mořských hlavonožců zase tolik není. A to se po nich pídím docela dlouho.) Futurama má hypnožábu, ale reálný svět má aspoň tu hypnosépii. Kromě toho myslím, že pro neviditelnou skákající ovci by osm chapadel byla přidaná hodnota - nechceš si toho chameleóna fakt ještě rozmyslet?

[qiRzT]

A jaký je vlastně to zadání?

[Kyosuke]

Tipoval bych zadání na "Najdi takový Turingův stroj o pěti stavech a dvou symbolech, který se zastaví po co největším počtu kroků.".

[zde]

Aby tě husa kopla! Turingův stroj je pro mě nepředstavitelně ošklivé slovo, kterému jsem se chtěl za každou cenu vyhnout...

[Kyosuke]

Mám třeba homeomorfismu říkat "hřejivá, chlupatá věc", jen proto, že to je nepředstavitelně ošklivé slovo?

[Messa]

Možná by se po takové změně terminologie našlo mezi informatiky víc normálních lidí a možná i holek

[frEon]

Myslim, ze by si normalini lidi pomysleli, ze tem informatikum uz uplne hrablo.

[zde]

Jo. Ale doporučuju radší něco jako "jeden na jeden spojitě".

[xsubway]

[thingie]

No, ono jsou to hlavně slova dvě.

[zde]

Mě z nich vadí jen to první, "stroj" skousnu.

[Kyosuke]

Nemáš toho pána rád? Fobie z matematiky, homofobie, fobie z halting problému, nebo pán radši spíš lambda kalkul?

[Ondrej 'SanTiago' Zajicek]

Vyborne. Prvni cast problemu (dekodovani zadani do srozumitelne podoby) mame vyresenou.

[zde]

Najít takovej program, kterej se zastaví (tj provede to "last"- to je perlovská syntaxe pro vyskočení ze smyčky), a předtím co nejvíckrát inkrementuje $cnt. Díky omezením na počet stavů je takových programů pro každé N jen konečný počet, a dají se snadno generovat a provádět. Stačí tedy vyloučit ty které se zacyklí, a ze zbylých vybrat ten nejlepší. Problém je že těch programů pro N=5 existuje pár miliónů, a zhruba stovka z nich je "problémových". Při spuštění to cyklí nad všechny rozumné limity, takže je hodně pravděpodobné že nikdy neskončí, ale nikdo pro to zatím neodvodil důkaz. Existuje tedy pořád šance že některý z těch programů někdy skončí, a pak logicky vytiskne ještě mnohem větší číslo než současný "šampión".

[qiRzT]

A formálně je to tedy ten Turingův stroj? Nebo jen konečný (zásobníkový) automat? Perl neovládám, takže z toho kódu toho moc nevyčtu

[Jirka P]

Jo, je to turingáč s binární abecedou a 5 stavy. Zajímavý na tom je, že fce (N -> max kroků, za které se nějaký TS s N stavy zastaví) není vyčíslitelná.

[qiRzT]

Na to stačí pár pojmů z teorie grafů. Třeba popisy algoritmů červeno-černých stromů (porovedeme něco pokud je strýc černý), okolo koster se dá taky určitě najít hodně zajímavě znějících tvrzení, nebo takové ušaté lemma...

[qiRzT]

Hups, to patří sem.

[andree]

tak presne toto ma caka.. vycislitelnost... dosiel som tak do 1/4 poznamok, uz asi 3x - a vzdy sa zastavim, ze vlastne neviem o com je rec... fakt najvacsi teoreticky humus co som zatial videl...

[Zdeněk Štěpánek]

Dneska jsem s kolegy připravoval učebnu pro celostátní kolo SoČ a zrovna jsme byly u matematiků. Přišli tři brýlatí pánové, už od pohledu divní, začetli se do svých lejster, začali mluvit jakýmsi jazykem vzdáleně připomínajícím češtinu. Radši jsem dodělal ty kompy a rychle zmizel...

Myslím že tito pánové by z tebe měli radost

Zdeněk

[hikikomori82]

Asi nikdy nepochopim ludi ktory riesia neexistujuci problem. Ale budis.

#!/bin/bash
echo 99999999999999999999999999999999999999

[freshmouse]

Přesně. A to ani nemluvím o výkonu toho "jejich" krámu a tohoto.

Holt ne všem je shůry dáno programovat: programování je postup při řešení problému, ne vytváření problému.

[qiRzT]

Bych se hádal, každý přeci ví, že počítače umí efektivně řešit problémy, které by bez počítačů neexistovaly

[David Jaša]

Odvoláš to nebo ti mám dát nějaké vypečené zadání vedoucí na metodu konečných prvků?

[qiRzT]

Neodvolám Aspoň zjistím co to je (i když to možná už vím, ale nevím, že se tomu tak říká).

[petr]

No, při čtení zápisku jsem si říkal, že holt každýho zajímá něco jinýho. Jeden ladí SQL dotazy, druhý zase tohle. Ale když jsem četl komentář

Jo, je to turingáč s binární abecedou a 5 stavy. Zajímavý na tom je, že fce (N -> max kroků, za které se nějaký TS s N stavy zastaví) není vyčíslitelná.

tak jsem již na sto procent přesvědčen, že bude lepší se živit čímkoli, jen né vývojem software Děkuji za definitivní důvod pro mé váhání.Hned zítra dávám výpověď.

[Messa]

Můžeš být v klidu (tedy pokud nepracuješ jako výzkumný pracovník), tohle není vývoj software, to je spíš vývoj vývoje softare. Tohle (AFAIK) normální programátoři neřeší ani ve volném čase

[petr]

Jo, také si dokážu představit jiný věci (nebo činnosti), který dělat vnoci než tohle Ale abych řekl pravdu, vývoj software mě baví. Mám to moc rád, ale bere mi to moc času. Zhruba nějakých 16 hodin denně plus víkendy. Možná jsem až moc poctivý. Vše musí být zdokumentováno, na vše musí být TestCase, vše musí být jednoduché a elegantní. Zdrojový kód musí vypadat krásně, vše musí mít jednotný "coding style". A jistě si dovedeš představit, jak asi vypadá kód druhých a tedy i co po nocích dělám, že? Takhle to dál nejde. Jsem maximalista a musím si tedy najít práci, kterou "běžný člověk" zvládne za dvě hodiny a abych tedy já měl těch zbylých šest hodin pracovní doby na to, abych to dovedl k podobě, ve které to chci mít. Ještě si asi odkroutím tu služební cestu někde v Evropě, protože jsem přišel o bydlení (teď píšu ze sluźebního bytu v Hradci Králové) a pak uvidím; pak se asi na chvíli nastěhuju na Bulovku na kapačky Koukám, že jsi na Karláku. Já se tam narodil (u Apolináře) a celých 22 let jsem prožil na Jiráskově náměstí. Pak jsem se s borcem přestěhoval na Pankrác. Tam jsem byl čtyři roky. Z okna jsem koukal na budovu České televize. Vždycky jsem si přes zimu dělal srandu, když byla mlha, že "ani nevidím na televizi" No, přespávám u rodičů, kocour Angrešt je u nich nadšenej. Jeden jejich pokoj je jako celý byt, kde jsem bydlel. Snad se mu daří dobře, klukovi jednomu. Proč to píšu? Nevím. To je jedno. Zapomeň na to…

[zde]

Nesplňuje hned první podmínku.

[kralyk z abclinuxu]

Á, dostalo tě to. Byls zmanipulován. Máš teď potřebu dodržovat dané podmínky plus ještě přesvědčovat ostatní k jejich dodržování. Myšlenka, že tyto podmínky veskutečnosti neexistují, již pro tebe pomalu ale jistě přestává být racionální, s čímž se ztrácí i svoboda mysli. Bohužel již není cesty zpět... :P

[laco]

Ani se neozývej Kralyk, kvůli tobě jsem tu nedávno pěkně dostal na frak já od nejmenované osoby. Byl jsem zmanipulován jednou tvojí starší zprávičkou.