Conjecture de Hartmanis-Stearns et nombres transcendantaux calculables

10

Dans l'article de 1965 « Sur la complexité de calcul des algorithmes » de Hartmanis et Stearns, les auteurs supposent que si une machine de Turing en temps réel calcule le nombre réel dans, par exemple, la base 10, alors est soit un nombre rationnel soit un numéro transcendantal.rr

Existe-t-il un nombre transcendantal calculable qui n'est pas calculable par une machine de Turing en temps réel dans, par exemple, la base 10?

XL _At_Here_There
la source
Si je comprends bien votre question, les constantes de Chaitin sont des exemples de tels nombres: ils sont transcendantaux et ne sont pas du tout calculables.
Bruno
@ Bruno , mais les constantes de Chaitin ne sont ni calculables, ni semi-calculables, donc ce ne sont pas les nombres qui sont des nombres transcendantaux calculables et qui ne sont pas calculables par une machine de Turing en temps réel.
XL _At_Here_There
Mon erreur, je n'ai pas remarqué que vous avez demandé un nombre calculable ...
Bruno

Réponses:

9

Lr(0,1)rrnnO(1)nO(n)r

Yuval Filmus
la source
Excellent, mais je dois y réfléchir attentivement. Et je viens de découvrir que le Datta et Pratap est un article qui vient d'être publié récemment.
XL _At_Here_There
Vraisemblablement, on savait que l'expansion binaire des nombres algébriques peut être calculée en temps polynomial. Leur article n'est que le premier que j'ai pu trouver, et il donne en fait de meilleurs résultats.
Yuval Filmus
Oui, je conjecture depuis longtemps que l'expansion binaire des nombres algébriques peut être calculée en temps polynomial, mais je n'ai trouvé aucune preuve de cela, merci encore pour votre réponse et le document de référence
XL _At_Here_There