Hay una primitiva recursiva de la función que da el enésimo dígito de $\pi$, a pesar de la tabla del fabricante dilema?

Question

Le pregunté a una pregunta acerca de esto hace un tiempo y quedó eliminado, por lo que he mirado un poco más y voy a explicar mi problema, mejor.

Planetmath.org me dijo que hay una primitiva recursiva de la función que da el enésimo dígito de $\pi$, pero no lo demuestran. Cuando le pregunté antes de cómo se puede demostrar que, un par de personas que se sugiere el uso de Gregorio de la serie. Ahora puedo ver que si usted sabe que para encontrar el n-ésimo dígito de $\pi$ usted necesita para calcular que dentro de $10^{-m}$ donde m es un p.r.f de n, se puede definir $$\lfloor{{10}^n\pi}\rfloor = \lfloor\frac{4\sum_{i=1}^{5\times10^{m-1}} \lfloor{\frac{10^{2m+1}}{2i-1}}\rfloor(-1)^{i-1}}{10^{2m+1-n}}\rfloor$$ y, a continuación, usted básicamente está allí.

El problema es: ¿puede usted ha de encontrar un m tal que el cálculo de pi de la exactitud $10^{-m}$ le da el enésimo dígito correcta con probabilidad 1? No hay, siempre hay una pequeña probabilidad de que los dígitos entre el n y el mth sería a las 9 o 0 todo, y así usted todavía puede obtener el n-ésimo dígito incorrecto, porque decir que todos ellos eran 9, podría haber calculado un número que tenía el enésimo dígito uno alto, digamos ...300000... en lugar de ...299999... que todavía sería preciso dentro de $10^{-m}$. De hecho, si como se sospecha de $\pi$ es normal, no es la secuencia de n nueves producirse un número infinito de veces para cualquier n? Este problema se llama la tabla del fabricante dilema, pero no he encontrado es mencionado explícitamente en este contexto.

Entonces, mi pregunta es, es el caso de que cualquiera de a) realmente no se puede definir una primitiva de la función recursiva mediante una media aritmética de la serie como esta, o b) de hecho, hay alguna manera de encontrar m como una función de n. Gracias!

Answer 1

Esto fue demostrado por K. Mahler (ver también aquí o aquí para el mejor de los límites), que

$$\left|\pi - \frac{p}{q}\right| \geq q^{-42}$$

para cualquier enteros $p,q \geq 2$. Por lo tanto, hay un límite a lo largo de la cadena de $9$'s, o los ceros puede ser. En otras palabras, el uso de la V. Kh. Salikhov enlazado, cualquier $m \geq 8n$ sería suficiente.

Espero que esto ayude a $\ddot\smile$

Answer 2

Si simplemente queremos la función computable (es decir, "recursivo" en la jerga de la teoría de la computabilidad), esto no es un problema. Tenemos un módulo de la convergencia de una serie de $\pi$, por lo que sabemos que un error de límite en cada suma parcial, con los límites de error se va a cero. En efecto, tenemos una computable de la secuencia de anidado racional de los intervalos, cuya intersección es sólo $\pi$.

Así que, si nos limitamos a calcular mejor y mejores aproximaciones, debido a $\pi$ es irracional eventualmente veremos que $\pi$ es mayor que o menor que cualquier número racional $r$, debido a $r$ caerá fuera uno de los intervalos en nuestra secuencia.

Porque decimal finito expansiones de dar los números racionales, esto significa que podemos definir la precisión decimal de expansión en varias ocasiones de encontrar el siguiente dígito de esta manera.

Sin embargo, este proceso no es, obviamente, primitiva recursiva, porque no hay ningún límite en que tan pequeño sea el intervalo será necesario antes de que se excluye a nuestro destino racional $r$. Este es exactamente el problema mencionado en la pregunta, donde una larga cadena de $9$s en una aproximación que podría eventualmente causar un cambio en antes que el dígito de la expansión. El algoritmo que acabo de mencionar se utiliza una desenfrenada búsqueda para encontrar un intervalo que excluye $r$, mientras que los primitivos métodos recursivos lo general no son capaces de realizar ilimitado de búsquedas.

En general, si nos fijamos en otros números de $\pi$, no está claro en todo lo que podríamos convertir un arbitrario de Cauchy de la secuencia de los racionales con un determinado módulo de convergencia en un decimal de expansión a través de un único proceso recursivo primitivo.

Por lo tanto, si la expansión decimal de $\pi$ es de hecho primitiva recursiva, algún otro método, o algunos adicionales (no trivial) información sobre el número de $\pi$ o de la secuencia de aproximaciones será necesario.