8299308018

1.2.2.3    Maszyny Turinga jako generatory

Ponieważ maszyny Turinga w trakcie swojej pracy zmieniają zapis na taśmie, można ich używać nie tylko do akceptowania słów, ale również do wykonywania obliczeń.

Przykład 1.14

Maszyna na rysunku obok wykonuje dodawanie 1 do liczby binarnej. Zakładamy, że oryginalna liczba, ciąg zer i jedynek, jest zapisana na taśmie, a głowica ustawiona jest na ostatniej (najmniej znaczącej) cyfrze. Maszyna zmienia ten zapis i kończy z głowicą znowu na ostatniej znaczącej cyfrze — temu służy pętelka przy stanie C oraz strzałka z C do D. Stan B oznacza, że jest jeszcze jedynka „w pamięci” (przeniesienie) do dodania do następnej cyfry.

□

Konstrukcja maszyn Turinga, wykonujących bardziej złożone obliczenia, jest żmudna, a powstałe maszyny mają sporo stanów. Proponuję czytelnikowi skonstruowanie maszyny dodającej dwie liczby. Proszę nie dziwić się, że będzie potrzeba wielu komend, których jedyną rolą będzie przenoszenie informacji z jednego miejsca taśmy w inne.

1.2.2.4    Znaczenie maszyn Turinga

Okazuje się, że maszyny Turinga, mimo swojej prostoty pojęciowej, potrafią policzyć wszystko, co w ogóle może zostać policzone. Stanowi to treść t.zw. „tezy Churcha-Turinga”:

Teza 1.15

Dla każdej funkcji f, której wartości dają się efektywnie obliczać dowolnymi sposobami, istnieje maszyna Turinga obliczająca f.

Ta teza oczywiście nie jest twierdzeniem i nie daje się dowieść, bo nie posiadamy żadnej ogólnej definicji „liczenia” niezależnej od pojęcia maszyny Turinga oraz od innych mechanizmów jej równoważnych. Jest to raczej teza filozoficzna, poparta tym, że jak dotąd nikomu nie udało się wymyślić żadnego przykładu czegoś, co sensownie można by nazwać obliczaniem, co nie byłoby wykonalne na jakiejś maszynie Turinga.

W szczególności wszystko, co daje się zaprogramować w dowolnym języku na komputer o dowolnej architekturze, daje się również policzyć przy pomocy jakiejś maszyny Turinga. Zachodzi też zależność odwrotna: jeśli abstrahować od skończoności pamięci komputerów, to każdy imperatywny język programowania¹ ogólnego zastosowania, taki jak Pascal, C lub Java, ma pełną moc maszyn Turinga. Natomiast niekoniecznie mają ją języki wąsko specjalizowane, takie jak HTML (język opisu witryn internetowych) lub SQL (język zapytań baz danych).

Znaczenie poznawcze maszyn Turinga wynika z tego, że

• stanowią one uniwersalny model obliczeń, oraz

11

1

Większość języków programowania komputerów to języki imperatywne. O nieimperatywnych językach programowania będzie jeszcze wzmianka w rozdz. 1.2.3.