¿Es este lenguaje reconocible por un TM de 3 símbolos en O (n log n)?

10

Estaba jugando con la muy interesante y abierta pregunta " Alfabeto de la máquina de Turing de una sola cinta " (por Emanuele Viola) y se me ocurrió el siguiente idioma:

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

donde es el número de s en la cadena x.1count1(x)1

Por ejemplo, si x = 01101111 entonces n = 8, m = 3, k = 2; entoncesxL

¿Puede L ser reconocido por una máquina de Turing con una sola cinta y un alfabeto de 3 símbolos en pasos? O ( n log n ){ϵ,0,1}O(nlogn)

Si usamos 4 símbolos, la respuesta es sí:

  • compruebe si reemplaza s con y s con y al mismo tiempo almacene s a la derecha; 0 ϵ 1 2 m 1|x|=2m0ϵ12m 1
  • luego cuente el número de s módulo en .m O ( n log n )2mO(nlogn)

Por ejemplo:

....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
fuente
Si es el número natural representado por que es siempre igual a y entonces ? x c o u n t 1 ( x ) 1 L = { 10 }|x|=n=2mxcount1(x)1L={10}
Marc Bury
Lo siento | x | significa longitud de la cuerda x. Un ejemplo: x = 01101111, n = 8, m = 3, k = 2, y por lo tantoxL
Marzio De Biasi
1
Por cierto, este es un excelente candidato para la pregunta de Emanuele, ya que está en : no es regular por el lema de bombeo, por lo que no puede ser , pero es . o ( n log n ) O ( n log n )Θ(nlogn)o(nlogn)O(nlogn)
Joshua Grochow

Respuestas:

10

¿No puede usar la misma idea que tiene para el caso de 4 símbolos , con las siguientes modificaciones:

  • Siempre procese un par de símbolos simultáneamente.
  • En sus barridos "div 2", marque un bloque de dos símbolos como "procesado" asignando . Todavía tiene disponible como un "separador" que puede usar en ambos extremos, y puede recuperar los datos originales fácilmente.ϵ ϵ(00,01,10,11)(ϵ0,ϵ1,0ϵ,1ϵ)ϵϵ
  • Use un truco similar para los pasos "mod 2".

En general, puede exprimir una cantidad arbitrariamente grande de información de contabilidad con la ayuda del tercer símbolo procesando los símbolos a la vez.O(1)

Jukka Suomela
fuente
¡Tienes razón! ... ahora sospecho que la respuesta a la pregunta de Emanuele es sí ... pero todavía está abierta, así que probablemente no sea demasiado fácil demostrarlo formalmente :-( ¡Gracias!
Marzio De Biasi