Od MI do MU
Debiutancka i najbardziej znana książka Douglasa Hofstadtera, Gödel, Escher, Bach. An Eternal Golden Braid, uchodzi za niemal kultową. Przeczytałem ją na początku lat 80., czyli niedługo po pierwszym wydaniu (1979) i od czasu do czasu do niej powracam. To wciągające, miejscami błyskotliwe popularno-naukowe czytadło z podtekstami, przystępne dla każdego, co nie oznacza, że nie trafiają się fragmenty wymagające sporego wysiłku intelektualnego. Przeciwnie, jest ich niemało, ale autor wciela się w rolę cierpliwego, mądrego nauczyciela, tłumaczącego niektóre sprawy nawet przesadnie drobiazgowo. Większość podtekstów pozostawia jednak domyślności czytelników, więc nic dziwnego, że mnóstwo osób (także gros recenzentów) miało i ma kłopoty z określeniem, o czym właściwie jest ta książka. Być może nie świadczy to najlepiej o autorze, skoro w związku z tym zdecydował się we wstępie do kolejnego, jubileuszowego wydania u progu XXI wieku napisać wprost, co „miał na myśli” zagłębiając się w tematy tak różne, jak utwory Bacha, rekurencja, składnia, buddyzm, paradoksy, mrówki, tłumaczenia, sztuczna inteligencja, języki programowania, DNA, wirusy, wolna wola, sztuki piękne itd. Wykładając kawę na ławę zaczyna zdaniem: to moja bardzo osobista próba wyjaśnienia, jak to się dzieje, że istoty świadome, uduchowione powstają z materii nieożywionej… W tym momencie wiekszości czytelników książki, nie wyłączając piszącego te słowa, szczęka opada.
Nie brak w GEB łamigłówek. Pozwolę sobie przytoczyć jedną z nich, tym śmielej, że ani to, ani żadne inne dzieło Hofstadtera dotąd nie zostało – o dziwo – wydane po polsku. Zadanie stanowi coś w rodzaju wstępu do nauki o systemach formalnych.
Dysponujemy dowolną liczbą liter M, I oraz U. Zaczynamy od wyrazu MI, który możemy przekształcać w kolejnych krokach, tworząc za każdym razem nowy wyraz, zgodnie z następującymi regułami:
1. jeśli wyraz kończy się literą I, można dodać do niego na końcu U.
2. wyraz Mx można przekształcić w Mxx, gdzie x jest dowolną literą lub ciągiem liter.
3. fragment złożony z trzech liter I można zastąpić literą U.
4. fragment UU można usunąć.
Czy stosując podane reguły uda się przekształcić MI w MU? A jeśli nie, to dlaczego?
Komentarze
Z tego co sobie myślę pomalutku to wychodzi mi, że zadanie byłoby rozwiązalne gdyby potęga dwójki była podzielna przez 6, wtedy powielalibyśmy litery I aż do tej ich liczby, dodali na końcu U a potem zamieniali III na U , no i na koncu UU po kolei kasowalibysmy.
Witam z racji tego, iż ten blog jest czytany głównie przez ludzi, którzy lubią myśleć i rozwiązywać łamigłówki.
Chciałbym zaprosić do wzięcia udziału w kombinacyjnej grze Shogi – są to japońskie Szachy zbliżone zasadami do zwykłych, jednak trzeba w nich więcej kombinować. Szukanie mata (Tsume) w 10 posunięciach jest na porządku dziennym. Jako ciekawostke dodam, iż najdłuższy nieuchronny mat w Shogi, który został stworzony, liczy ponad 1000 posunięć :)…
Zapraszam na stronę http://www.shogi.pl – tam można znaleźć więcej informacji na temat organizowanego marcowego turnieju w Warszawie.
Pozdrawiam
Adrian
1. Nie da sie (co nie zaskakuje, bo gdyby sie dalo to zadanie musialoby byc dosc proste).
2. Interesuje nas tylko ilosc literek I w ciagu. Pytamy czy z ilości = 1 możemy dojść do ilości = 0.
Operacje 1. i 4. -> nie zmieniają ilosci I.
Operacja 2. -> podwaja ilosc I
Oeracja 3. -> zmniejsza ilosc I o 3.
I teraz tylko wystarczy zauważyc, że podwajanie i odejmowanie 3 nigdy nie zrobić z 1 zera (formalnie np. przez modulo 3 jak niżej).
Formalniej chyba mozna to napisac tak:
Niech S bedzie funkcja, ktora kazdemu ciagowi przyporzadkowuje liczbe 0, 1 lub 2.
S (ciag) = liczba znakow „I” w ciagu ( modulo 3).
Wykonywanie operacji 1., 3. i 4. na ciagu nie zmieniaja jego wartosci S.
Operacja 2. „podwaja” wartosc S.
Czyli jeśli S wynosilo 1, bedzie równe 2; a jeśli było 2 -> będzie 1.
Ponieważ zaczynamy od wartości S=1, nigdy nie dojdziemy do wartości S=0.
Przypiszmy tekstom wartości liczbowe równe reszcie z dzielenia przez 3 liczby liter I w danym tekście.
Dla przykładu w tekście MMIUIIMIUUI litera I występuje 5 razy, dlatego temu tekstowi przypiszemy 2, czyli resztę z dzielenia liczby 5 przez 3. Zapiszmy to tak: f(MMIUIIMIUUI) = 2
Teraz przyjrzyjmy się regułom przekształcania.
Reguła pierwsza (r1) nie zmienia liczby liter I. Zatem f(tekst)=f(r1(tekst)).
Reguła druga (r2) zwiększa liczbę liter I dwukrotnie. Zatem:
– jeśli f(tekst)=0, to f(r2(tekst))=0,
– jeśli f(tekst)=1, to f(r2(tekst))=2,
– jeśli f(tekst)=2, to f(r2(tekst))=1.
Reguła trzecia (r3) zmniejsza liczbę liter I o 3. Zatem f(tekst)=f(r3(tekst)).
I wreszcie reguła czwarta (r4) – podobnie jak r1 – nie zmienia liczby liter I. Zatem f(tekst)=f(r4(tekst)).
Dla naszego wejściowego tekstu f(MI)=1. Jakiekolwiek zastosowanie wymienionych reguł nie przekształci tego tekstu tak, aby jego wartość po przekształceniach była równa 0. Natomiast dla tekstu końcowego f(MU)=0. Co dowodzi nieprzekształcalności tekstu MI w tekst MU.
Z pozdrowieniami,
Jazz_off
Oczywiście nie da się.
Każda z reguł pozostawia liczbę liter I niepodzielną przez 3. Zatem nie otrzymamy żadnego wyrazu bez liter I.
Adam
Nie widzę możliwości przekształcenia MI w MU.
Reguły zadania są tak ustalone, że tworzą one zaporę nie do przebycia pomiędzy słowami MI i MU.
Pozdrawiam
Nie da rady przekształcić MI do MU.
Żeby osiągnąć MU, w poprzednim kroku musimy mieć MIII (lub większą ilość I, ale podzielną przez 3).
Startujemy od jednego I (jeden nie jest podzielne przez trzy).
Ilość I możemy zawsze podwajać zgodnie z regułą drugą, ale startując od jednego nie osiągniemy w ten sposób ilości I podzielnej przez 3.
Reguła trzecia pozwala usunąć III, ale to nie zmienia ich podzielności przez trzy (tzn. jeżeli ilość I nie była podzielna przez trzy, to usunięcie trzech sztuk powoduje, że dalej ta ilość nie jest podzielna).
Zamotałem, może ktoś to ładniej ubierze w słowa 🙂
Pozdrawiam
Szwagier