Esse idioma é reconhecível por uma TM de 3 símbolos em O (n log n)?

10

Eu estava brincando com a pergunta muito interessante e ainda aberta " Alfabeto da máquina de Turing de fita única " (de Emanuele Viola) e surgiu com o seguinte idioma:

L={x{0,1}n s.t. |x|=n=2m and count1(x)=km;n,m,k1}

onde é o número de 1 s na cadeia de x.count1(x)1

Por exemplo, se x = 01101111, então n = 8, m = 3, k = 2; então xL

L pode ser reconhecido por uma máquina de Turing com uma única fita e um alfabeto de 3 símbolos nas etapas O ( n log n ) ? {ϵ,0,1}O(nlogn)

Se usarmos 4 símbolos, a resposta é sim:

  • verifique se substituindo 0 s por ϵ e 1 s por 2 e, ao mesmo tempo, armazene m 1 s à direita;|x|=2m0ϵ12m 1
  • então conte o número de s módulo m em O ( n log n ) .2mO(nlogn)

Por exemplo:

....01101111....... input x  (|x| = 8 = 2^3)
000.021.1212.0001.. div 2, first sweep (000. can safely be used as a delimiter)
000.022.1222.00011. div 2, second sweep
000.022.2222.000111 div 2, third sweep --> m = 3 (= log(n) )
000..22.2222....111 cleanup (original 1s are preserved as 2)
000..22.2221102.... start modulo m=3 calculation
000..22.2210022.... mod 3 = 2
000..22.2000222.... mod 3 = 0
000..22.0012222.... mod 3 = 1
000..20112.2222.... mod 3 = 2
000..11122.2222.... ACCEPT
Marzio De Biasi
fonte
|x|=n=2mxcount1(x)1L={10}
xL
11
Θ(nlogn)o(nlogn)O(nlogn)

Respostas:

10

Você não pode usar a mesma idéia que tem para o caso de 4 símbolos , com as seguintes modificações:

  • Sempre processe um par de símbolos simultaneamente.
  • (00,01,10,11)(ϵ0,ϵ1,0ϵ,1ϵ)ϵϵ
  • Use um truque semelhante para as etapas "mod 2".

O(1)

Jukka Suomela
fonte
Você está certo! ... agora eu suspeito que a resposta à pergunta de Emanuele é sim ... mas ainda está aberta para que, provavelmente, não é muito fácil de provar formalmente :-( Graças!
Marzio De Biasi