Wyspa robotów

ilustracja D. Mróz

W książce Raymonda Smullyana Szatan, Cantor i nieskończoność oraz inne łamigłówki, znajduje się rozdział Wyspa robotów a w nim opis wyspy, na której działają roboty potrafiące tworzyć i niszczyć inne roboty.

Każdy robot działa według programu zapisanego jako skończone słowo złożone z wielkich liter.

Małych liter będziemy używać do oznaczenia dowolnych słów (skończonych ciągów złożonych z dużych liter).

Przykłady słów:

• ABC słowo złożone z liter A, B i C
• Ax słowo rozpoczynające się od litery A za którą znajdują się litery słowa x
• ABxC słowo rozpoczynające się od liter A i B, zakończone literą C, natomiast między początkowymi literami AB i końcową C znajduje się pewne słowo x
• xx słowo będące sklejenie słowa x z samym sobą (np. jeśli x = ABC, to xx = ABCABC)

Mówimy, że x tworzy y, jeśli robot sterowany programem x tworzy robota sterowanego programem y.

Mówimy, że x niszczy y, jeśli robot sterowany programem x niszczy robota sterowanego programem y.

Niektóre wielkie litery mają specjalne znaczenie.

• Reguła Q: Dla dowolnego słowa x, słowo Qx nazywa słowo x (inaczej mówiąc Qx jest nazwą słowa x).
• Reguła R: Jeśli x nazywa y, to Rx nazywa yy.
• Reguła C: Jeśli x nazywa y, to Cx tworzy y.
• Reguła D: Jeśli x tworzy y, to Dx niszczy y.

Dla przykładu, jeśli x jest dowolnym słowem, to DCQx niszczy x, ponieważ CQx tworzy x.

W programie napisanym w Prologu przyjmiemy następujące założenia:

• słowo złożone z wielkich liter będzie reprezentowane listą złożoną ze stałych zapisanych małymi literami (np. słowo ABC będziemy zapisywać w postaci listy [a, b, c])
• słowo ABCx zapisywać będziemy w postaci listy [a, b, c | X]
• jeśli z = xy, to będziemy to wyrażać warunkiem append(X, Y, Z)

Reguły Q, R, C i D zapiszemy w Prologu w postaci następujących klauzul:

nazywa([q | X], X).
nazywa([r | X], Z) :- nazywa(X, Y), append(Y, Y, Z).
tworzy([c | X], Y) :- nazywa(X, Y).
niszczy([d | X], Y) :- tworzy(X, Y).

Jeśli chcemy poznać program x dla robota tworzącego własną kopię (tworzącego robota o programie x), to wydaje się, że wystarczy zadać pytanie:

?- tworzy(X, X).
X = [c, q | X]

Jednak znaleziony w ten sposób program jest nieskończony: x = CQx = CQCQCQCQCQ...

Aby ograniczyć poszukiwane programy do słów skończonych, trzeba w pytaniu narzucić na zmienną X warunek, że odpowiada jej skończona lista (skończone słowo). W tym celu użyjemy predykat length/2:

?- length(X, _), tworzy(X, X).
X = [c, r, q, c, r, q]

Zatem robot tworzący swoją kopię sterowany jest programem CRQCRQ. Sprawdźmy to:

1. Słowo RQCRQ, nazywa CRQCRQ, ponieważ słowo QCRQ nazywa słowo CRQ (reguła R).
2. Słowo CRQCRQ tworzy słowo CRQCRQ, ponieważ słowo RQCRQ tworzy słowo CRQCRQ (reguła C).

Poszukajmy teraz robota x tworzącego robota y, który to robot y niszczy robota x:

?- length(X, _), tworzy(X, Y), niszczy(Y, X).
X = [c, r, q, d, c, q, c, r, q],
Y = [d, c, q, c, r, q, d, c, q, c, r, q]

Zatem robot CRQDCQCRQ tworzy robota DCQCRQDCQCRQ, który go niszczy.

Zapytajmy się czy jest taki robot x, który niszczy robota y, ale robot y może stworzyć robota z, który go pomści (zniszczy robota x):

?- length(X, _), niszczy(X, Y), tworzy(Y, Z), niszczy(Z, X).
X = [d, c, r, q, c, q, d, c, q, d, c, r, q],
Y = [c, q, d, c, q, d, c, r, q, c, q, d, c, q, d, c, r, q],
Z = [d, c, q, d, c, r, q, c, q, d, c, q, d, c, r, q]

Zatem robot DCQDCRQVQDCQDCRQ pomści robota CQDCQDCRQCQDCQDCRQ zniszczonego przez robota DCRQCQDCQDCRQ.

Wszystkie reguły omawiane w rozdziale Wyspa robotów znajdziesz w pliku roboty.pl.