Cómo demostrar que la complejidad del espacio es en la mayoría de los casos complejidad

No, esto no funciona.

Sea M una máquina de Turing determinista y suponga que la entrada [math] \ sigma [/ math] es una entrada fuerte para M con un tamaño como máximo n.

Para cualquier cálculo hay una secuencia de configuraciones [matemática] C_0, C_1, \ ldots C_n [/ matemática] donde [matemática] C_0 [/ matemática] es la configuración inicial.

¿Por qué la secuencia de configuraciones tendría la misma longitud que la entrada (+1)? La secuencia de configuraciones puede ser de cualquier longitud, delimitada por [math] T_M (n) [/ math]. No como has afirmado, limitado por [matemáticas] n + 1 [/ matemáticas].

Observe que la ubicación más lejana alcanzada por el cabezal de lectura / escritura es el primer símbolo en blanco (es decir, el siguiente símbolo después del final de la cadena de entrada) en la posición [matemática] n + 1 [/ matemática].

No es verdad. Puede hacer una máquina de Turing que envíe el cabezal de lectura / escritura a cualquier distancia finita más allá del final de la entrada. Lo que sabemos aquí es que no va más allá de [math] S_M (n) [/ math].

Además, M puede detenerse en cualquier configuración [matemática] C_0, C_1, \ ldots C_n [/ matemática]. Al comparar tanto la complejidad del espacio en el tiempo, vemos que si M se detiene en cualquier configuración hasta el punto de ver el primer símbolo en blanco, tanto el espacio como el tiempo son iguales.

No necesariamente. Esto solo sería cierto si M solo se moviera a la derecha a lo largo de la entrada en cada paso de tiempo. Pero los cabezales de las máquinas Turing pueden moverse en ambos sentidos. Una máquina podría, por ejemplo, moverse a la mitad de la entrada, luego volver al inicio y detenerse. Tomando el doble de pasos de tiempo que los espacios de cinta.

Sin embargo, aunque la cabeza nunca puede avanzar más allá del primer símbolo en blanco, no puede detenerse antes o en este punto.

La primera parte no es cierta como ya dije, la segunda parte tampoco es cierta, puede detenerse en cualquier etapa.

Por lo tanto, el tiempo para el cálculo puede continuar indefinidamente, a pesar de que el espacio está limitado por [matemáticas] n + 1 [/ matemáticas].

El tiempo no está limitado, y el espacio no está limitado por n + 1, como he dicho.

La prueba correcta es como dijo Royce Peng. En cada paso de tiempo, la máquina puede usar como máximo un espacio nuevo que no haya usado antes. Entonces, en cada paso de tiempo, la cantidad de espacio utilizado permanece igual o aumenta en 1. Por lo tanto, la cantidad de espacio utilizado no puede aumentar más rápido que el tiempo, por lo que [math] S_M (n) \ leq T_M (n) [/ math ]

Cuando ejecuta M, en cada paso puede escribir en una sola celda. Entonces, al final del cálculo, el número de celdas en las que ha escrito no puede ser mayor que el número de pasos en el cálculo.