Od programowania do kafelkowania (i z powrotem)
16.10.2009 - Krzysztof Dryś
Pierwsza część dowoduSpró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. Druga część dowoduPodobnie 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:
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ę. (5 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com