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

33

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ć.SQS

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?

Joseph O'Rourke
źródło
1
Możesz również rozważyć TM, które można udowodnić jako całkowite, powiedzmy PA, ZFC, ...
Kaveh
@Kaveh: Czy można to sformułować jako ograniczenie zachowania TM w jakimś prawie fizycznym sensie?
Joseph O'Rourke
Nie, nie sądzę.
Kaveh
1
Problem decyzyjny na maszynie z pojedynczym rejestrem (z instrukcjami bezwarunkowego inkrementacji i skoku, jeśli-zero-to-skoku-w innym przypadku dekrementacji-i-skoku i zatrzymania) jest rozstrzygalny.
wchargin
AFAIK Problem zatrzymania maszyn Turinga z ograniczoną przestrzenią S nie jest rozstrzygany przez maszyny Turinga ograniczone do przestrzeni S.
Taemyr

Odpowiedzi:

30

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}

Marzio De Biasi
źródło
Ograniczenie odwrócenia taśmy jest rzeczywiście całkiem naturalne. Dzięki!
Joseph O'Rourke
18

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 zS(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, orazS(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)logn

  1. L jest akceptowany przez deterministyczne -AuxPDAS(n)
  2. L jest akceptowany przez niedeterministyczną -AuxPDAS(n)
  3. L jest w dla niektórych stałych .DTIME(cS(n))c

z zaskakującym:

Wniosek znajduje się w wtedy i tylko wtedy, gdy jest zaakceptowane przez -AuxPDA.LPLlogn

Thomas Klimpel
źródło
Dzięki, Thomas, jest to również naturalne ograniczenie.
Joseph O'Rourke
3

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.

vzn
źródło
przypadkiem pytanie wydaje się dość koncepcyjnie podobne do tego, które niedawno zadano w informatyce : Jakie są najbardziej ekspresyjne, kończące języki?
vzn
1
Dzięki za linki do automatów czasowych , których koncepcji nie znałem.
Joseph O'Rourke
btw, przemyślenie / uzupełnienie: jeden aspekt znanej teorii, który dąży / wydaje się naciskać na jakikolwiek „naturalny, rozstrzygalny relaks” istniejącej TM, Rices thm . jednak innym naturalnym pov / pomysłem przywołanym nieco w innych odpowiedziach jest to, że cała hierarchia czasu / przestrzeni i klasy złożoności są „naturalnymi”, rozstrzygalnymi wersjami baz TM.
vzn
Maszyna stanów skończonych może być zbyt daleko od maszyny Turinga, aby mówić o ograniczeniach, ale ograniczona maszyna Turinga, która mogłaby obliczyć wszystkie prymitywne funkcje rekurencyjne, byłaby wystarczająco blisko, aby można było zasadnie powiedzieć, że jest to ograniczony model maszyny Turinga.
Thomas Klimpel