Uniwersalna symulacja maszyn Turinga

Niech będzie stałą funkcją konstruowaną w czasie.$f$

Klasyczny uniwersalny wynik symulacji dla TM (Hennie i Stearns, 1966) stwierdza, że ​​istnieje TM z dwiema taśmami, taka$U$

• opis TM i$\langle M \rangle$
• ciąg wejściowy ,$x$

uruchamia kroki i zwraca odpowiedź na . I może być dowolną funkcją w .$g(|x|)$$M$$x$$g$$\omega(f(n)\lg f(n))$

Moje pytania to:

1. Jaki jest najbardziej znany wynik symulacji na jednej taśmie TM? Czy powyższy wynik również nadal obowiązuje?

2. Czy jest jakaś poprawa w [HS66]? Czy możemy symulować bazy TM na dwóch taśmach dla kroków w szybszy sposób? Czy możemy wziąć do zamiast ?$f(n)$$g(n)$$\omega(f(n))$$\omega(f(n)\lg f(n))$

Jaki jest najbardziej znany wynik symulacji na jednej taśmie TM? Czy powyższy wynik również nadal obowiązuje?

Możemy symulować TM z wieloma taśmami na TM z jedną taśmą z kwadratowym wydłużeniem czasu. Czas symulacji wynosi . Kwadratyczny wzrost jest wymagany, ponieważ istnieją języki (np. Palindromy), które wymagają czasu Ω ( n 2 ) na DTM z pojedynczą taśmą, ale można je rozwiązać w czasie O ( n ) na DTM z dwiema taśmami.$O(n^2)$$\Omega(n^2)$$O(n)$

Krótko mówiąc, powyższy wynik nie działa, gdy symulator jest TM z jedną taśmą.

W przypadku symulacji TM z pojedynczą taśmą na TM z pojedynczą taśmą (z dowolnym skończonym alfabetem) wynik jest zachowany, tj. Symulacja może być wykonana ze wzrostem współczynnika w czasie. Zobacz (2) i (3). Odniesieniem wydaje się być (6).$\lg$

Czy jest jakaś poprawa w [HS66]? Czy możemy symulować bazy TM na dwóch taśmach dla kroków w szybszy sposób? Czy możemy przyjąć, że g ( n ) jest w ω ( f ( n ) ) zamiast ω ( f ( n ) lg f ( n ) ) ?$f(n)$$g(n)$$\omega(f(n))$$\omega(f(n)\lg f(n))$

Wydaje się, że nie nastąpiła żadna poprawa, ponieważ oznaczałoby to lepsze twierdzenie o hierarchii czasu niż obecnie znane.

Korekta: Zwykłe twierdzenia dotyczące hierarchii opierają się na klasach złożoności czasu zdefiniowanych za pomocą pojedynczych taśm TM. W przypadku baz TM typu ścisły wynik podobny do twierdzenia o hierarchii przestrzeni został udowodniony przez Furera w 1982 r. (5). Współczynnik lg nie jest potrzebny. Zobacz także (4).$n$$\lg$

Bibliografia:

1. Peter van Emde Boas, „Modele maszyn i symulacja”, w Handbook of Theoretical Computer Science, 1990
   (w szczególności s. 18–21)

2. Michael Sipser, „Wprowadzenie do teorii obliczeń”, 2006
   (klasy złożoności czasowej są definiowane przy użyciu baz TM z pojedynczą taśmą nieskończoną w obu kierunkach i dowolnym skończonym alfabetem, patrz strony 140 i 341)

3. Odifreddi, „Classical Recursion Theory”, vol. I i II, 1989 i 1999
   (definicje są podobne do Sipsera, patrz Def. I.4.1 w tomie I strona 48, Def. VII.4.1 w tomie II strona 67 i Thm. VII.4.15 w tomie II strona 83)

4. Piergiorgio Odifreddi, „Klasyczna teoria rekurencji”, vol. II, 1999
   (strona 84)

5. Martin Fürer, „ Tight Deterministic Time Hierarchy ”, 1982

6. Juris Hartmanis, „ Złożoność obliczeniowa obliczeń na jednej taśmie Turinga ”, 1968

7. FC Hennie i RE Stearns, „ Two-Tape Simulation of Multitape Turing Machines ”, 1966

8. Inne powiązane pytania:

   1. Dolne granice i separacja klas ,
   2. Uzasadnienie w DTIME hierarchia twierdzenie$\lg f$ ,
   3. Alfabet maszyny Turinga z pojedynczą taśmą ,
   4. W przypadku twierdzenia o hierarchii czasu, w jaki sposób dane wejściowe są skutecznie tłumaczone? ,
   5. komentarz Luca Trevisana.