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.
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.
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.
Potrzeba nam ścisłego opisu komputerów. Jak go stworzyć? Można powiedzieć: komputer, to to co stoi na moim biurku. To zdanie dokładnie definiuje komputer. Ale ma jedną wadę. Jaką? Maszyna, która stoi obok mnie, jest bardzo skomplikowana. Ma w sobie tysiące obwodów i układów. Dlatego bardzo trudno czegoś o niej dowieść.
Jak działa zwyczajny komputer? Możemy wyobrażać sobie, że komputer składa się programu, procesora i pamięci. Pamięć jest podzielona na komórki - w każdej z nich zapisana jest jakaś liczba. W kolejnych turach procesor wykonuje rozkazy zapisane w programie. Od czasu do czasu pisze do pamięci i z niej czyta.
Ten opis zaczyna się robić coraz prostszy, prawda? Jednak chcemy opisać komputer jeszcze ściślej i jeszcze prościej.
Maszyna Turinga jest wzorowana na starszych komputerach. Dlatego zamiast procesora będziemy mieli głowicę. A zamiast pamięci - taśmę.
Taśma Maszyny Turinga jest nieskończona (uwaga, to ważne!) i podzielona na komórki. W każdej komórce znajduje się jeden z symboli: , , lub . Symbol występuje na taśmie dokładnie raz - na pierwszym jej polu. Symbol oznacza pustą komórkę - taką w której jeszcze nic nie zostało zapisane.
Głowica Maszyny Turinga służy do pisania na taśmę i czytania z niej. Głowica ma różne stany. Każdy stan ma swoją nazwę. Zbiór wszystkich stanów głowicy nazywamy . Każda maszyna ma jeden stan końcowy .
Praca maszyny Turinga jest podzielona na tury. Na początku każdej tury głowica czyta symbol nad którym się znajduje. Następnie, na podstawie swojego aktualnego stanu i przeczytanego właśnie symbolu podejmuje trzy decyzje:
Maszyna Turinga musi stosować się do paru zakazów. Między innymi nie wolno jej napisać (ani zamazać!) symbolu . Gdy przeczyta symbol nie wolno jej pójść w lewo. Te reguły wynikają ze zdroworozsądkowego przekonania, że niedobrze by było, gdyby głowica wypadła z taśmy.
I jeszcze na koniec ostatnie już definicje. Stan taśmy Maszyna Turinga na początku obliczeń nazywamy wejściem. Stan taśmy Maszyna Turinga na koniec obliczeń (po przejściu w stan końcowy) nazywamy wyjściem. Na początku obliczeń głowica znajduje się nad symbolem .
Czy Maszyna Turinga jest dobry modelem dla komputerów? Jest. Świadczy o tym następujące twierdzenie:
Dla każdego programu istnieje równoważna mu Maszyna Turinga. Dla każdej Maszyny Turinga istnieje równoważny jej program.
Co to znaczy, że program jest równoważny maszynie ? Oznacza to, że dla każdych danych wejściowych program zapętla się wtedy i tylko wtedy, gdy się zapętla. Podobnie, jeżeli dla jakichś danych wejściowych maszyna zwraca jakiś wynik, to również algorytm zwracaca ten sam wynik.
Czytaliście artykuł o tym, czy komputery mogą wszystko [2]? Można tam zobaczyć między innymi następuje twierdzenie:
Nie da się napisać programu, który czyta kod innego programu oraz liczbę i mówi, czy ten program zapętli się po przeczytaniu liczby .
Spróbujmy dowiedzieć się czegoś o Maszynie Turinga. Pokażemy następujące twierdzenie:
Nie istnieje program, który czyta na wejściu opis Maszyny Turinga oraz liczbę , a następnie mówi, czy ta maszyna zapętli się, jeżeli jej wejściem będzie liczba .
To twierdzenie mówi o nowym ograniczeniu komputerów. Do tej pory wiedzieliśmy, że nie da się sprawdzić, czy jakiś program się może się zatrzymać. Teraz zobaczymy, że nie da się również sprawdzić, czy Maszyna Turinga może się zatrzymać !
Przeprowadzimy prosty dowód nie wprost. Załóżmy, że istnieje program, który czyta na wejściu opis Maszyny Turinga oraz liczbę , a następnie mówi, czy ta maszyna zapętli się, jeżeli jej wejściem będzie liczba . Rozważmy następujący program:
1 2 3 4 5 6 7 8 | Wczytaj program A, Wczytaj liczbę l, Zbuduj Maszynę Turinga M, równoważną programowi A, Sprawdź, czy maszyna M zapętla się, jeżeli jej wejściem będzie liczba l Jeżeli tak: Zwróć TAK Jeżeli nie: Zwróć NIE |
Program i maszyna są równoważne. Oznacza to, że powyższy algorytm sprawdza, czy algorytm zatrzyma się po przeczytaniu liczby . Ale to jest niemożliwe! Osiągnęliśmy sprzeczność. Oznacza ona, że nasze pierwsze założenie (mówiące, że istnieje algorytm, który który czyta na wejściu opis Maszyny Turinga oraz liczbę , a następnie mówi, czy ta maszyna zapętli się, jeżeli jej wejściem będzie liczba ) jest nieprawdziwe!
Innymi słowy - taki algorytm nie istnieje. To twierdzenie jest ciekawe - mówi nam coś nowego o komputerach. Ale zaraz będzie jeszcze ciekawiej. Nareszcie dowiemy się czegoś o kafelkowaniu!
No nareszcie - zbudowaliśmy opis komputera. Czas spożytkować nasz trud i użyć tego opisu do pokazania czegoś naprawdę ciekawego.
Zobaczymy jak za pomocą kafelków zasymulować Maszynę Turinga. Tak właśnie! Zobaczymy jak można przeprowadzać obliczenia na kafelkach łazienkowych. Jak to możliwe? Idea będzie następująca: Kolejne rzędy kafelków będą oznaczać stan taśmy Maszyny Turinga w kolejnych krokach.
Najpierw popatrzmy na kafelki. Każdy kafelek będzie odpowiadał jednemu polu na taśmie i będzie zawierał dwie informacje:
Przełóżmy to na język kafelków. Na każdym kafelku jest wzorek. Składa się on z dwóch elementów. Dolna połowa mówi jaki symbol jest zapisany na polu, któremu odpowiada kafelek. Jeżeli nad polem nie ma głowicy, to górne pole jest puste. Jeżeli nad polem jest głowica, to na górnym polu znajduje się numer tego stanu.
Informacje o tym, co robi (tzn. jak się przemieszcza i co pisze) głowica w kolejnych stanach będziemy kodowali za pomocą dozwolonych kwadratów. Wreszcie początkowy stan maszyny będzie zakodowany jako kompozycja, której zażyczył sobie artysta na górny rząd kafelków.
Pozostaje pokazać dwie rzeczy:
Spróbujmy przeprowadzić pierwszą część dowodu. Załóżmy, że zakodowana maszyna zatrzymuje się na podanym wejściu w krokach. Oznacza to, że głowica nie mogła pójść w prawo dalej niż kroków. Tak więc maszyna korzysta tylko z pierwszych pól taśmy! Oznacza to, że można zbudować ścianę o rozmiarze . Jej kolejne rzędy będą zakodowanymi stanami taśmy w kolejnych krokach. Dzięki odpowiedniemu doborowi reguł wiemy, że na takiej ścianie będą same poprawne kwadraty. W ostatnim rzędzie, zgodnie z panującą modą, znajdzie się kafelek w kolorze świeżej śliwki, który koduje stan końcowym.
Podobnie przebiegnie druga cześć dowodu. Załóżmy, że ścianę da się wykafelkować. Jako że dozwolone kwadraty wybraliśmy tak, by symulować Maszynę Turinga, to kolejne rzędy kodują stan taśmy w kolejnych krokach. W ostatnim rzędzie znajduje się kafelek kodujący stan końcowy. Oznacza to, że na ścianie zakodowane są całe obliczenia - w ostatnim kroku maszyna jest już w stanie końcowym.
Pamiętacie, że jesteśmy w trakcie dowodu nie wprost? Dowód zaczął się od założenia, że istnieje algorytm, który czyta wymagania klienta i mówi, czy da się dozwolone kwadraty ułożyć w ścianę. Wykorzystajmy to do zbudowania następującego algorytmu:
1 2 3 4 5 6 7 | Wczytaj opis Maszyny Turinga M Wczytaj liczbę l Zbuduj zestaw "reguł kafelkowych" równoważnych uruchomieniu M na l Jeżeli reguły pozwalają na zbudowanie ściany: Odpowiedz TAK Jeżeli reguły nie pozwalają na zbudowanie ściany: Odpowiedz NIE |
Ale przecież to jest niemożliwe! Pokazaliśmy wcześniej, że taki algorytm nie istnieje! Osiągnęliśmy sprzeczność! Oznacza ona, że nie istnieje algorytm, który czyta wymagania klienta i mówi, czy da się dozwolone kwadraty ułożyć w ścianę.
Co tu się właściwie wydarzyło? Postawiliśmy proste, wydawałoby się, zadanie. Należy określić czy da się wykafelkować ścianę w taki sposób, by kafelki spełniały parę prostych zasad. Co się okazało? Zobaczyliśmy, że komputer nie może sobie poradzić z tym zadaniem!
Jest tak dlatego, że za pomocą kafelków można symulować Maszyne Turinga. Ta natomiast jest równoważna naszym komputerom. Oznacza to, że na kafelkach można symulować obliczenia komputerowe. Innymi słowy: można tak dobrać reguły by z kafelków dało się ułożyć ścianę wtedy i tylko wtedy, gdy Maszyna Turinga (albo odpowiadający mu program) zatrzyma się.
Zobaczyliśmy problem który, chociaż wydaje się zwyczajny, jest nierozwiązywalny na komputerze. I to niezależnie od możliwości sprzętowych, dostępnego czasu i umiejętności programistycznych. Trudność tego problemu wyniknęła z tego można za jego pomocą symulować zachowanie komputera.
Dlatego następnym razem, zanim zabierzecie się za rozwiązywanie problemu przy pomocy komputera, zastanówcie się najpierw, czy jest w ogóle możliwe!
Odnośniki:
[1] http://informatyka.wroc.pl/node/213
[2] http://informatyka.wroc.pl/node/192