Wariant funkcji bobra zajętego

Po przeczytaniu tego pytania „ Naturalne problemy RE nierozstrzygalne, ale nie pełne Turinga ” przyszedł mi do głowy następujący język:

Jeśli jest funkcją bobra zajętego (maksymalny osiągalny wynik wśród wszystkich zatrzymujących 2-symbolowych maszyn Turinga n-stanu opisanego powyżej typu, gdy jest uruchamiany na czystej taśmie), zdefiniuj funkcję: $\Sigma(\cdot)$

B B (⟨ M ⟩) = {\begin{cases} 1 & ⟨ M ⟩ computes Σ (\cdot) \\ 0 & otherwise \end{cases}

$BB(\langle M \rangle) = \begin{cases} 1 & \text{$\langle M \rangle$ computes $\Sigma(\cdot)$}\\ 0 & \text{ otherwise} \end{cases}$

Teraz zdefiniuj język:

$L = \{ \langle M \rangle \; | \; \langle M \rangle \mbox{ halts and } BB(\langle M \rangle) = 0 \}$

Czy rekurencyjnie wyliczalny? (powinno być ponownie: po prostu symuluj równolegle M ze wszystkimi bazami TM tej samej długości, a jeśli zatrzymuje się i kolejne zatrzymuje się z wyższym wynikiem, dodaj M do wyliczenia). $L$ $M$ $M'$

Czy możemy zredukować problem zatrzymania do ? (wydaje się, że nie jest w stanie „uchwycić” zatrzymania zajętych bobrów) $L$

computability turing-machines Vor
źródło

Czyliczba stanów?

| ⟨ M ⟩ |

$|\langle M \rangle|$

Pål GD

Kiedy policzysz literę , która nie zatrzymuje się na ? nie może być RE, chyba że wyliczysz wszystkich jego członków, a procedura, którą opisałeś, wylicza tylko tych, którzy faktycznie się zatrzymali.

M

$M$

L

$L$

L

$L$

Steven Stadnicki

@ PålGD: tak, jest to liczba stanów (bez stanu wstrzymania)

Vor

@StevenStadnicki: Domyślnie założyłem, że zawiera tylko maszyny, które zatrzymują się ... być może powinienem to wyjaśnić w pytaniu (pozwól mi trochę o tym pomyśleć, być może pytanie to będzie trywialne).

L

$L$

Vor

@Kaveh Nie jest to nawet obietnica - możesz po prostu zdefiniować (jak wierzę, że OP zamierzał) jako .

L

$L$

L = {⟨ M ⟩ | M halts \land B B (⟨ M ⟩) = 0}

$L=\{\langle M\rangle | M\ \text{halts} \wedge BB(\langle M\rangle) = 0\}$

Steven Stadnicki

Odpowiedzi:

Nie mogę uwierzyć, że nie widziałem tego wcześniej - ale tak, z wyrocznią dla możesz rozwiązać problem zatrzymania. Oczywiście wyrocznia dla daje nam „rekurencyjnie” wszystkie maszyny zatrzymujące bobry nie zajęte , więc pytanie brzmi „czy możemy rekurencyjnie dowiedzieć się w jakie są zajęte bobry?”. Zdefiniuj jako funkcję zliczania „drugiego najbardziej ruchliwego bobra”; to jest drugi najwyższy możliwy do uzyskania wynik spośród wszystkich zatrzymujących dwumaganiowe TM stanowych TM. Sztuczka polega na tym, że istnieje funkcja rekurencyjna taka, że (jest prawie pewne, że $L$ $L$ $L$ $\Sigma_2(n)$ $n$ $f()$ $\Sigma(n)\leq\Sigma_2(f(n))$ $f(n)=n+1$ załatwi sprawę, ale to wymaga wiedzy, że funkcja BB ściśle się zwiększa): biorąc pod uwagę maszynę o rozmiarze która drukuje 1 na swojej taśmie, a następnie zatrzymuje się, jest trochę i dwie maszyny o rozmiarze które drukują dokładnie 1s i dokładnie 1s odpowiednio na swoich taśmach - i dotyczy to maszyny „zajętej bobra” nawet jeśli nie nie znam wprost . Oznacza to, że ograniczenie dla funkcji „drugi zajęty bóbr” dla daje ograniczenie dla funkcji zajętego bobra na $M$ $n$ $\Sigma(M)$ $c\gt 1$ $\leq cn$ $\Sigma(M)$ $\Sigma(M)+1$ $M$ $M$ $f(n)$ $n$ ; ale mając to, łatwo jest rozwiązać problem zatrzymania dla TM o rozmiarze - jeśli to powiedz, że zatrzymuje się; w przeciwnym razie znajdź najdłużej działającą maszynę o rozmiarze w (co można zrobić rekurencyjnie, ponieważ istnieje tylko skończona liczba maszyn o rozmiarze ) i symuluj na tyle kroków, ile potrzeba, aby ta maszyna postój. Jeśli nie zatrzyma się w tym czasie, prawdopodobnie nie może się zatrzymać. $M$ $n$ $\langle M\rangle\in L$ $M$ $f(n)$ $L$ $\leq f(n)$ $M$ $M$ $M$

Steven Stadnicki
źródło

Dzięki; zainspirowany twoją odpowiedzią znalazłem szybką (trywialną) -: bezpośrednią redukcję problemu zatrzymania w osobnej odpowiedzi.

Vor

To jest przerobiona wersja dobrej odpowiedzi Stevena, z wyraźnym zmniejszeniem problemu Halting.

Biorąc pod uwagę build który uruchamia na a jeśli się zatrzyma, idzie na prawo od taśmy, zapisuje 0 i zatrzymuje. $\langle M \rangle, w$ $M'$ $M$ $w$

Jeśli zatrzymuje się, ponieważ istnieje odpowiednik TM o tym samym rozmiarze, który zapisuje 1 i zatrzymuje się; więc możemy użyć decydatora dla aby sprawdzić, czy zatrzymuje się ( zatrzymuje się iff ) $M'$ $BB(M')=0$ $L$ $M$ $w$ $M$ $w$ $M' \in L$

... okazało się, że pytanie jest rzeczywiście banalne :-)

Vor
źródło