Z pamiętnika ciągotki B

24 stycznia 2009
Marek Penszko

Chciałabym być samotna, ale to nie takie proste. Ciągle przyczepia się do mnie jakiś A lub C, a nawet spokrewniony B…
W moim świecie są tylko trzy rodzaje bezwymiarowych istot-punktów – A, B i C. Na świat przychodzimy jednak jako jednowymiarowe, ukierunkowane pary – AC, CB lub BA. Potem łączymy się albo dzielimy, tworząc krótsze lub dłuższe literowe ciągi, dlatego właśnie zwą nas ciągotkami. Naszymi przekształceniami rządzą dwie podstawowe reguły:
(1) w każdym miejscu pary lub ciągu może pojawić się lub (jeśli występuje) zniknąć para AC, CB lub BA.
(2) tuż po AB może pojawić się C, tuż po BC – A, zaś tuż po CA – B.
W tej chwili jestem z A i oboje tworzymy parę BA.
Ile co najmniej i jakich zmian powinno nastąpić, abym została sama?

Gwoli jasności, od siebie dodam przykład, jak najszybciej można dotrzeć od AC do ABC:
AC > ACAC (1) > ACABC (2) > ABC (1).
Proszę zwrócić uwagę, że w tym przypadku sekret przekształcenia polega na posłużeniu się tą samą parą AC, która pojawia się i znika.

Świat ciągotek i ciągotków powstał pod wpływem lektury bestsellera  Douglasa Hofstadtera, a ściślej – zamieszczonej w tej książce łamigłówki, którą cytowałem w poprzednim wpisie. Nie miała ona niestety rozwiązania, co precyzyjnie uzasadnili Państwo w komentarzach. Mówiąc najkrócej, brak rozwiązania spowodowany był niemożnością pozbycia się litery I. Powyższy ciągotkowy świat i łamigłówka są więc następstwem ciągotek do „normalnych” łamigłówek, czyli takich, których rozwiązaniem nie jest brak rozwiązania.

Łamigłówki z systemami (językami) formalnymi, w których dokonując zmian zgodnie z określonymi regułami należy dotrzeć od jednego stanu do drugiego, przypominają algorytmy. Są znacznie starsze nie tylko od książki Douglasa Hofstadtera, ale i od ojca jej autora (fizyka i noblisty, Roberta). Kiedy raczkowały, nikt nie słyszał ani o językach formalnych, ani o algorytmach. Dziś także powstają na ogół bez związku z informatyką, a jedynie gwoli rozruszania szarych komórek, choć większość z nich można rozgryźć, pisząc prosty program komputerowy. Najczęściej są liczbowe. Postaram się przygotować jakieś ciekawe przykłady do następnego wpisu.