Od programowania do kafelkowania (i z powrotem)

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

Ważne twierdzenie (bez dowodu)

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.

Mówimy, że program się zapętlił, jeżeli jest w takim stanie, że nigdy nie zakończy obliczeń i nigdy nie zwróci wyniku.

Co to znaczy, że program $ A $ jest równoważny maszynie $ M $? Oznacza to, że dla każdych danych wejściowych program $ A $ zapętla się wtedy i tylko wtedy, gdy $ M $ się zapętla. Podobnie, jeżeli dla jakichś danych wejściowych maszyna $ M $ zwraca jakiś wynik, to również algorytm $ A $ zwracaca ten sam wynik.

Ważne twierdzenie (z innego artykułu)

Czytaliście artykuł o tym, czy komputery mogą wszystko? Można tam zobaczyć między innymi następuje twierdzenie:

Nie da się napisać programu, który czyta kod innego programu oraz liczbę $ l $ i mówi, czy ten program zapętli się po przeczytaniu liczby $ l $.

Twierdzenie o Maszynie Turinga

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ę $ l $, a następnie mówi, czy ta maszyna zapętli się, jeżeli jej wejściem będzie liczba $ l $.

To jak będziemy kodować, czyli pamiętać w komputerze Maszynę Turinga zupełnie nas tutaj nie obchodzi!

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ę $ l $, a następnie mówi, czy ta maszyna zapętli się, jeżeli jej wejściem będzie liczba $ l $. 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 $ A $ i maszyna $ M $ są równoważne. Oznacza to, że powyższy algorytm sprawdza, czy algorytm $ A $ zatrzyma się po przeczytaniu liczby $ l $. 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ę $ l $, a następnie mówi, czy ta maszyna zapętli się, jeżeli jej wejściem będzie liczba $ l $) 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!

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com