Alfabeto da máquina de Turing de fita única

40

Todas as funções computáveis ​​no tempo t em uma máquina de Turing de fita única usando um alfabeto do tamanho k = O ( 1 ) podem ser computadas no tempo O ( t ) em uma fita única máquina de Turing usando um alfabeto de tamanho 3 (por exemplo, 0 , 1 , e em branco)?f:{0,1}{0,1}tk=O(1)O(t)30,1,

(Dos comentários abaixo do OP) Observe que a entrada é escrita usando , mas a máquina de Turing usando o alfabeto do tamanho k pode substituir os símbolos de entrada pelos símbolos do alfabeto maior. Não vejo como codificar símbolos no alfabeto maior no alfabeto menor sem precisar mudar a entrada, o que custaria o tempo n 2 .0,1kn2

Manu
fonte
8
Observe que a entrada é escrita usando , mas a máquina de Turing usando o alfabeto de tamanho k pode substituir os símbolos de entrada por símbolos do alfabeto maior. Não vejo como codificar símbolos no alfabeto maior no alfabeto menor sem precisar mudar a entrada, o que custaria o tempo n 2 . 0,1kn2
Manu
4
@ Emanuele: Você deve editar a pergunta e enfatizar esse aspecto; caso contrário, soa exatamente como um exercício manual padrão ...
Jukka Suomela
3
@ Tsuyoshi, acho que você não entendeu a pergunta.
Suresh Venkat
4
@Jukka: Em uma máquina de Turing com uma fita, tudo o que pode ser calculado no tempo é de fato linguagens regulares. o(nlogn)
Kristoffer Arnsfelt Hansen
6
@Abel: O resultado que você cita de Arora e Barak contorna a questão principal aqui, porque em seu modelo (que é bastante padrão para TMs multipara), eles têm uma fita de entrada separada, somente leitura.
Joshua Grochow

Respostas:

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

... você não pode construí-lo diretamente do TM4, mas o TM3 existe.

Ω(n2)

Ω(nlogn)o(n2)


(1) Cálculos de máquinas de Turing off-line de Hennie, com uma fita (1965)

(2) Kobayashi, Sobre a estrutura da hierarquia de tempo de máquina de Turing não determinística de uma fita (1985)

Marzio De Biasi
fonte
11
o(nlogn)Ω(nlogn)o(n2)
Você está certo, eu não notei o comentário de Kristoffer. Expressei mal o caso interessante (não sei como provar), então atualizei a resposta.
Marzio De Biasi
11
o(nlogn)O(n)
11
LO(n2)xL|x|2xL|x|2O(n)tempo, e não é solucionável usando uma máquina de estados finitos.
Jukka Suomela
11
Θ(n2)xΘ(|x|2)xLΘ(|x|)bits de preenchimento.)
Jukka Suomela
-4

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

ttk{0,1,,k1}log2(k)log2(k){0,1}(espaços em branco são reservados para marcar células não utilizadas). Observe que este é essencialmente um código binário.

log2(k)tO(t)

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

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

Rafael
fonte
3
Até que você me convença por que isso deveria ser o caso, vou manter isso em votação.
Andrej Bauer
11
Gostaria de ouvir algumas evidências de sua reivindicação. Tudo isso, é apenas uma alegação.
Andrej Bauer
2
Oh, entendo a que você está se referindo. Ok desculpe. No entanto, a questão não é sobre isso . É uma ligeira variação.
Andrej Bauer
6
Eu acho que o caso com t = Ω (n ^ 2) é o caso mais fácil, porque você pode ter tempo para mudar a string de entrada. O caso essencial é quando t = o (n ^ 2). Não sei o quanto é importante considerar a TM de fita única com o (n ^ 2) tempo, mas a questão é sobre isso.
Tsuyoshi Ito 16/02
3
Ω(n2)