He leído que problemas resemblings collatz se han demostrado para ser indecidible. Conway probó parecer pero Im no está seguro si la prueba fue constructiva.
Por lo que me pregunto: ¿Cuál es el más simple collatz como problema es indecidible?
Respuesta
¿Demasiados anuncios?
lhf
Puntos
83572
Yo no sé acerca de los más simples, pero esta respuesta por Gerry Myerson cita dos documentos que prueban que algunas generalizaciones naturales de la Collatz problema indecidible:
Conway, "Impredecible iteraciones", 1972
Kurtz y Simón, "El Undecidability de la Generalizada Collatz Problema", 2007
También hay una más reciente, bastante corto de papel:
- Lehtonen, Dos indecidible variantes de Collatz problemas, 2008
el PDF parece libremente disponible
