Czy każdy język rekurencyjny jest rozpoznawany przez śmiertelną maszynę Turinga?

Mówimy, że maszyna Turinga jest śmiertelna, jeśli zatrzymuje się przy każdej początkowej konfiguracji (w szczególności zawartość taśmy i stan początkowy mogą być dowolne). Czy każdy język rekurencyjny jest rozpoznawany przez śmiertelną Maszynę Turinga? (tzn. jeśli istnieje baza TM, która akceptuje , istnieje również śmiertelna baza TM, która akceptuje ) $M$ $M$ $L$ $L$

computability Marcin Kotowski
źródło

Czy możesz podać odniesienia do Mortal Turing Machines? Dzięki :)

Tayfun Zapłać

Jak to możliwe, że stan początkowy może być dowolny? Czy śmiertelna maszyna Turinga nie jest TM, która zatrzymuje się przy każdym wejściu?

Philip White

@Marcin: czy interesują Cię maszyny, które zatrzymują się we wszystkich konfiguracjach, w tym nieskończonych, czy tylko te, które zatrzymują się we wszystkich konfiguracjach skończonych ?

Joshua Grochow

Myślę, że ma na myśli skończone konfiguracje początkowe. Dobrze?

Philip White

@Philip: Wyobraź sobie maszynę w dowolnym stanie i konfiguracji, a następnie uruchom obliczenia od tego momentu zgodnie ze zwykłymi regułami.

Joshua Grochow

Odpowiedzi:

Oto dwa wyniki cytowane w Charles E. Hughes „Nierozstrzygalność skończonej zbieżności dla konkatenacji, wstawiania i ograniczonych tasowania operatorów” :

Twierdzenie 3 : Klasa śmiertelnych maszyn Turinga jest dokładnie klasą maszyn Turinga o stałym czasie pracy.

st wszystkich początkowych konfiguracji, , zatrzymanie w ciągu nie więcej niż etapów $ConstT = \{ M \mid \exists s$ $C$ $M$ $s$ $\}$

Więc myślę, że możemy czerpać następujące: podany śmiertelny maszyna Turinga , niech mieć odpowiedni czas na stałym TM i jej czas pracy. Język rozpoznawany przez alfabetu to dokładnie: $M$ $M', s$ $M$ $\Sigma = \{0,1\}$

{x y ∣ | x | \leq s \land M^{'} accepts x in no more than s steps, y \in {0, 1}^{*}}

$\{ xy \mid |x| \leq s \land M' \text{ accepts } x \text{ in no more than s steps}, y \in \{0,1\}^* \}$

Zatem klasa języków rozpoznawana przez śmiertelne maszyny Turinga jest odpowiednim podzbiorem klasy zwykłych języków. Na przykład możesz użyć aby oszukać za każdym razem TM. $L = \{(0|1)^*1^*\}$

Sprawy stają się interesujące, gdy próbujemy zdecydować, czy maszyna Turinga jest śmiertelna, ponieważ musimy zmierzyć się z dowolną (skończoną) początkową taśmą i stanem.

Twierdzenie 4 : zbiór śmiertelnych maszyn Turinga jest rekurencyjnie wyliczalny.

Marzio De Biasi
źródło

Myślę, że jest. Musimy wykonać dla każdego L an M, który to zaakceptuje, w taki sposób, aby wszystkie jego ruchy były rejestrowane na taśmie i po każdym „głównym kroku” sprawdza, czy wszystkie jego kroki do tego momentu były naprawdę prawidłowe. Poniżej daję szkic, jak taka maszyna powinna być wykonana (która może zawierać drobne błędy, ale główny pomysł powinien być w porządku).

Oznacz maszynę, która akceptuje L przez T. Teraz opisujemy M. Najpierw kopiujemy x na osobnej taśmie pamięci. Następnie, gdy T wykona ruch, zapisujemy go na taśmie pamięci, po x. Następnie kopiujemy całą zawartość taśm T na dodatkowe taśmy robocze i sprawdzamy, czy od konfiguracji początkowej T naprawdę przejdzie do obecnego stanu po krokach zapisanych na taśmie pamięci. Jeśli nie, zatrzymamy się. Jeśli tak, kontynuujemy.

domotorp
źródło

pisząc moją odpowiedź, czytam twoją ... która mówi coś przeciwnego :-) ... być może źle interpretuję ciąg znaków akceptowany przez śmiertelną maszynę Turinga?

Marzio De Biasi,

@MarzioDeBiasi: Pojęcie śmiertelnika rozważane w tym artykule wymaga zatrzymania maszyny w skończonej liczbie kroków, nawet jeśli zostanie uruchomiona z nieskończoną ilością dowolnych danych na taśmie. Ale myślę, że konstrukcja domotorp co najwyżej działa dla konfiguracji skończonych. Na przykład w konfiguracji z wejściem o nieskończonej długości M domotorp zostaje złapany w nieskończoną sekwencję kopiowania danych o nieskończonej długości na osobną taśmę pamięci ...

Joshua Grochow

Tak, różnica polega na tym, że przypuszczałem, że każda zawartość taśmy jest skończona i wiemy, gdzie są granice. W przeciwnym razie śmiertelne TM są po prostu stałe, jak piszesz.

domotorp