Qualquer número transcendental computável computável no tempo P, mas não

9

Existe algum número transcendental computável conhecido tal que o seu º dígito é computável em tempo polinomial, mas não em ?O ( n )nO(n)

XL _At_Here_There
fonte
2
Ainda não faz sentido. Você quer dizer "... mas não a tempo ", ou o quê? O(n)
Emil Jeřábek
Quero dizer no tempo P e não no . Não tenho certeza se meu inglês está errado ou o seu, de qualquer forma, obrigado pelo seu comentário. O(n)
XL _At_Here_There
2
Se o autor conseguir formular essa pergunta em inglês legível, isso pode estar relacionado à conjectura de Hartmanis-Stearns: Todo número real calculado por uma máquina de Turing multitape em tempo real é transcendental ou racional.
Gamow
@ Gamow certo, mas exclui o caso da conjectura Hartmanis-Stearns.
XL _At_Here_There
2
Tentei tornar isso compreensível, mas ainda não está muito claro. Você quer dizer que não se sabe computável em ou provavelmente não computável em O ( n ) ? Qual é o modelo de computação: máquina de Turing de uma ou várias fitas, ou algo mais? O(n)O(n)
Sasho Nikolov

Respostas:

19

Aqui está a construção desse número. Você pode argumentar se isso significa que esse número é "conhecido".

Tomar qualquer função a partir de N de { 1 , 2 , ... , 8 } onde o n 'th dígito não é calculável no S ( n ) de tempo. Essa função existe, por exemplo, pela técnica usual de diagonalização. Interpretar f ( n ) como o n 'th dígitos decimais de algum número real α . Agora, para cada n da forma 2 2 k , k 1 , altere os dígitos de αfN{1,2,,8}nO(n)f(n)nαn22kk1αnas posições a 0 's. O número resultante β evidentemente retém a propriedade de que o n 'th dígito não é calculável no S ( n ) de tempo, mas tem um número infinito de muito boas aproximações por racionais, dizer a fim ó ( q - 3 ) , da forma p / q . Então, pelo teorema de Roth, β não pode ser algébrico. (Não é racional porque possui blocos arbitrariamente longos de 0n,n+1,,3n0βnO(n)O(q3)p/qβ0desencadeado por nonzeros de ambos os lados.)

Jeffrey Shallit
fonte
12

De maneira mais geral, para qualquer constante , existem números transcendentais computáveis ​​no tempo polinomial, mas não no tempo O ( n k ) .k1O(nk)

Primeiro, pelo teorema da hierarquia do tempo, existe uma linguagem não computável no tempo O ( 2 k n ) . Podemos assumir L { 0 , 1 } , e também podemos supor que todas as strings w L tenham comprimento divisível por 3 .L0EO(2kn)L{0,1}wL3

Segundo, seja a versão unária de L 0 . Para definiteness, para qualquer w { 0 , 1 } * , deixe N ( w ) denotam o número inteiro cuja representação binária é um W , e colocar G 1 = { um N ( w ) : w G 0 } . Então L 1P , mas L 1 não é computável no tempo OL1L0w{0,1}N(w)1weu1 1={umaN(W):Weu0 0}eu1 1Peu1 1 . Além disso, L 1 tem a seguinte propriedade: para qualquer m , L 1 não contém um a n tal que 2 3 m + 1n < 2 3 m + 3 .O(nk)eu1 1meu1 1uman23m+1 1n<23m+3

Terceiro, deixe (Estou assumindo aqui que a pergunta é sobre computação de números em binário. Caso contrário, os 2 acima podem ser substituídos por qualquer base desejada, isso não importa.)

α={2-n:umaneu1 1}.
2

Então é computável em tempo polinomial, pois podemos calcular seus primeiros n bits verificando se a , a 2 , , a n estão em L 1 . Pela mesma razão, não é computável no tempo O ( n k ) , pois o n- ésimo bit determina se um nL 1 .αnuma,uma2,...,umaneu1 1O(nk)numaneu1 1

Para qualquer , seja p = { 2 2 3 m + 1 - n : n L 1 , n < 2 3 m + 1 } = α 2 2 3 m + 1 and , e q = 2 2 3 m + 1 . Então | α - pm

p={223m+1 1-n:neu1 1,n<23m+1 1}=α223m+1 1,
q=223m+1 1 Assim,αpossui uma medida de irracionalidade de pelo menos4, portanto é transcendental peloteorema de Roth.
|α-pq|2-23m+3=q-4.
α4
Emil Jeřábek
fonte
2
Hmm, vejo que fui escavado. De qualquer forma, deixarei a resposta, pois pode ser útil para alguém.
Emil Jeřábek 5/07
3
Eu escolhi o post de Jeffrey como a resposta para a pergunta, já que a resposta dele foi publicada anteriormente.
XL _At_Here_There
6
Sim. Da próxima vez, lembrarei a mim mesma de não me preocupar em perder tempo e esforço em escrever uma resposta completa com todos os detalhes técnicos, pois é aparentemente mais valioso publicar alguns minutos antes.
Emil Jerabek
3
: D, ótimo! Espero que possamos desfrutar de mais tópicos.
XL _At_Here_There