Alfabet maszyny Turinga z pojedynczą taśmą

Czy każda funkcja która jest obliczalna w czasie na maszynie Turinga z pojedynczą taśmą, używając alfabetu wielkości być obliczona w czasie na single-taśma maszyna Turinga za pomocą alfabetu wielkości (powiedzmy, i puste)? $f : \{0,1\}^* \to \{0,1\}$ $t$ $k = O(1)$ $O(t)$ $3$ $0,1,$

(Z poniższych komentarzy OP). Uwaga: dane wejściowe są zapisywane przy użyciu , ale maszyna Turinga z alfabetem wielkości może nadpisać symbole wejściowe symbolami z większego alfabetu. Nie widzę, jak zakodować symbole w większym alfabecie w mniejszym alfabecie bez konieczności przesuwania danych wejściowych, co kosztowałoby czas . $0,1$ $k$ $n^2$

computability turing-machines

— Manu
źródło

Uwaga: dane wejściowe są zapisywane za pomocą

, ale maszyna Turinga wykorzystująca alfabet wielkości

może nadpisać symbole wejściowe symbolami z większego alfabetu. Nie widzę, jak zakodować symbole w większym alfabecie w mniejszym alfabecie bez konieczności przesuwania danych wejściowych, co kosztowałoby czas

0, 1

$0,1$

k

$k$

n^{2}

$n^2$

— Manu

@Emanuele: Powinieneś edytować pytanie i podkreślić ten aspekt; inaczej brzmi dokładnie jak standardowe ćwiczenie z podręcznika ...

— Jukka Suomela

@Tsuyoshi, myślę, że źle zrozumiałeś pytanie.

— Suresh Venkat

@Jukka: Na maszynie Turinga z jedną taśmą wszystko, co można obliczyć w czasie

to w rzeczywistości zwykłe języki.

o (n \log n)

$o(n \log n)$

— Kristoffer Arnsfelt Hansen

@Abel: Wynik cytowany przez Arorę i Baraka omija tutaj główny problem, ponieważ w ich modelu (który jest dość standardowy dla wielopasmowych baz TM) mają osobną taśmę wejściową tylko do odczytu.

— Joshua Grochow

Odpowiedzi:

$o( |x| \log |x|)$

$\Sigma_4 = \{\epsilon,0,1,2 \}$ $f:\{0,1\}^* \to \{0,1\}$ $L = \{ x | f(x) = 1 \}$ $(o( |x| \log |x|))$

$1DLIN = 1DTime(O(n))$

$REG = 1DLIN$
$REG = 1DTime(o(n \log n))$

$L$ $\Sigma_3 = \{\epsilon,0,1\}$

$\Sigma_3$

... nie możesz zbudować go bezpośrednio z TM4, ale TM3 istnieje.

$\Omega(n^2)$

$\Omega(n\log n) \cap o(n^2)$

(1) Hennie, obliczenia maszyny Turinga na jednej taśmie, off-line (1965)

(2) Kobayashi, O strukturze niedeterministycznej hierarchii czasowej maszyny Turinga na jednej taśmie (1985)

— Marzio De Biasi
źródło

o (n \log n)

$o(n\log n)$

Ω (n \log n) \cap o (n^{2})

$\Omega(n\log n) \cap o(n^2)$

Masz rację, nie zauważyłem komentarza Kristoffera. Źle wyraziłem interesujący przypadek (nie wiem, jak to udowodnić), więc zaktualizowałem odpowiedź.

— Marzio De Biasi,

o (n \log n)

$o(n \log n)$

O (n)

$O(n)$

L

$L$

O (n^{2})

$O(n^2)$

x \in L

$x \in L$

| x |^{2}

$|x|^2$

x \notin L

$x \notin L$

| x |^{2}

$|x|^2$

O (n)

$O(n)$ czasu i nie można go rozwiązać za pomocą skończonej maszyny stanów.

— Jukka Suomela,

Θ (n^{2})

$\Theta(n^2)$

x

$x$

Θ (| x |^{2})

$\Theta(|x|^2)$

x \in L

$x \in L$

Θ (| x |)

$\Theta(|x|)$ fragmenty wypełnienia.)

— Jukka Suomela,

-4

~~$1$ $\log_k(x) \in \Theta(\log_l(x))$ $k, l > 1$~~

$t$ $t$ $k$ $\{0,1,\dots,k-1\}$ $\lceil \log_2(k) \rceil$ $\lceil \log_2(k) \rceil$ $\{0,1\}$ (puste miejsca są zaznaczone, aby zaznaczyć nieużywane komórki). Uwaga: są to zasadniczo binarnie kodowane cyfry.

$\lceil \log_2(k) \rceil \cdot t \in \mathcal{O}(t)$

$\{0,1\}$ $\mathcal{O}(n^2)$ $\mathcal{O}(n^2) + \lceil \log_2(k) \rceil \cdot t$

$t(n) \in \Omega(n^2)$ $\Omega(n^2)$

— Raphael
źródło

Dopóki nie przekonasz mnie, dlaczego tak ma być, zachowam tę opinię.

— Andrej Bauer,

Chciałbym usłyszeć dowody na twoje roszczenie. Wszystko to tylko jedno roszczenie.

— Andrej Bauer,

Och, rozumiem o czym mówisz. Ok przepraszam. Jednak pytanie nie dotyczy tego . To niewielka odmiana.

— Andrej Bauer,

Myślę, że przypadek z t = Ω (n ^ 2) jest łatwym przypadkiem, ponieważ można sobie pozwolić na czas na przesunięcie ciągu wejściowego. Istotnym przypadkiem jest sytuacja, gdy t = o (n ^ 2). Nie wiem, jak ważne jest rozważenie pojedynczej taśmy TM z czasem o (n ^ 2), ale pytanie o to.

— Tsuyoshi Ito

Ω (n^{2})

$\Omega(n^2)$