Función construible

En teoría de la complejidad , una función construible en tiempo es una función f de números naturales a números naturales con la propiedad de que f ( n ) puede ser construida a partir de n por una máquina de Turing en un tiempo de orden f ( n ). El propósito de esta definición es excluir funciones que no proporcionan una cota superior para el tiempo de ejecución de alguna máquina de Turing. ^{[ 1 ]}

Sea la máquina de Turing definida de la manera estándar, con un alfabeto que incluya los símbolos${\displaystyle 0,1}$Tiene una cinta de entrada estándar que contiene ceros, excepto una cadena de entrada.${\displaystyle 1^{n}}$denota una cadena compuesta de${\displaystyle n}$unos. Es decir, es la representación unaria de${\displaystyle n}$. Dejar${\displaystyle |n|}$sea ​​la representación binaria .

Una función${\displaystyle f}$Se dice que es construible en el tiempo si existe una máquina de Turing.${\displaystyle M}$de tal manera que el cálculo${\displaystyle M(1^{n})}$paradas en${\displaystyle O(f(n))}$pasos con valor${\displaystyle |f(n)|}$.

Esta definición puede utilizarse${\displaystyle M(1^{n})=1^{f(n)}}$en cambio, dado que los dos pueden interconvertirse en${\displaystyle O(f(n))}$pasos. ^{[ 1 ]}

Una función${\displaystyle f}$Se dice que es construible en el espacio si existe una máquina de Turing.${\displaystyle M}$de tal manera que${\displaystyle M(1^{n})}$paradas con valor${\displaystyle |f(n)|}$(o equivalentemente${\displaystyle 1^{f(n)}}$), mientras usa${\displaystyle O(f(n))}$espacio. ^{[ 1 ]}

De forma equivalente,${\displaystyle f}$Se dice que es construible en el espacio si existe una máquina de Turing.${\displaystyle M}$, de tal manera que para todos excepto un número finito de${\displaystyle n}$, el cálculo${\displaystyle M(1^{n})}$se detiene en una configuración en la que exactamente${\displaystyle f(n)}$Las celdas no están vacías y no se ha escrito en ninguna otra celda durante su operación. ^{[ 3 ] : Definición 2.4} A esto a veces se le llama "completamente construible en espacio". Sin embargo, las dos definiciones son equivalentes. ^{[ 3 ] : Teorema 2.7}

Todas las funciones de uso común (como${\displaystyle n,n^{2},2^{n},n!}$) son construibles en el tiempo y el espacio, siempre y cuando${\displaystyle f(n)=\Omega (n)}$La construcción es sencilla. Por ejemplo,${\displaystyle n^{2}}$se construye mediante un bucle for anidado, mientras que${\displaystyle n^{3}}$se construye mediante dos bucles for anidados, etc.

Si${\displaystyle f(n)=o(n)}$Si es construible en el tiempo, entonces eventualmente será constante, ya que de lo contrario no hay tiempo suficiente para leer toda la entrada.

${\displaystyle \ln n}$es construible en el espacio aunque${\displaystyle \ln n=o(n)}$.

Para cada función computable${\displaystyle f}$, existe una función computable${\displaystyle g}$eso es construible en el tiempo y${\displaystyle \forall n,g(n)>f(n)}$. ^{[ 3 ] : Lema 2.3}

Las funciones construibles en el tiempo se utilizan en resultados de la teoría de la complejidad, como el teorema de la jerarquía temporal . Son importantes porque este teorema se basa en máquinas de Turing que deben determinar en tiempo O ( f ( n )) si un algoritmo ha dado más de f ( n ) pasos. Esto, por supuesto, es imposible sin poder calcular f ( n ) en ese tiempo. Estos resultados suelen ser válidos para todas las funciones naturales f, pero no necesariamente para las funciones construidas artificialmente . Para formularlos con precisión, es necesario tener una definición precisa de una función natural f para la cual el teorema sea verdadero. Las funciones construibles en el tiempo se utilizan a menudo para proporcionar dicha definición.

Las funciones construibles en el espacio se utilizan de forma similar, por ejemplo, en el teorema de la jerarquía espacial .

Este artículo incorpora material de constructible en PlanetMath , que está bajo la licencia Creative Commons Attribution/Share-Alike License .