Od programowania do kafelkowania (i z powrotem)

16.10.2009 - Krzysztof Dryś
TrudnośćTrudnośćTrudność

Pierwsza część dowodu

Spróbujmy przeprowadzić pierwszą część dowodu. Załóżmy, że zakodowana maszyna zatrzymuje się na podanym wejściu w $ n $ krokach. Oznacza to, że głowica nie mogła pójść w prawo dalej niż $ n $ kroków. Tak więc maszyna korzysta tylko z pierwszych $ n $ pól taśmy! Oznacza to, że można zbudować ścianę o rozmiarze $ n \times n $. 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.

Uwaga! To nie jest zupełnie ścisły dowód. Pewnie trzeba by dopracować parę szczegółów. Ale my chcemy zobaczyć sendo problemu, a nie brnąć w szczegóły dowodu!

Druga część dowodu

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.

Nareszcie koniec dowodu!

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
Przed chwilą dowiedliśmy, że każdą Maszynę Turinga $ M $ oraz liczbę $ l $ da się zakodować jako zestaw reguł kafelkowych. Reguły te pozwalają na zbudowanie ściany wtedy i tylko wtedy, gdy maszyna $ M $ zatrzymuje się, gdy jej wejściem jest liczba $ l $. Oznacza to, że powyższy algorytm sprawdza, czy maszyna $ M $ zatrzyma się, gdy jej wejściem jest liczba $ l $.

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ę.

4.6
Twoja ocena: Brak Ocena: 4.6 (5 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com