Conjectura de Hartmanis-Stearns e os números transcendentais computáveis

No artigo de 1965 " Sobre a complexidade computacional dos algoritmos ", de Hartmanis e Stearns, os autores conjeturam que se uma Máquina de Turing em tempo real computa o número real , por exemplo, na base 10, então é um número racional ou um número transcendental. $r$ $r$

Existe um número transcendental computável que não é computável por uma máquina de Turing em tempo real, por exemplo, na base 10?

cc.complexity-theory reference-request examples XL _At_Here_There
fonte

Se entendi sua pergunta corretamente, as constantes de Chaitin são exemplos de tais números: são transcendentais e não são computáveis.

284 Bruno

@ Bruno ，, mas as constantes de Chaitin não são computáveis ou semicomputáveis, portanto, não são os números que são números transcendentais computáveis e não são computáveis por uma máquina de Turing em tempo real.

XL _At_Here_There

Meu erro, eu não percebi que você pediu um número computável ...

de Bruno

Respostas:

Seja um idioma EXPTIME-complete e seja o real correspondente. Claramente é computável. O número não pode ser algébrica desde o -ésimo bit de um número algébrico pode ser calculado em tempo ( Datta e Pratap ). Uma vez que o -ésimo bit de qualquer número calculável por uma máquina de Turing em tempo real pode ser calculado em tempo , não pode ser calculado por um tempo real Turing máquina. $L$ $r \in (0,1)$ $r$ $r$ $n$ $n^{O(1)}$ $n$ $O(n)$ $r$

Yuval Filmus
fonte

Excelente, mas tenho que pensar com cuidado. E acabei de descobrir que o Datta e o Pratap é um artigo que acaba de ser publicado recentemente.

XL _At_Here_There

Presumivelmente, sabia-se que a expansão binária de números algébricos pode ser calculada em tempo polinomial. O artigo deles é apenas o primeiro que pude encontrar e, na verdade, prova resultados mais fortes.

Yuval Filmus

Sim, eu especulam há muito tempo que a expansão binária de números algébricos pode ser calculado em tempo polinomial, mas não encontraram qualquer prova de que, mais uma vez obrigado pela sua resposta e do papel referenciada

XL _At_Here_There