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 construirse a partir de n mediante una máquina de Turing en el tiempo de orden f ( n ). El propósito de tal definición es excluir funciones que no proporcionan un límite superior en el tiempo de ejecución de alguna máquina de Turing. [1]
Hay 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 consta de n unos, se detiene exactamente después de 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 O ( f ( n )) tiempo (una representación unaria se puede utilizar en su lugar, ya que los dos se pueden interconvertir en tiempo O ( f ( n )). [1]
También existe la noción de una función totalmente construible en el tiempo. Una función f se considera totalmente construible en el tiempo si existe una máquina de Turing M que, dada una cadena 1 n que consta de n unos, se detiene exactamente después de 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 definiciones. [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 O ( f ( n )) espacio. [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 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 finalmente sea 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 del tiempo . Son importantes porque el teorema de la jerarquía temporal se basa en las máquinas de Turing que deben determinar en el tiempo O ( f ( n )) si un algoritmo ha tomado más de f ( n ) pasos. Por supuesto, esto es imposible sin poder calcular f ( n ) en ese tiempo. Estos resultados suelen ser ciertos para todas las funciones naturales f pero no necesariamente ciertos para f 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 es verdadero. A menudo se utilizan funciones construibles en el tiempo para proporcionar dicha definición.
Las funciones construibles en el espacio se utilizan de manera similar, por ejemplo en el teorema de la jerarquía espacial .
Este artículo incorpora material de construible en PlanetMath , que tiene la licencia Creative Commons Attribution/Share-Alike License .
