¿Cuál es el problema "más cercano" a la conjetura de Collatz que se ha resuelto con éxito?

Estoy interesado en el problema "más cercano" (y "más complejo") de la conjetura de Collatz que se ha resuelto con éxito (que Erdos dijo que "las matemáticas aún no están maduras para tales problemas"). Se ha demostrado que una clase de problemas "tipo Collatz" es indecidible. Sin embargo, los problemas que son vagamente similares, como el juego MIU de Hofstadter (resuelto, pero ciertamente es más un problema de juguete) son decidibles o se han resuelto.

Preguntas relacionadas

Conjetura de Collatz y gramáticas / autómatas

reference-request open-problem nt.number-theory halting-problem computability vzn
fuente

Dado que esto es HTML y no LaTeX, es más fácil si alinea las referencias donde son pertinentes.

Suresh Venkat

TCS / ángulos empíricos en collatz / referencias

vzn

Hay al menos una persona que afirma que "la conjetura de Collatz" es la respuesta única a su pregunta. Soy escéptico sobre la integridad de la prueba vinculada, pero aún no he pasado suficiente tiempo analizándola.

Boyd Stephen Smith Jr.

Para su información, aquí hay un nuevo artículo de Michel que examina muy bien el área que conecta la indecidibilidad con un marco teórico numérico general, problemas en la teoría numérica de la concurrida competencia de castores

vzn

Respuestas:

Un comentario extendido:

Collatz-como secuencias puede ser calculada por pequeñas máquinas de Turing que tienen pocos símbolos y estados. En " Máquinas de Turing pequeñas y competencia generalizada de castores ocupados " de P. Michel (2004), hay una buena tabla que posiciona problemas similares a Collatz entre TM decidibles (para los cuales el problema de detención es decidible) y Universal TM.

ingrese la descripción de la imagen aquí

$TM(5,2)$ $TM(3,3)$ $TM(2,4)$ $TM(k,l)$ $k$ $l$

De la conclusión del artículo:

$TM(4,2)$

Véase también " La complejidad de las pequeñas máquinas universales de Turing: una encuesta " de D. Woods y T. Neary (2007).

$\mu = 2, v=3,0\rightarrow 00, 1 \rightarrow 1101$

Marzio De Biasi
fuente

Para complementar la respuesta: Conway mostró que hay secuencias similares a Collatz que son indecidibles ams.org/mathscinet-getitem?mr=392904 . es decir, una secuencia tipo collatz puede simular una máquina de turing universal.

Sasho Nikolov

¡Gracias! ¡la encuesta / resultados de mitchell son geniales! Para su aclaración en la tabla, una "T" en una celda indica que se ha demostrado que existe una TM (k, l) que es equivalente a la conjetura de collatz. la perspectiva también sugiere que la conjetura de collatz no es simplemente una curiosidad teórica aislada, sino posiblemente un fenómeno superficial de algo más profundo en la teoría de la computabilidad. pd también muy interesado si alguna vez se resolvió algún "problema similar a collatz" ...?

vzn

$T: \mathbb N \rightarrow \mathbb N$ $T(n)=n/2$ $n$ $T(n)=n+1$ $n$ $n \in \mathbb N$ $k \in \mathbb N$ $T^{(k)}(n)=1$

$T(n)=n+1$ $n$ $T(n)=3n+1$ $n$

Craig Feinstein
fuente

No creo que esto satisfaga la parte "más compleja" de la pregunta, ya que un estudiante motivado de primaria puede identificar la idea clave detrás de la prueba de su declaración con un poco de reflexión.

Yonatan N

Pero si es más complejo y aún resuelto, ya no se parecerá a la Conjetura de Collatz. Además, el título de su pregunta indica que da prioridad al "más cercano" sobre el "más complejo".

Craig Feinstein