Cualquier número trascendental computable que sea computable en tiempo P pero no

9

¿Hay algún número trascendental computable conocido tal que su º dígito es computable en tiempo polinomial, pero no en ?nO(n)

XL _A__Aquí_Aquí
fuente
2
Todavía no tiene sentido. ¿Quieres decir "... pero no a tiempo ", o qué? O(n)
Emil Jeřábek
Quiero decir en tiempo P y no en . No estoy seguro si mi inglés es incorrecto o el tuyo, de todos modos gracias por tu comentario. O(n)
XL _At_Here_There
2
Si el autor logra formular esta pregunta en un inglés legible, entonces podría estar relacionado con la Conjetura de Hartmanis-Stearns: cada número real calculado por una máquina de Turing multitapa en tiempo real es trascendental o racional.
Gamow
@Gamow a la derecha, pero excluye el caso de la conjetura de Hartmanis-Stearns.
XL _At_Here_There
2
Traté de hacer esto comprensible, pero aún no está muy claro. ¿Quiere decir que no se sabe que sea computable en , o que no sea computable en ? ¿Cuál es el modelo de cálculo: máquina Turing de una o varias cintas, o algo más? O(n)O(n)
Sasho Nikolov

Respuestas:

19

Aquí está la construcción de tal número. Puede discutir si esto significa que tal número es "conocido".

Tome cualquier función de a donde el 'th dígitos no es computable en tiempo. Dicha función existe, por ejemplo, mediante la técnica de diagonalización habitual. Interpretar como el 'th dígito decimal de algún número real . Ahora, para cada de la forma , , cambie los dígitos de en las posiciones a 's. El número resultante conserva evidentemente la propiedad que elfN{1,2,,8}nO(n)f(n)nαn22kk1αn,n+1,,3n0βn -ésimo dígito no es computable en tiempo, pero tiene una infinidad de muy buenas aproximaciones de números racionales, por ejemplo a fin , de la forma . Entonces, según el teorema de Roth, no puede ser algebraico. (No es racional porque tiene bloques arbitrariamente largos de activados por nonzeros en ambos lados).O(n)O(q3)p/qβ0

Jeffrey Shallit
fuente
12

Más generalmente, para cualquier constante , hay números trascendentales computables en el tiempo polinómico, pero no en el tiempo O ( n k ) .k1O(nk)

Primero, según el teorema de la jerarquía de tiempo, existe un lenguaje no computable en el tiempo O ( 2 k n ) . Podemos suponer que L { 0 , 1 } , y también podemos suponer que todas las cadenas w L tienen una longitud divisible por 3 .L0EO(2kn)L{0,1}wL3

Segundo, que sea ​​la versión unaria de L 0 . Para mayor claridad, para cualquier w { 0 , 1 } , deje N ( w ) denotar el número entero cuya representación binaria es 1 w , y ponga L 1 = { a N ( w ) : w L 0 } . Entonces L 1P , pero L 1 no es computable en el tiempo OL1L0w{0,1}N(w)1wL1={aN(w):wL0}L1PL1 . Además, L 1 tiene la siguiente propiedad: para cualquier m , L 1 no contiene ninguna a n tal que 2 3 m + 1n < 2 3 m + 3 .O(nk)L1mL1an23m+1n<23m+3

Tercero, dejemos que (Asumo aquí que la pregunta es sobre calcular números en binario. Si no, el 2 anterior se puede reemplazar con cualquier base deseada, no importa).

α={2n:anL1}.
2

Entonces es computable en tiempo polinómico, ya que podemos calcular sus primeros n bits comprobando si a , a 2 , ... , a n están en L 1 . Por la misma razón, no es computable en tiempo O ( n k ) , como el n bit-ésimo determina si un nL 1 .αna,a2,,anL1O(nk)nanL1

Para cualquier , supongamos que p = { 2 2 3 m + 1 - n : n L 1 , n < 2 3 m + 1 } = α 2 2 3 m + 1, y q = 2 2 3 m + 1 . Entonces | α - pm

p={223m+1n:nL1,n<23m+1}=α223m+1,
q=223m+1 Por lo tanto,αtiene una medida de irracionalidad de al menos4, por lo tanto, es trascendental segúnel teorema de Roth.
|αpq|223m+3=q4.
α4
Emil Jeřábek
fuente
2
Hmm, veo que me sacaron. Dejaré la respuesta de todos modos, ya que puede ser útil para alguien.
Emil Jeřábek
3
Elegí la publicación de Jeffrey como respuesta a la pregunta, ya que su respuesta se publicó anteriormente.
XL _At_Here_There
66
Si. Me recordaré la próxima vez que no me moleste en perder tiempo y esfuerzo en escribir una respuesta exhaustiva con todos los detalles técnicos, ya que aparentemente es más valioso publicar unos minutos antes.
Emil Jeřábek
3
: D, genial! Espero que podamos disfrutar de más temas.
XL _At_Here_There