Obliczanie długości wejściowej na maszynie Turinga z jedną taśmą

W związku z tym pytaniem przyszło mi do głowy: jaka jest złożoność czasu w przypadku maszyny Turinga z pojedynczą taśmą do obliczenia długości danych wejściowych? Mówiąc ściślej, powiedzmy, że alfabet na taśmie to , wejściem jest ciąg znaków w otoczony spacjami, maszyna zaczyna się od lewego najbardziej wejściowego symbolu i musi kończyć się na skrajnie lewy symbol łańcucha w $\{0,1,b\}$ $(0+1)^*$ $(0+1)^*$ (ponownie otoczony spacjami), który daje binarną reprezentację długości wejściowej. Można to również traktować jako problem konwersji liczby z jedności na binarną.

Łatwo jest rozwiązać to na maszynie z dwiema taśmami lub maszyną z dwiema głowicami w czasie liniowym (wystarczy zeskanować dane wejściowe jedną głowicą, używając drugiej głowicy do wielokrotnego zwiększania licznika; zwiększanie jest operacją polegającą na stałym zamortyzowanym czasie). Ale rozwiązania pojedynczej głowicy, które mogę wymyślić, to tylko (np. Wielokrotnie zwiększaj licznik, a następnie przesuwaj go o jedną pozycję wzdłuż taśmy). Czy istnieje pasująca dolna granica? $O(n\log n)$

Próbowałem kilka wyszukiwań, ale frazy takie jak „jedna głowa” i „długość wejściowa” są tak powszechne, że utrudniają wyszukiwanie w literaturze znanych wyników tego problemu.

turing-machines David Eppstein
źródło

Ciekawe .. Jest to mniej oczywiste, niż się wydaje. Jestem ciekawy, czy istnieje związek między dolną granicą dla tego a dolną granicą dla nieświadomej symulacji TM. (Każda TM rozwiązująca ten problem z definicji byłaby nieświadoma (lub miałaby niepotrzebny kod).)

Daniel Apon

Odpowiedzi:

$o(n\lg n)$

$M$ $x$ $x$

$M$

$M$ $o(n \lg n)$ $o(n \lg n)$ $\mathsf{DTime}(n \lg n)$

L = {0^{i} ∣ \exists k i = 2^{k}}

$L = \{ 0^i \mid \exists k \ i = 2^k\}$

D T i m e (o (n \lg n)) = R e g

$\mathsf{DTime}(o(n \lg n)) = \mathsf{Reg}$

L

$L$

M

$M$

o (n \lg n)

$o(n \lg n)$

Kaveh
źródło

D T i m e (o (n \lg n)) = R e g

$\mathsf{DTime}(o(n\lg n))=\mathsf{Reg}$

D T i m e (n \lg n) = R e g

$\mathsf{DTime}(n \lg n) = \mathsf{Reg}$

Dzięki za wskazówki, zajrzałem do „Klasycznej teorii rekurencji” vol. II. To, że się zmieniło, nie jest dla mnie tak jasne. Na przykład książka Sipsera używa baz TM z pojedynczą taśmą do definiowania klas złożoności czasu, ale książka Hopcroft-Ullman i najnowsze Arora-Barak i Goldreich używają wieloformatowych baz TM.

Bruno

@Bruno, myślę, że bardziej powszechna definicja DTime jest bardziej skomplikowana. Np. Powszechnie stwierdzane twierdzenie, że „twierdzenie o hierarchii czasu nie jest ścisłe” jest prawdziwe tylko w przypadku maszyn z jedną taśmą, w przypadku urządzeń z dwiema taśmami wiadomo, że jest ścisłe od 1982 r.

Kaveh

D T i m e

$\mathsf{DTime}$