Task: Question Generation
Input (Spanish): El uso de un modelo computacional, como una máquina de Turing determinista, se hace necesario a la hora de obtener una definición más precisa de los que significa resolver un problema a partir de un tiempo y un espacio dado. El tiempo requerido por una máquina de Turing determinista M sobre una entrada x es el número total de cambios de estado o pasos que la máquina realiza antes de detenerse y generar una respuesta (sí o no). Se dice que una máquina de Turing M funciona con un tiempo f(n), si el tiempo requerido por M a lo largo de cada entrada n es como mucho f(n). Un problema de decisión puede resolverse en un tiempo f(n), si existe una máquina de Turing, funcionando en ese tiempo f(n), que resuelva el problema. Puesto que la teoría de la complejidad busca clasificar los problemas en función de su dificultad, se definen una serie de problemas en base a ciertos criterios. Por ejemplo, un conjunto de problemas que pueden resolverse dentro de un tiempo f(n) en una máquina de Turing determinista, se define como DTIME(f(n)).
Output (Spanish): ¿Cómo se define al conjunto de problemas que pueden resolverse dentro de un tiempo f(n) en una máquina de Turing determinista?