Conjetura de Hartmanis-Stearns y los números trascendentales computables

En el artículo de 1965 " Sobre la complejidad computacional de los algoritmos " de Hartmanis y Stearns, los autores conjeturan que si una máquina de Turing en tiempo real calcula el número real en, por ejemplo, la base 10, entonces es un número racional o un número trascendental $r$ $r$

¿Existe un número trascendental computable que no sea computable por una máquina de Turing en tiempo real, por ejemplo, en la base 10?

cc.complexity-theory reference-request examples XL _A__Aquí_Aquí
fuente

Si entiendo su pregunta correctamente, las constantes de Chaitin son ejemplos de tales números: son trascendentales y no son computables en absoluto.

Bruno

@ Bruno, pero las constantes de Chaitin no son computables, ni semicomputables, por lo que no son los números los que son números trascendentales computables y no son computables por una máquina de Turing en tiempo real.

XL _At_Here_There

Mi error, no me di cuenta de que pedías un número computable ...

Bruno

Respuestas:

Sea un lenguaje EXPTIME-complete, y sea el real correspondiente. Claramente, es computable. El número no puede ser algebraica ya que el ésimo bit de un número algebraico se puede calcular en el tiempo ( Datta y Pratap ). Dado que el ésimo bit de cualquier computable número por una máquina de Turing en tiempo real se puede calcular en tiempo , no se puede calcular por un tiempo real de máquina de Turing. $L$ $r \in (0,1)$ $r$ $r$ $n$ $n^{O(1)}$ $n$ $O(n)$ $r$

Yuval Filmus
fuente

Excelente, pero tengo que pensarlo cuidadosamente. Y acabo de descubrir que Datta y Pratap es un artículo que se acaba de publicar recientemente.

XL _At_Here_There

Presumiblemente se sabía que la expansión binaria de los números algebraicos se puede calcular en tiempo polinomial. Su trabajo es el primero que pude encontrar, y en realidad demuestra resultados más sólidos.

Yuval Filmus

Sí, he conjeturado durante mucho tiempo que la expansión binaria de los números algebraicos se puede calcular en tiempo polinómico, pero no he encontrado ninguna prueba de eso, gracias de nuevo por su respuesta y el documento de referencia

XL _A__Aquí_Aquí