Este es básicamente el Hartmanis-Stearns Conjetura, y es una de las principales pregunta abierta. La diferencia básica entre la pregunta y la Conjetura es, básicamente, una formalización de la "constante de tiempo". Ver
http://rjlipton.wordpress.com/2012/06/04/transcendental-aspects-of-turing-machines/y
http://rjlipton.wordpress.com/2012/06/15/why-the-hartmanis-stearns-conjecture-is-still-open/ para muchas discusiones sobre el tema.
En pocas palabras, la Hartmanis-Stearns Conjetura considera la complejidad de la computación de la siguiente dígito en la expansión decimal. En lugar de tomar $n$ como entrada y salida de la $n$-ésimo dígito (como se propone), la máquina imprime el decimal de expansión para siempre. El problema es que se debe imprimir los dígitos a una tasa constante. Esto se conoce como siendo computables en "tiempo real".
El HS Conjetura dice que cualquier número es racional o trascendental.
Echemos un vistazo a dos de sus reclamaciones.
Para cualquier número racional (y su forma decimal), de los costos de ti de la constante de tiempo para el cálculo de cifras;
La intuición detrás de esto es que cualquier número racional decimal de expansión es el tiempo de periódico. En otras palabras, no es un fijo prefijo, seguido por un patrón que se repite siempre. Así que a la salida de la $n$th dígitos, tenemos dos casos. Si $n$ está dentro de la inicial prefijo, se muestra el dígito (a partir de un pre-calculado de la tabla). De lo contrario, se calculan $n \bmod p$ y regresa el elemento de la repetición del patrón.
Por desgracia, esto no es técnicamente una "constante de tiempo". Tanto la comprobación de si $n$ está en el prefijo y la computación $n\bmod p$ requieren de tiempo $O(\log n)$ ya que tienes que leer a cada poco.
En el HS versión, la máquina puede recordar su ubicación entre los dígitos. Por lo tanto, sólo tiene que incrementar un puntero, ya sea moverse al siguiente punto en el pre-calculado de la tabla o pasar a la siguiente ubicación en el patrón de repetición. Estas son en realidad la constante de tiempo de las operaciones.
Por el contrario, dado un número, si los costos de la constante de tiempo para el cálculo de cifras, es un número racional.
De nuevo, nos encontramos tecnicismos de qué es exactamente constante de tiempo medio. En muchos razonable esquemas de codificación para $n$ (es decir, "little-endian" binario) este hecho implica la racionalidad.
Otras codificaciones (es decir, big-endian binario) ceder el paso trascendental números. Considerar el número cuyas $n$-ésimo dígito binario es 0 si el segundo bit en $n$ (escrito en big-endian binario) es 0. Este número está claro que no es periódica, ya que las pistas mantener el aumento en longitud, por lo que no es racional. De hecho, es en realidad trascendental.
Tenga en cuenta que el Hartmanis-Stearns conjetura no tiene la pretensión de que cada trascendental número puede ser impreso en tiempo real. No tengo un contra-ejemplo práctico (por favor dejar un comentario si lo hace!)
Otra cuestión es que el SA conjetura permite extremadamente complicados cálculos para algunos dígitos, siempre que están precedidos por una suficientemente largo trivial tramo. La conversión de la big-endian ejemplo anterior en el tiempo real, el formalismo, utiliza este truco, por ejemplo. Sin embargo, si miras el teorema como una declaración negativa sobre computación irrationals, entonces la brecha en realidad refuerza la conjetura (ya que más potencial de algoritmos son legales).
Otra manera de formalizar la constante de tiempo es la palabra modelo. En este modelo básico de operaciones con números enteros ($+$, $-$, $<$, $=$, etc) se considera constante de tiempo. No sé cuál es el estado de la conjetura es en ese modelo. (Punteros muy apreciado!)
