Sé que la raíz cuadrada de n es espacio-construible . No puedo demostrarlo con la definición de espacio-construible. ¿Cómo puedo demostrar que sólo $\sqrt{n}$ ¿se utiliza el espacio?
Respuesta
¿Demasiados anuncios?
Spiros
Puntos
171
La definición de funciones construibles en el espacio es la siguiente:
Una función $f$ es espacio-construible si existe un TM que, a la entrada $1^n$ , utiliza $\Theta(f(n)$ células del TM.
Puede haber versiones ligeramente diferentes de esta definición, pero la cuestión es que se puede demostrar que una función es espacio-construible simplemente construyendo una TM multi-cinta que la compute y utilice sólo $f(n)$ celdas en todas las cintas excepto en la cinta de entrada (porque siempre necesita $n$ para leer la entrada). Sin embargo, no se pueden escribir símbolos en la primera cinta: es de sólo lectura.
Así que para tu ejemplo, esa TM sería bastante fácil:
Tengamos un TM de 3 cintas que utiliza la primera cinta para la entrada, la segunda cinta comienza con la cadena "1" en ella y la tercera cinta se utiliza para la salida y está inicialmente en blanco Tenga en cuenta que yo calculo la función sólo en números naturales (así que vamos a suponer que $f(n) = \lceil \sqrt{n} \rceil$ ¡)!
Lees la cadena en tu segunda cinta y mueves el número apropiado de celdas de la cinta de entrada hacia la derecha. Si llegas al final de la segunda cinta, escribes "1" en tu tercera cinta de salida y te mueves hacia la derecha y restableces la posición en la segunda cinta. A continuación, comprueba el número de unos en la segunda cinta y en la tercera cinta. Si son iguales pero aún no has llegado al final de la entrada, tienes que continuar. Incrementa la cadena en tu segunda cinta y reinicia todo en tu tercera cinta.
Continúe hasta que llegue al final de la entrada. Usted puede ver fácilmente, que la tercera y segunda cinta finalmente tendrá la raíz cuadrada en ellos y usted no necesita más que $\lceil \sqrt{n} \rceil$ células.
Vamos a demostrarlo con un número $4$ ( $x$ marca la posición de la cabeza antes de la célula):
entrada: x1111 -> 1x111 -> espera comprobación -> x1111 -> 11x11 -> 1111x -> fin entrada
segundo: x1 -> 1x -> comprobar longitud e incremento-> x11 -> 11x -> comprobar y reajustar posición -> x11
tercero: xB -> 1x -> comprobar longitud y reiniciar-> xB -> 1x -> comprobar -> 11x -> comprobar longitud y FINALIZAR
Si el número no tiene raíz cuadrada natural, simplemente escribimos un 1 en la tercera cinta y lo emitimos. Espero que ahora esté claro.
