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:

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

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))$

— Kaveh
źródło

Czy liczba taśm powinna być taka sama, czy jakoś ograniczona?

— Raphael

Na jednej taśmie można symulować wiele taśm w czasie kwadratowym, więc jeśli tego rodzaju symulacja jest sprawiedliwa, dlaczego oczekujesz różnicy? A może czas symulacji liniowej jest sprawiedliwy z innych powodów?

— Raphael

„Pytam, czy można przeprowadzić symulację z liniowym obciążeniem” - nie mogę dopasować tego do pytania. Miałeś na myśli ?

o (f (n))

$o(f(n))$

— Raphael

@ Rafael, sprawdziłem to ponownie i zaktualizowałem pytanie. jest poprawna, to nuta jest dowolna czynność w . (w twierdzeniu potrzebujemy czegoś rosnącego szybciej niż ponieważ alfabet i liczba stanów symulowanej maszyny nie są stałe, więc istnieje stała zależna od maszyny. jest używana przez nich.)

ω

$\omega$

g

$g$

ω (f (n))

$\omega(f(n))$

f (n) \lg f (n)

$f(n) \lg f(n)$

ω

$\omega$

— Kaveh

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 na DTM z pojedynczą taśmą, ale można je rozwiązać w czasie 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 jest w zamiast ? $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 nie jest potrzebny. Zobacz także (4). $n$ $\lg$

Bibliografia:

Peter van Emde Boas, „Modele maszyn i symulacja”, w Handbook of Theoretical Computer Science, 1990
(w szczególności s. 18–21)
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)
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)
Piergiorgio Odifreddi, „Klasyczna teoria rekurencji”, vol. II, 1999
(strona 84)
Martin Fürer, „ Tight Deterministic Time Hierarchy ”, 1982
Juris Hartmanis, „ Złożoność obliczeniowa obliczeń na jednej taśmie Turinga ”, 1968
FC Hennie i RE Stearns, „ Two-Tape Simulation of Multitape Turing Machines ”, 1966
Inne powiązane pytania:

— Kaveh
źródło

Nadal jest kilka rzeczy, które wciąż nie są dla mnie całkowicie jasne, szczególnie w przypadku wersji 8.3 i symulacji pojedynczej taśmy w maszynach z jedną taśmą, w razie potrzeby zaktualizuję odpowiedź.

— Kaveh

n^{2} \leq t (n)

$n^2 \leq t(n)$

t (n)

$t(n)$