¿Es posible poner una topología en idiomas reconocibles por Turing para expresar densidad entre todos los idiomas?

Question

En un Calculabilidad y complejidad supuesto que he tenido en la universidad, hemos demostrado que existen lenguas que no son Turing-reconocible basiclly el uso de Cantor en diagonal del argumento (el conjunto de todos los idiomas es incontable y el conjunto de Turing reconocible de idiomas es contable). Esto trajo de inmediato a la analogía con $\mathbb Q$ que es contable dentro de $\mathbb R$ que no lo es. Pero tenemos una topología en $\mathbb R$ (y por tanto sobre el $\mathbb Q$) lo que nos permite mostrar que $\mathbb Q$ es un subconjunto denso de $\mathbb R$ (también es un espacio métrico).

Una pregunta, a continuación, apareció en mi cabeza: ¿hay alguna manera de poner una topología en el conjunto de idiomas que llevaría a una smilar resultado, es decir, la densidad de la Turing-reconocible lanuages entre todos los idiomas?

Tenga en cuenta que no tengo idea de si esto tiene algún sentido: no estoy realmente en los fundamentos teóricos de la informática, y no tengo idea de si la noción de "cercanía" entre las lenguas tiene ningún sentido. Esto es sólo una pregunta que me he pulsado durante demasiado tiempo, y yo tenía que preguntar si alguien ya ha respondido a esto o si esto es sólo una pregunta sin sentido.

Answer 1

Desde una perspectiva ligeramente diferente: teórica a los efectos de que a menudo es mejor trabajar con computable y uncomputable establece en vez de idiomas; de hecho, si el lenguaje es a través de un alfabeto finito $A$, luego está el clásico naturales correspondencia entre $A^*$ e $\mathbb{N}$ dada por 'base-$|A|$ representación', y no debería ser difícil convencer a ti mismo que una lengua $\mathcal{L}\subseteq\mathcal{P}(A^*)$ es Turing reconocible si el conjunto de $S_L\subseteq\mathbb{N}$ dada por la correspondencia es computable.

Esto nos permite utilizar un estándar de la topología en subconjuntos de a$\mathbb{N}$; por ejemplo, podemos utilizar una métrica como $d(A,B)=2^{-n}$, donde $n$ es el elemento más pequeño de $A\Delta B$. En virtud de esta topología, la computable conjuntos son de hecho 'denso' en el conjunto de todos los subconjuntos de a$\mathbb{N}$ — de hecho, el finito de conjuntos (todos los cuales son computables) ya están densa. (Esto es exactamente otros análogos para la diádica racionales denso en el conjunto de los reales, aunque los 'naturales' mapeo $S\subseteq\mathbb{N}\mapsto \sum_{s\in S} 2^{-s}$ mapa de la subconjuntos de los naturales en $[0,1]$ no funciona ya que no es 1-a-1.)

Answer 2

No sé si esto se puede hacer como quiera, pero algunos pensamientos: un lenguaje de algunos fijos alfabeto $\Sigma$, es simplemente un conjunto de (longitud finita) de las cuerdas, por lo que un miembro de $\mathscr{P}(\Sigma^\ast)$. $\Sigma^\ast$ es esencialmente un subconjunto de un producto $\Sigma^\omega$ por lo que puede administrarse un algo natural topología (si el conjunto finito $\Sigma$ obtiene la topología discreta; obtenemos un subconjunto de un conjunto de Cantor, topológicamente).

El juego de poder de $\Sigma^\ast$ se puede dar un producto de la topología de nuevo, usando la función característica de identificación. Es bien sabido que este conjunto tiene una contables subconjunto denso (Hewitt-Marzcewksi-Pondizcery teorema) así que creo que no es buena la esperanza de que podamos encontrar una Turing reconocible de la familia de lenguas que es denso en esta topología como se describe. No hay tiempo para mirar en más detalles por el momento.. Parece un buen ejercicio para alguien, aunque.