Problem ograniczonego zatrzymania jest rozstrzygalny. Dlaczego ten konflikt z twierdzeniem Rice'a?

Jedno stwierdzenie twierdzenia Rice'a znajduje się na stronie 35 „Złożoności obliczeniowej: nowoczesne podejście” (Arora-Barak):

Funkcja częściowa od do to funkcja, która niekoniecznie jest zdefiniowana na wszystkich jej wejściach. Mówimy, że TM oblicza funkcję cząstkową jeżeli dla każdego na którym zdefiniowano , i dla każdego na którym nie zdefiniowano przechodzi w nieskończoną pętlę po wykonaniu na wejściu . Jeśli jest zbiorem funkcji częściowych, to definiujemy jako funkcję boolowską, która na wejściu wyjścia 1 iff$\{0,1\}^*$$\{0,1\}^*$$M$$f$$x$$f$$M(x) = f(x)$$x$$f$$M$$x$$S$$f_S$$\alpha$$M_\alpha$oblicza częściowy funkcję . Twierdzenie Rice'a mówi, że dla każdej niebrywalnej funkcja nie jest obliczalna.$S$$S$$f_S$

Wikipedia stwierdza, że ​​języki ograniczonych urządzeń do pomiaru czasu są WYGODNE. Oczekuję, że ten język wygląda jak akceptuje mniej niż kroków . Więc niech będzie jakimś DTM, który decyduje o tym ograniczonym języku w czasie wykładniczym. Wygląda na to, że DTM decyduje o jakiejś właściwości WSZYSTKICH maszyn Turinga, więc moja intuicja podpowiada mi, że twierdzenie Rice'a wyklucza taką decyzję. Ale oczywiście oblicza całkowitą funkcję.$\{(\alpha,x,n) : M_\alpha$$x$$n$$\}$$M$$M$

Czego mi brakuje w związku między tym językiem a twierdzeniem Rice'a?

Język

$\qquad \{(α,x,n):M_α \text{ accepts } x \text{ in less than } n \text{ steps}\}$

nie jest zestawem indeksów, to znaczy nie ma formy

$\qquad L_P = \{ \langle M \rangle \mid M \text{ is TM},\ \exists\, f \in P.\ f_M = f \}$

dla pewnego zbioru funkcji (częściowe rekurencyjne) , przy funkcję (częściowe) obliczony przez TM . Twierdzenie Rice'a zawiera stwierdzenia tylko o takim ; wiele „intuicyjnych” przeredagowań nie jest pomocnych. Zobacz także tutaj .$P$$f_M$$M$$L_P$

Pamiętaj, że nie jest to tylko szczegół techniczny. Twierdzenie Rice'a nie ma zastosowania

$\qquad L = \{ \langle M \rangle \mid M \text{ accepts } \langle M \rangle \text{ in less than } \langle M \rangle \text{ steps} \}$ ,

zarówno. Czy widzisz dlaczego?

Dla każdej maszyny w można łatwo skonstruować wiele maszyn, które akceptują ten sam język, ale pracować dłużej niż kroki, a tym samym nie są w . Zatem nie jest zestawem indeksów.$L$$\langle M \rangle$$L$$L$

$L$ jest rozstrzygalne, używając tego samego argumentu, co w przypadku oryginalnego języka, który omawiamy.

Twierdzenie Rice'a mówi, że nie można nic powiedzieć o ostatecznym zachowaniu programu, gdy jest on uruchamiany do nieskończoności - bez względu na to, jak klasyfikujesz programy, będą dwa programy, które zbiegną się do tego samego ostatecznego zachowania (funkcja obliczona ), chociaż sklasyfikowałeś je inaczej.

Ale uruchomienie programów do nieskończoności jest niezbędne. Aby dowiedzieć się, co robią w pierwszej kolejności$n$ kroki, możesz po prostu symulować je po raz pierwszy $n$kroki, a następnie zakończ wydawanie werdyktu na temat zachowania programu. Podobna symulacja do nieskończoności nie działa, ponieważ jeśli symulowany program nigdy nie zakończy działania na symulowanym wejściu, klasyfikator również się rozejdzie, zamiast podać klasyfikację.

Po pierwsze, słowa w twoim języku nie są kodowaniem maszyn, zawierają więcej informacji, więc nie możesz bezpośrednio zastosować twierdzenia Rice'a. To powiedziawszy, twierdzenie Rice'a mówi o niemożności rozumowania funkcji obliczonej przez maszynę Turinga (mianowicie, czy leży ona w jakimś zbiorze$S$). W tym przypadku tak nie jest, ponieważ, jak wspomniał Raphael, istnieją dwie maszyny$M,M'$ którzy obliczają tę samą funkcję, ale jedna leży w twoim języku, a druga nie (tutaj ignoruję problem składniowy i zapominam o tym, że $x,n$są częścią danych wejściowych). Chodzi o to, że oglądana tutaj właściwość jest mechaniczna, a nie semantyczna (maszyny mogą obliczać tę samą funkcję, ale w inny sposób).

Twierdzenie Rice'a mówi, że dla każdego nietrywialnego zestawu $\mathcal{L}$ języków, zestaw maszyn Turinga, które rozpoznają język $\mathcal{L}$jest nierozstrzygalny. Wikipedia mówi, że określony język jest rozstrzygalny. Więc nie ma sprzeczności.