8299308019

• są koncepcyjnie proste, znacznie prostsze niż istniejące języki programowania, czy architektury istniejących komputerów.

Dlatego każdy nowy model obliczeń zwyczajowo porównujemy z maszynami Turinga. Jeśli okaże się, że potrafi on zasymulować każdą maszynę Turinga, to uważamy, że lepiej już być nie może.

Definicja 1.16

Każdy model obliczeń, równoważny maszynom Turinga, nazywamy zupełnym w sensie Turinga.

Oczywiście automaty skończone nie są zupełne w sensie Turinga.

1.2.2.5 Rozstrzygalność problemów i obliczalność funkcji

Łatwo sprawdzić, że różnych maszyn Turinga jest Ho, czyli tyle, co liczb naturalnych.

Z drugiej strony, dla niepustego i skończonego alfabetu E, zbiór E* wszystkich słów nad tym alfabetem ma moc Ho, a języków zawierających te słowa jest 2^H° = c, czyli continuum, to znaczy znacznie więcej niż maszyn Turinga. Tak więc nie każdy język posiada rozpoznającą go maszynę; i nie do każdego można skonstruować rozpoznający go program komputerowy. Każdy t.zw. problem decyzyjny, czyli pytanie, na które maszyna (lub komputer) miałyby odpowiedzieć „tak” lub „nie”, daje się sprowadzić do sprawdzenia należenia słów do pewnego języka¹. Różnica między mocą zbioru języków oraz mocą zbioru maszyn Turinga określa granicę możliwości komputerów: zawsze będą one potrafiły odpowiedzieć tylko na Ho pytań, czyli na niewielką część tego, czego nie wiadomo.

Podobnie ma się sprawa z obliczaniem wartości funkcji. Wszystkich funkcji z N do N jest Hq° = c, czyli znowu continuum. Wobec tego daleko nie wszystkie funkcje dadzą się zaprogramować za pomocą maszyny Turinga; w związku z tym również nie dadzą się zaprogramować w żadnym języku na żadnym komputerze.

Tych nierozstrzygalnych problemów i nieobliczalnych funkcji jest znacznie więcej niż roz-strzygalnych i obliczalnych, jednak wskazanie konkretnego takiego problemu lub funkcji nie jest proste. Poniżej podany jest szkic konstrukcji ważnego problemu nierozstrzygalnego.

Definicja 1.17

Problem C (równoważnie: podzbiór C CE*) nazywamy rozstrzygalnym jeśli istnieje maszyna Turinga M, taka że C = L(M). Analogicznie, funkcję nazywamy obliczalną lub reku-rencyjną, jeśli istnieje obliczająca ją maszyna Turinga.

Twierdzenie 1.18

Problem stopu maszyny Turinga, to znaczy problem, czy dana maszyna Turinga M kończy obliczenie dla danego słowa w G E* na taśmie, jest nierozstrzygalny. T.zn. nie istnieje maszyna Turinga S, która potrafiłaby zbadać dowolną maszynę Turinga M oraz dowolne dane w (obie rzeczy jakoś zakodowane na taśmie wejściowej dla S), zatrzymać się i poprawnie odpowiedzieć na pytanie, czy M zatrzymuje się na w.

12

1

Terminy język rekurencyjny oraz problem rozstrzygalny są synonimami. Oba oznaczają akceptację przez jakąś maszynę Turinga zarówno każdego słowa z języka (instancji problemu dla konkretnych danych), jak jego dopełnienia (zaprzeczenia).