Alfabet maszyny Turinga z pojedynczą taśmą

40

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

(Z poniższych komentarzy OP). Uwaga: dane wejściowe są zapisywane przy użyciu , ale maszyna Turinga z alfabetem wielkości k 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 n 2 .0,1kn2

Manu
źródło
8
Uwaga: dane wejściowe są zapisywane za pomocą , ale maszyna Turinga wykorzystująca alfabet wielkości k 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 n 2 . 0,1kn2
Manu
4
@Emanuele: Powinieneś edytować pytanie i podkreślić ten aspekt; inaczej brzmi dokładnie jak standardowe ćwiczenie z podręcznika ...
Jukka Suomela
3
@Tsuyoshi, myślę, że źle zrozumiałeś pytanie.
Suresh Venkat
4
@Jukka: Na maszynie Turinga z jedną taśmą wszystko, co można obliczyć w czasie to w rzeczywistości zwykłe języki. o(nlogn)
Kristoffer Arnsfelt Hansen
6
@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:

5

o(|x|log|x|)

Σ4={ϵ,0,1,2}f:{0,1}{0,1}L={x|f(x)=1}(o(|x|log|x|))

1DLIN=1DTime(O(n))

  • REG=1DLIN
  • REG=1DTime(o(nlogn))

LΣ3={ϵ,0,1}

Σ3

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

Ω(n2)

Ω(nlogn)o(n2)


(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
1
o(nlogn)Ω(nlogn)o(n2)
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,
1
o(nlogn)O(n)
1
LO(n2)xL|x|2xL|x|2O(n)czasu i nie można go rozwiązać za pomocą skończonej maszyny stanów.
Jukka Suomela,
1
Θ(n2)xΘ(|x|2)xLΘ(|x|)fragmenty wypełnienia.)
Jukka Suomela,
-4

1logk(x)Θ(logl(x))k,l>1

ttk{0,1,,k1}log2(k)log2(k){0,1}(puste miejsca są zaznaczone, aby zaznaczyć nieużywane komórki). Uwaga: są to zasadniczo binarnie kodowane cyfry.

log2(k)tO(t)

{0,1}O(n2)O(n2)+log2(k)t

t(n)Ω(n2)Ω(n2)

Raphael
źródło
3
Dopóki nie przekonasz mnie, dlaczego tak ma być, zachowam tę opinię.
Andrej Bauer,
1
Chciałbym usłyszeć dowody na twoje roszczenie. Wszystko to tylko jedno roszczenie.
Andrej Bauer,
2
Och, rozumiem o czym mówisz. Ok przepraszam. Jednak pytanie nie dotyczy tego . To niewielka odmiana.
Andrej Bauer,
6
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
3
Ω(n2)