Definición de la función tiempo-edificable

Question

Lo que sería una idea intuitiva de tiempo-edificable funciones ? Hay una función que no es el momento-edificable?

En mis propias palabras diría que es una función del tiempo edificable cuando 1. es computable en un TM y 2. se calcula en el tiempo que a sí mismo se calcula. De modo que 2^n puede ser edificable si hay un TM cálculo de 2^n (para cualquier n) y el cálculo termina en más que 2^n tiempo (pasos, segundos, alguna otra medida de tiempo, etc.).

---

EDITAR:

Estoy leyendo el libro de CC por Arora y Barak. Me quedé atrapado en la página 16, donde el concepto de Tiempo-edificable funciones, que, en mis palabras, dice:

"Una función f de tiempo edificable cuando hay un TM que calcula el f en f(n) de tiempo."

Para mí, esto es acerca de la escritura de un programa (en TM) que calcula el valor de f(n) donde el cálculo de la misma no podrá exceder f(n) time que es el valor calculado por el TM. Así que hay algunos un poco complicado de auto-referencia.

Me gustaría saber donde la noción de tiempo y espacio de la complejidad, es decir, lo que es bueno, y algunos contraejemplo - alguna función que no es tiempo edificable. Esto ayudaría a comprender mejor el concepto, que a mí me parece que para ser realmente fundamental para todo el resto (en el libro).

---

Estoy teniendo dificultades para la comprensión de este concepto y sus racional, ya que es una especie de auto-referencial; se está definiendo a sí mismo por medio de su propia producción. Algunos ejemplos y contraejemplos que sería realmente útil. Gracias.

Answer 1

El uso básico de tiempo-constructibility (y el espacio-constructibility) es el reloj el tiempo una de las máquinas de carreras (o espacio de usa), es decir, queremos simular una máquina sólo para $t(n)$ pasos en una entrada de longitud $n$, sólo el uso de $O(t(n))$ pasos. Para ello, tenemos que calcular el valor de $t(n)$ en el tiempo $O(t(n))$. Si $t(n)$ no puede ser calculado en tiempo de $O(t(n))$ el tiempo total de ejecución de la simulación no se $O(n)$.

Un ejemplo es cuando queremos demostrar un teorema de la jerarquía. Necesitamos simular todas las máquinas de la más pequeña de la clase en el tiempo límite de la clase más grande.

No hay auto-referencia. Revisión de una función, por ejemplo,$n^2$. Esta es la función, no estamos hablando acerca de cómo se calcula. Ahora la pregunta es determinado $n$, queremos calcular el valor de $n^2$ (tanto de entrada como de salida en binario). ¿Cuál es la complejidad de este problema? Bueno, es $O(n^2)$. Por lo $n^2$ es de tiempo-edificable. La función de $n^2$ es utilizado dos veces (una vez como la función que queremos calcular, y una vez como el tiempo de la envolvente), pero no es una auto-referencia.

---

Actualización:

Hay una función que no es el momento-edificable?

Sí, hay. E. g. cualquier no-computable función no es tiempo edificable. Pero creo que te refieres son no computables funciones que no son de tiempo edificable? La respuesta está sí, pero dando ejemplos no es muy fácil porque la mayoría de las funciones que las que nos enfrentamos en la práctica resulta ser el tiempo edificable.