Układanie kolorowych kafelków może ukrywać nierozstrzygalny problem
Kafelki Wanga to kwadraty z kolorami na czterech krawędziach. Dostajemy skończony zestaw typów i nieograniczoną liczbę kopii; sąsiednie krawędzie muszą mieć ten sam kolor. Pytanie brzmi, czy danym zestawem można pokryć całą nieskończoną płaszczyznę. Robert Berger udowodnił, że ogólny „domino problem” jest nierozstrzygalny. Nie istnieje algorytm, który dla każdego skończonego zestawu kafelków zawsze poprawnie zdecyduje, czy takie nieskończone ułożenie istnieje. Konstrukcje potrafią kodować przebieg maszyny Turinga, więc pytanie geometryczne dziedziczy granice problemu stopu.
Bardzo proste reguły lokalne
Każdy kafelek ma kolor północny, wschodni, południowy i zachodni. Kafelki układa się bez zmiany skali na siatce kwadratowej, a stykające się krawędzie muszą pasować kolorami. Reguła jest całkowicie lokalna: patrzymy tylko na sąsiadów. Mimo tej prostoty pytanie o możliwość wypełnienia całej nieskończonej płaszczyzny jest problemem globalnym.
Dlaczego duży prostokąt nie wystarcza
Jeśli zestaw potrafi pokryć kwadrat o boku milion, nie wynika z tego automatycznie, że potrafi pokryć całą płaszczyznę. Nieskończony obiekt może wymagać zgodności warunków na wszystkich skalach. To właśnie nieskończoność odróżnia klasyczny domino problem od wielu ograniczonych wersji na skończonej planszy, dla których zawsze można w zasadzie przeprowadzić skończone przeszukiwanie.
Kafelkami można symulować obliczenie
Klucz do nierozstrzygalności polega na zakodowaniu historii maszyny Turinga w kolejnych pasach ułożenia. Lokalne kolory wymuszają, by następny „wiersz czasu” był poprawnym następnikiem poprzedniego. W ten sposób istnienie całego nieskończonego tilingu można powiązać z zachowaniem obliczenia. Współczesne prace o Wang tiles nadal opisują klasyczny wynik Bergera jako redukcję prowadzącą do nierozstrzygalności.
Aperiodyczność pojawiła się przy okazji
Historia domino problem wiąże się także z aperiodicznymi zestawami kafelków — takimi, które potrafią pokrywać płaszczyznę, ale nie okresowo. Wang początkowo przypuszczał, że jeśli tiling istnieje, istnieje też tiling okresowy; Berger obalił tę hipotezę podczas prac nad nierozstrzygalnością. To pokazało, jak bogate globalne zachowanie może wynikać z banalnie lokalnych reguł dopasowania.
Granica obliczeń w geometrycznym przebraniu
Ten przykład jest szczególnie zapamiętywalny, bo problem nie wygląda jak program. Nie ma kodu źródłowego ani pętli — są kolorowe kwadraty. A jednak reguły są wystarczająco ekspresywne, by zasymulować obliczenia. Nierozstrzygalność jest więc własnością struktury problemu, a nie wyglądu jego interfejsu.
Nie każdy zestaw kafelków jest tajemniczy
Nierozstrzygalność problemu domino nie oznacza, że nie da się rozwiązać żadnego konkretnego układu kafelków. Dla wielu zestawów odpowiedź jest oczywista albo można ją ustalić konstrukcyjnie. Twierdzenie mówi o braku jednego algorytmu, który dla dowolnego skończonego zestawu kafelków zawsze zakończy pracę i poprawnie odpowie, czy da się nimi pokryć całą nieskończoną płaszczyznę. Ta różnica między „konkretny przypadek” a „uniwersalna procedura dla wszystkich przypadków” jest dokładnie tym samym rodzajem granicy, który pojawia się w problemie stopu. Kafelki są więc zaskakująco fizyczną, geometryczną postacią pytania o obliczalność.
Nieskończona płaszczyzna jest istotną częścią problemu
Gdyby pytanie dotyczyło skończonej planszy o zadanych wymiarach, liczba możliwych ułożeń byłaby skończona i w zasadzie można byłoby je wszystkie przeszukać. Problem domino pyta o możliwość pokrycia całej nieskończonej płaszczyzny. Nie można więc po prostu ustalić rozmiaru planszy, po którym brak rozwiązania staje się pewny dla każdego zestawu kafelków. To właśnie przejście od skończonego obszaru do globalnego zachowania na nieskończonej siatce umożliwia zakodowanie nierozstrzygalności.