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ć.
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?
turing-machines
decidability
Joseph O'Rourke
źródło
źródło
Odpowiedzi:
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)
źródło
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 ):
źródło
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
źródło