funciones no construibles en el tiempo

Question

Una función de $T: \mathbb N \rightarrow \mathbb N$ es de tiempo edificable si $T(n) \geq n$ y hay un $TM$ $M$ que calcula la función de $x \mapsto \llcorner T(\vert x\vert) \lrcorner$ en el tiempo $T(n)$. ($\llcorner T(\vert x\vert) \lrcorner$ denota la representación binaria de el número de $T(\vert x\vert)$.)

Ejemplos de tiempo-construible las funciones son $n$, $nlogn$, $n^2$, $2^n$. Tiempo de límites que no son tiempo edificable puede conducir a resultados anómalos.

--Arora, Barak.

Esta es la definición de tiempo-edificable funciones en Complejidad Computacional - Un Enfoque Moderno por Sanjeev Arora y Booz Barak.

Es difícil encontrar ejemplos válidos de la no-tiempo-edificable funciones. $f(n)=c$ es un ejemplo de un no-tiempo-edificable de la función. Lo que más (sofisticado) ejemplos están ahí fuera?

Answer 1

Puede usar el teorema de jerarquía de tiempo para crear un contraejemplo.

Usted sabe por THT que DTIME ($n$)$\subsetneq$ DTIME ($n^2$), por lo tanto, elija un idioma que esté en DTIME ($n^2$)$\backslash$ DTIME ( $n$). Para este idioma, tiene una máquina de Turing$A$ que decide si una cadena está en el idioma en el tiempo$O(n^2)$ y$\omega(n)$. Ahora puede definir la siguiente función

$f(n) = 2\cdot n+A(n)$

Si es tiempo constructible, contradice el THT.

Answer 2

De acuerdo a la definición de Arora, funciones trigonométricas no son buenos ejemplos de lo contrario, ya que no son funciones de$\mathbb{N}$$\mathbb{N}$.

Sin embargo, la función de $TUC : \mathbb{N} \rightarrow \mathbb{N}$ definido por $TUC(n) = n$ si $M_n(n) \neq n$ $TUC(n) = 2n + 1$ lo contrario, no es tiempo-edificable:

Supongamos que existe $M$ que calcula el $TUC$ $TUC(n)$ del tiempo, entonces no existe $n$ tal que $M = M_n$ (cf. la codificación de una máquina de Turing en Arora del libro), pero

-si $TUC(n) = n$,$M(n) \neq n$, por lo que $TUC(n) \neq n$ $\rightarrow$ contradicción.

-si $TUC(n) = 2n +1 $,$M(n) = n$, por lo que $TUC(n) = n$ $\rightarrow$ contradicción.

Ambos casos a una contradicción, por lo $TUC$ no es tiempo-edificable.