Biyecciones de entrada limitada de secuencias infinitas

28

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 3N5N 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 k,l2 , parece que esta construcción solo puede mostrar que kN y lN son isomórficos si k y l son impares o ambos pares. Esto deja abierta la pregunta:

¿Hay una biyección de entrada limitada de a 3 N ?2N3N

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 kI y una función f m : Xf:iIXijJYjkfkfjJi1,,ikI tal que para todoxXel componente f(x)jes igual afj(x i 1 ,,x i k ).fm:Xi1××XikYjxXf(x)jfj(xi1,,xik)

Una biyección es una biyección de entrada limitada si es una función de entrada limitada.f

Una biyección es un isomorfismo de entrada limitada si ésta y su inverso son funciones de entrada limitada. Esto también es interesante.f

Colin McQuillan
fuente
Probablemente sea mejor copiar la definición de "biyección de entrada limitada" de su nota. No entendí la definición hasta que la leí.
Tsuyoshi Ito
1
Hecho. Me gustaría señalar que, si bien la motivación de la pregunta proviene de la semántica de la teoría de categorías, el rompecabezas en sí es combinatorio.
Colin McQuillan
1
¡Lo más molesto de este problema es que parece fácil! Todos los conjuntos están delimitadas-entrada isomorfo a la otra, y también lo son todos los conjuntos ( 2 k + 1 ) N . No puedo ver ninguna razón por la cual estos dos no se pueden hacer isomorfos de entrada limitada mediante el uso de una variación de los isomorfismos utilizados en las pruebas existentes, pero tales intentos parecen fallar. Aghh (No tengo experiencia en este campo, así que puedo estar fuera de lugar.)(2k)N(2k+1)N
Tsuyoshi Ito
1
Realmente me gusta esta conjetura, y ha estado saliendo por un mes ahora. Daré una recompensa a cualquiera que lo resuelva o haga un progreso sustancial en cualquier dirección.
Aaron Sterling
3
Buena pregunta :-) Por cierto, ¿cuál es el isomorfismo "más simple" entre y 3 N que conoces? 2N3N
Andrej Bauer

Respuestas:

2

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 ):PNPZ

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é.

gondolero
fuente
Por mi parte, agradezco cualquier idea loca de lluvia de ideas en este momento.
Aaron Sterling el
2
Tenga en cuenta que si los índices se toman de ℕ o ℤ es irrelevante en esta pregunta.
Tsuyoshi Ito
He otorgado la recompensa completa a esta respuesta, porque, si no hiciera nada, la respuesta recibiría la mitad de la recompensa de todos modos, como la más votada (y haber recibido al menos dos votos). Si alguien publica una prueba completa o parcial en una fecha posterior, y lo veo, probablemente comenzaré otra recompensa, para otorgar representante al solucionador.
Aaron Sterling el
0

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 .kN2Nkk=3k2k1

La naturaleza exclusiva y exhaustiva nos permite definir el inverso ( ) de manera obvia.2NkN

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.ii 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.kkikki


fuente
2
Esto no es entrada limitada en ninguna dirección. De acuerdo con la definición de una función de entrada limitada, necesita un límite uniforme en el número de variables de entrada de las que depende cada variable de salida. En la dirección hacia adelante de su mapeo, la variable de salida i-ésima depende de las primeras variables de entrada i, por lo que no hay un límite uniforme. En la dirección hacia atrás, la variable de salida i-ésima depende de las primeras variables de entrada ki.
Tsuyoshi Ito
1
D'oh Voy a leer la pregunta por 1.5ª vez. :(