Aquí hay un rompecabezas que no he logrado resolver. Me gustaría saber si este problema ya se conoce o si tiene una solución fácil.
Es posible definir una biyección utilizando las propiedades de las categorías cerradas bicartesianas. Andrej Bauer publicó una explicación de lo que esto significa en su blog como " Gema constructiva: malabares exponenciales ".
Esta biyección tiene una propiedad interesante: es "entrada limitada", lo que significa que cada componente de la salida depende únicamente de muchos componentes de la entrada. Sin embargo, para , parece que esta construcción solo puede mostrar que y son isomórficos si y son impares o ambos pares. Esto deja abierta la pregunta:
¿Hay una biyección de entrada limitada de a 3 N ?
Aquí hay una breve nota que describe el problema con más detalle: una conjetura sobre biyecciones de entrada limitada de secuencias infinitas .
Definiciones:
Una función es una entrada acotada si existe un entero k tal que cada componente de la salida de f dependa solo de la mayoría de los k componentes de la entrada. Más formalmente, f es una entrada limitada si para cada índice j ∈ J hay índices i 1 , ⋯ , i k ∈ I y una función f m : X tal que para todox∈Xel componente f(x)jes igual afj(x i 1 ,⋯,x i k ).
Una biyección es una biyección de entrada limitada si es una función de entrada limitada.
Una biyección es un isomorfismo de entrada limitada si ésta y su inverso son funciones de entrada limitada. Esto también es interesante.
fuente
Respuestas:
No soy un tipo de teoría de CS. Pero en la teoría ergódica este tipo de mapeo se conoce como isomorfismos finitarios . Por ejemplo, las personas consideraron si dos secuencias de Bernoulli de la misma entropía son finitamente isomorfas o no. Por ejemplo (este es un cambio unilateral porque parece que le preocupa lugar de P Z ):PN PZ
A. Del Junco, "Códigos finitarios entre los cambios de Bernoulli unilaterales", Ergodic Theory Dynamical Systems, vol. 1, págs. 285-301, 1981.
PD: Tengo la intención de dejar esto como un comentario, pero no puedo debido a la falta de reputación. Avíseme si está completamente fuera de tema, lo eliminaré.
fuente
Creo que cualquier colección de prefijos binarios exclusivos y exhaustivos de tamaño k debería proporcionar un isomorfismo entre y 2 N , por ejemplo para k = 3 podríamos usar "0", "10" y "11". En general, podemos usar "0", "10", "110", ..., "11 ... 10", "11 ... 11" donde el penúltimo tiene k - 2 unidades y el el último tiene k - 1 .kN 2N k k=3 k−2 k−1
La naturaleza exclusiva y exhaustiva nos permite definir el inverso ( ) de manera obvia.2N→kN
La acotación en la dirección hacia delante es fácil, ya que cada uno de los dígitos de entrada proporciona al menos un dígito de salida el ésimo dígito binario se determina fácilmente por no más de la primera i k dígitos ary.i i k
La delimitación en la dirección hacia atrás es un poco más fea. Con la colección prefijo di encima de cada dígitos ary "lee" de en la mayoría de k dígitos binarios y por lo que el i ésimo k ary dígitos se determina por no más de la primera k i dígitos binarios.k k i k ki
fuente