En teoría de la complejidad , una función construible en el 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 el tiempo de orden f ( n ). El propósito de tal definición es excluir funciones que no proporcionen un límite superior en el tiempo de ejecución de alguna máquina de Turing. [1]
Existen dos definiciones diferentes de una función construible en el tiempo. En la primera definición, una función f se llama construible en el tiempo si existe un entero positivo n 0 y una máquina de Turing M que, dada una cadena 1 n que consiste en n unos, se detiene después de exactamente f ( n ) pasos para todo n ≥ n 0 . En la segunda definición, una función f se llama construible en el tiempo si existe una máquina de Turing M que, dada una cadena 1 n , genera la representación binaria de f ( n ) en tiempo O ( f ( n )) (se puede usar una representación unaria en su lugar, ya que las dos se pueden interconvertir en tiempo O ( f ( n ))). [1]
También existe el concepto de función completamente construible en el tiempo. Una función f se denomina completamente construible en el tiempo si existe una máquina de Turing M que, dada una cadena 1 n formada por n unos, se detiene después de exactamente f ( n ) pasos. [2] Esta definición es ligeramente menos general que las dos primeras pero, para la mayoría de las aplicaciones, se puede utilizar cualquiera de las dos. [3]
De manera similar, una función f es construible en el espacio si existe un entero positivo n 0 y una máquina de Turing M que, dada una cadena 1 n que consta de n unos, se detiene después de usar exactamente f ( n ) celdas para todo n ≥ n 0 . De manera equivalente, una función f es construible en el espacio si existe una máquina de Turing M que, dada una cadena 1 n que consta de n unos, genera la representación binaria (o unaria) de f ( n ), mientras usa solo el espacio O ( f ( n )). [1]
Además, una función f es completamente construible en el espacio si existe una máquina de Turing M que, dada una cadena 1 n que consta de n unos, se detiene después de usar exactamente f ( n ) celdas. [2]
Todas las funciones comúnmente utilizadas f ( n ) (como n , n k , 2 n ) son construibles en el tiempo y en el espacio, siempre que f ( n ) sea al menos cn para una constante c > 0. Ninguna función que sea o ( n ) puede ser construible en el tiempo a menos que sea eventualmente constante, ya que no hay tiempo suficiente para leer la entrada completa. Sin embargo, es una función construible en el espacio.
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 el teorema de la jerarquía temporal 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 es, por supuesto, imposible sin poder calcular f ( n ) en ese tiempo. Tales resultados son típicamente ciertos para todas las funciones naturales f pero no necesariamente ciertos para f construida artificialmente . Para formularlos con precisión, es necesario tener una definición precisa para 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 jerarquía espacial .
Este artículo incorpora material de constructible en PlanetMath , que está licenciado bajo la Licencia Creative Commons Atribución/Compartir-Igual .
