¿Hay algún lenguaje decidible incontable de Turing?

17

Hay muchos (y quiero decir muchos) idiomas contables que son decidibles por Turing. ¿Puede cualquier lenguaje incontable ser Turing decidible?

Jyotirmoy Pramanik
fuente
2
Si el lenguaje de todas las palabras posibles es incontable (lo que requiere un alfabeto incontable), inmediatamente proporciona un ejemplo de un lenguaje incontable decidible (trivial) de Turing. Si no lo es (es decir, es contable), entonces los sublenguajes tampoco son incontables.
Marc van Leeuwen

Respuestas:

25

Cada idioma sobre un alfabeto finito (o incluso contable) es contable. Suponiendo que el alfabeto de su máquina Turing es finito, cualquier idioma que pueda aceptar es contable.

Yuval Filmus
fuente
¿Qué pasa con el conjunto de todos los idiomas de un número finito de cadenas sobre un alfabeto infinito? ¿Es contable o incontable? Tampoco pude pensar en la prueba de "el lenguaje sobre un alfabeto infinitamente contable es contable".
anir
Su conjunto también es contable.
Yuval Filmus
Esto demuestra que "un conjunto de idiomas sobre alfabeto finito es contable". Siento que podemos demostrar que "un conjunto de idiomas que contienen innumerables cadenas infinitas sobre alfabeto finito es contable" siguiendo el mismo enfoque de prueba debido al alfabeto finito. Pero no puedo imaginar cómo se puede adaptar este enfoque para un alfabeto infinitamente contable.
anir
No puedes probarlo ya que es falso. El número de secuencias binarias infinitas ya es incontable.
Yuval Filmus
12

Podemos tener innumerables idiomas solo si permitimos palabras de longitud infinita, véase, por ejemplo , el lenguaje Omega-regular . Estos idiomas se llaman ω -lenguajes. Otro ejemplo será el lenguaje del subconjunto de reales que contiene, por ejemplo, expansiones decimales de todos los números reales.

Hay algunos modelos en los que las máquinas de Turing se modifican para aceptar idiomas . Algunos de estos modelos utilizan la condición de Buchi para su aceptación. Como no puede ver la totalidad de la entrada en tiempo finito, decimos que la entrada se acepta si la máquina de Turing ingresa en el estado de aceptación infinitas veces. Si podemos probar esto analizando la entrada (no ejecutándola), decimos que la entrada es aceptada.ω

Shreesh
fuente
1
¿Por qué el alfabeto debería ser contable?
Leftaroundabout
2
Cada modelo que se estudia tiene un alfabeto finito. Si el alfabeto también se vuelve infinito (contable o incontable) es difícil tener un modelo razonable.
Shreesh
@Shreesh Bueno, si el alfabeto es incontable, un mapeo ingenuo de un FSM (con transiciones incontables entre un número finito de estados) podría ser bastante poderoso.
Yakk
1
Es cierto que este es el tipo de extensiones, que pueden tener clases de idiomas que pueden ser superclase de RE o lenguajes recursivos. Pero no se estudian bien, si es que se estudian en absoluto. El mayor problema es, en mi opinión, cómo podemos dar una representación finita de la máquina. Luego tienes que escribir el símbolo en una celda de cinta. Incluso la humilde celda puede necesitar memoria infinita para almacenar la descripción del símbolo de la cinta que se está escribiendo.
Shreesh
Esta es una gran explicación. Agregaría que incluso si se usa un criterio habitual de aceptación / rechazo, podría decirse que todavía existen algunos idiomas que una máquina de Turing podría decidir y técnicamente tendría innumerables cadenas, pero solo porque la gran mayoría de los caracteres son " inútil "al lenguaje.
Owen
5

La computabilidad clásica analiza funciones sobre cadenas finitas de un alfabeto finito. Como resultado, todos los idiomas, ya sean decidibles o indecidibles, son contables.

Para considerar innumerables idiomas , tenemos que mirar cadenas infinitas en lugar de cadenas finitas. (AFAIK, tener un alfabeto infinito no es muy interesante y no corresponde a un modelo realista de computación en sí mismo).

Existen modelos de computación en los que podemos manejar cadenas infinitas que nos permiten representar objetos de innumerables dominios como números reales. Estos a menudo se representan como cálculos de tipo superior. Un modelo que usa máquinas Turing es el modelo TTE. En este modelo, la entrada puede ser cadenas infinitas y las máquinas pueden acceder a cualquier elemento de la cadena que desee. La máquina no necesita terminar, sin embargo, existen condiciones para asegurarse de que la salida de la máquina converja.

Supongamos que la entrada de nuestra máquina es de , es decir, cadenas infinitas del alfabeto Σ , por ejemplo, Σ = { 0 , 1 } . Entonces hay Σ N = 2 N cadenas. Por lo tanto hay 2 2ΣωΣΣ={0,1}ΣN=2N idiomas posibles. El número de máquinas TTE Turing todavía es contable. Entonces, la mayoría de estos idiomas son indecidibles.22N

Pero hay algo aún más interesante aquí: si desea que la máquina se detenga siempre, podrá leer solo una parte inicial finita de la entrada. Como resultado tenemos lo siguiente: Sea una máquina TTE que siempre se detiene (en tiempo finito). Luego hay un lenguaje sin prefijo L Σ y una máquina de Turing N tal que para cualquier x Σ ω , M acepta x iff N acepta la parte inicial de xMLΣNxΣωMxNx que está en L .

Para decirlo en términos simples, el cálculo de las máquinas Turing Turing que siempre se detienen se determina mediante el cálculo de una máquina Turing en cadenas finitas.


Permítanme dar un ejemplo de lenguajes decidibles e indecidibles de cadenas infinitas:

  1. Para cualquier el lenguaje de cadenas infinitas cuya posición k es 0 es decidible. Lo mismo con la posición de k ésima 1. La intersección de dos idiomas decidibles es decidible, por ejemplo, cadenas cuya tercera posición es 0 y 6.kNkk36 ª posición es 1.

  2. La unión de cualquiera de los dos idiomas decidibles es decidible. Ej. Cadenas que comienzan con o0 .10

  3. Sea una lista computablemente enumerable de lenguajes decidibles. Entonces L = i L i es semi-decidible, es decir, hay máquina que se detiene y acepta cada vez que una cuerdas en L y no acepta cuando las cuerdas no es en L . Si no está en L, la máquina podría no detenerse. Se puede obtener cualquier idioma semidecidible mediante la unión de una lista enumerable de idioma del formulario que figura en el punto 1 anterior.LiL=iLiLLL

  4. Un idioma es decidible si tanto el idioma como su complemento son semi-decidibles.

  5. kk


xlgxxlgx para nosotros.


f{0,1}f1(1) ". También hay muchas otras referencias en el sitio web para Computabilidad y Complejidad en la Red de Análisis .

Kaveh
fuente
1
" Como resultado, todos los idiomas son finitos " - ¿Quieres decir contable?
Anton Trunov
Creo que sí, señor Trunov.
Jyotirmoy Pramanik
Esta es una buena publicación, pero no puedo ver qué tiene que ver su volumen con la pregunta específica aquí. ¿Quizás quisiste crear un par de preguntas y respuestas?
Raphael