Od programowania do kafelkowania (i z powrotem)

Jednym z ważnych momentów w historii informatyki i matematyki było stworzenie przez Alana Turinga modelu komputera, nazwanego później maszyną Turinga. Czy może być coś ciekawego w matematycznym opisywaniu czegoś, co tak dobrze znamy? Może, bo tylko tak można poznać parę ciekawych właściwości komputerów. I dowiedzieć się czegoś o kafelkowaniu.

Pomocnik kafelkarza

Zapomnijmy na chwilę o komputerach, Maszynach Turinga i programach. Wyobraźmy sobie Adama. Adam postanowił dorobić sobie przez wakacje. Dlatego zatrudnił się jako pomocnik kafelkarza. Praca ciężka, ale nieźle płatna. Szczególnie, że majster, u którego Adam pracuje, kafelkuje zazwyczaj łazienki u artystów.

Jak wiadomo artyści mają swoje wymagania. Każdy artysta ma ulubiony zestaw wzorów: każdy kafelek musi być w jednym z tych wzorów. Poza tym każdy artysta ma kombinacje wzorów, których zwyczajnie nie jest w stanie znieść. Przed złożeniem zamówienia wyraźnie artysta mówi kafelkarzowi, które kwadraty 2 na 2 wchodzą w grę.

Artyści lubią mieć wkład w projektowanie układu kafelków. Dlatego sami ustalają kawałek pierwszego (najwyższego) rzędu. Poza tym, zgodnie z najnowszą modą, w dolnym rzędzie ma być dokładnie jeden kafelek w kolorze świeżej śliwki. Szef Adama pracuje tylko u zamożnych artystów. Rozmiar łazienki nie gra dla nich roli - może ona być dowolnie duża.

Przykładowe wymagania pewnego artysty. Dozwolone kafelki to: czarny kafelek, biały kafelek i kafelek w kolorze świeżej śliwki. Kawałek najwyższego rzędu, który artysta ustalił samemu to: biały, czarny, czarny. Poniżej są cztery dozwolone kwadraty . Po prawej dwa przykładowe ułożenia ściany. Wyższe jest poprawne. Niższe jest niepoprawne: artysta nie dopuszcza układu takiego, jak cztery zaznaczone kafelki.

Szef Adama ma dużo zamówień. Wydaje mu się jednak, że nie wszystkie da się zrealizować. Niektórym artystom tak się poprzewracało w głowach, że dobrali dozwolone kwadraty w ten sposób, że zwyczajnie nie da się ich ułożyć na ścianie!

Młody, ty coś wiesz o komputerach - powiedział kiedyś, podczas pracy, szef do Adama - dlatego napiszesz mi program, który będzie sprawdzał, czy wymagania klienta w ogóle pozwalają wykafelkować jakąś ścianę.

Tak właściwie ze zdaniem szefa nie powinno się dyskutować. Ale czy Adam miał w ogóle szansę wykonać swoje zadanie? Okazuje się, że nie! Jak to pokazać? W ten celu trzeba właśnie zbudować matematyczny opis komputera.