función construible
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 proporcionen 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 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 def ( n ) en tiempo O ( f ( n )) (en su lugar, se puede usar una representación unaria, ya que los dos pueden interconvertirse 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 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 después de exactamente f ( n ) pasos. [2] Esta definición es un poco menos general que las dos primeras pero, para la mayoría de las aplicaciones, se puede usar cualquiera de las dos 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 todos los 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 totalmente 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 f ( n ) comúnmente utilizadas (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.
