En la 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]
Definiciones construibles en el tiempo
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 después de exactamente f ( n ) pasos para todo n ≥ n 0 . En la segunda definición, una función f se denomina 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 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 llama completamente 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 después de exactamente f ( n ) pasos. Esta definición es un poco menos general que las dos primeras pero, para la mayoría de las aplicaciones, se puede utilizar cualquiera de las dos definiciones [ cita requerida ] .
Definiciones construibles en el espacio
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 que 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 [ cita requerida ] .
Ejemplos de
Todas las funciones f ( n ) de uso comú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 toda la entrada. Sin embargo, es una función construible en el espacio.
Aplicaciones
Las funciones construibles en el tiempo se utilizan en los 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 O ( f ( n )) tiempo si un algoritmo ha dado más de f ( n ) pasos. Por supuesto, esto es imposible sin poder calcular f ( n ) en ese tiempo. Estos resultados son típicamente 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 que el teorema es verdadero. Las funciones construibles en el tiempo se utilizan a menudo para proporcionar tal 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 constructible en PlanetMath , que tiene la licencia Creative Commons Attribution / Share-Alike License .