Ograniczenia maszyny Turinga, które sprawiają, że zatrzymanie jest rozstrzygalne

Jeśli ograniczy się maszyny Turinga do skończonej taśmy (tj. Do zastosowania ograniczonej przestrzeni ), wówczas problem zatrzymania jest rozstrzygalny, zasadniczo dlatego, że po kilku etapach (które można obliczyć na podstawie liczby stanów i oraz rozmiar alfabetu), konfigurację należy powtórzyć.$S$$Q$$S$

Czy istnieją inne naturalne ograniczenia dotyczące maszyny Turinga, które sprawiają, że zatrzymanie jest rozstrzygalne?

Z pewnością, jeśli wykres przejścia stanu nie ma pętli ani cykli, decydujące jest zatrzymanie. Ktoś jeszcze?

Dość naturalną i przebadaną odmianą jest maszyna Turing-Reversal Bounded Turing (liczba zwojów taśmy jest ograniczona); patrz na przykład:

Juris Hartmanis: Obliczenia maszyny Turinga związane z odwracaniem taśmy. J. Comput. Syst. Sci. 2 (2): 117-135 (1968)

Edycja : [ta odmiana jest bardziej sztuczna] problem zatrzymania jest rozstrzygalny dla nieusuwalnej maszyny Turinga, która ma co najwyżej dwie instrukcje alfabetu ; patrz Maurice Margenstern: Nieustające maszyny Turinga: granica między decydującym problemem zatrzymania a uniwersalnością. Teoria Comput. Sci. 129 (2): 419–424 (1994)$\{0,1\}$

Biorąc pod uwagę, w jaki sposób przekazywanie parametrów do podprogramów i ogromna część zarządzania pamięcią w popularnych językach komputerowych opiera się na stosach, oczywistą i naturalną odmianą jest ograniczenie nieograniczonej pamięci maszyny Turinga do stosu.

Taki model ma fajne właściwości , oprócz tego, że można go rozstrzygać (dobrze znany z PDA ):

Pojęcie PDA można uogólnić na pomocniczy automat przesuwający ( -AuxPDA) . Składa się ona z$S(n)$$S(n)$

1. taśma wejściowa tylko do odczytu, otoczona znacznikami końcowymi,
2. skończona kontrola stanu,
3. taśma pamięci do odczytu i zapisu o długości , gdzie jest długością ciągu wejściowego, oraz$S(n)$$n$
4. stos

W „Hopcroft / Ullman (1979) Wprowadzenie do teorii automatów, języków i obliczeń (wydanie pierwsze) znajdujemy:

Twierdzenie 14.1 Poniższe są równoważne dla .$S(n)\geq\log n$

1. $L$ jest akceptowany przez deterministyczne -AuxPDA$S(n)$
2. $L$ jest akceptowany przez niedeterministyczną -AuxPDA$S(n)$
3. $L$ jest w dla niektórych stałych .$\operatorname{DTIME}(c^{S(n)})$$c$

z zaskakującym:

Wniosek znajduje się w wtedy i tylko wtedy, gdy jest zaakceptowane przez -AuxPDA.$L$$\mathsf P$$L$$\log n$

sformułowanie tego pytania jest nieco problematyczne, ponieważ maszyna Turinga ze skończoną taśmą jest prawdopodobnie mało związana z maszyną Turinga i bliżej / zasadniczo do maszyny skończonej. podobnie jak w przypadku wszystkich innych „ograniczeń” na maszynach Turinga, prawie każde ograniczenie wydaje się być zupełnie innym zjawiskiem (tj. innym niż kompletność Turinga o zupełnie innych właściwościach). w rzeczywistości niektóre artykuły wzywają teraz / szczegółowo badają tę granicę i może mieć pewne przybliżone podobieństwo z inną znaną granicą obliczeniową, tj. całkowitymi przejściami faz NP.

a jego nieco sprzeczne z intuicją to, że teoria FSM „prostsza obliczeniowo / w pełni rozstrzygalna” pojawiła się długo po wynalezieniu maszyny Turinga, prawdopodobnie nieco niejasno zainspirowana. więc może jednym ze sposobów na przeformułowanie jest poproszenie o „najbardziej wyrafinowane rozstrzygalne modele obliczeń” lub „badanie granicy między niezdecydowanymi a rozstrzygalnymi modelami obliczeniowymi”.

więc i tak nieco przeformułowany w ten sposób, rozsądny program odpowiedzi / teorii / badań, który nie został jeszcze wymieniony, to obecnie znacznie rozwinięta i aktywnie badana / rozwijająca się teoria automatów czasowych, która właśnie wygrała nagrodę kościelną dla Alur / Dill. Oto przykład artykułu na temat automatów czasowych i badania granicy modelu (nie) rozstrzygalności modelu obliczeniowego. W tym duchu jest wiele innych.

• Zdolność rozstrzygania i złożoność automatów czasowych za pośrednictwem Channel Machines / Abdulla, Deneux, Worrell

• Nagroda Kościoła Alonzo 2016, Timed Automata, Alur / Dill

• Teoria automatów czasowych / Alur, Dill

• Wywiad z Rajeevem Alurem i Davidem Dillem, laureatami nagrody Alonzo Church Award 2016 / Aceto, Process Algebra Diary