Teorema de la jerarquía espacial en CS teórica

Question

Sipser tiene una prueba de este teorema que dice así:

$$D = \text{"On input } w$$

$$1. \text{Let } n \text{ be the length of } w$$

$$2. \text{Compute } f(n) \\ \text{using space constructibility and mark off this much tape. If later stages ever attempt to use more, } reject$$

$$3. \text{If } w \text{ is not of the form } <M>10^* \text{ for some TM } M, reject.$$

$$4. \text{Simulate } M \text{ on } w \text{ while counting the number of steps used in the simulate. If the count ever exceeds } 2^{f(n)}, reject\text{"}.$$

$$5. \text{If } M \text{ accepts,} reject. \text{If } M \text{ rejects}, accept.$$

Así que veo llegar a la contradicción si decimos que alguna Máquina de Turing $M$ decide la lengua $A$ la lengua que decida $D$ que se ejecuta en $o(f(n))$ espacio.

Pero ¿qué ocurre cuando se ejecuta $D$ sobre sí mismo . Doesn't $5$ ¿darte una contradicción? Si $D$ acepta, rechaza, y si $D$ rechaza, acepta. Entonces, ¿no se produciría una contradicción suponiendo que la siguiente TM $D$ es un decisor de $A$ ?

El teorema que intentamos demostrar es la jerarquía Espacio-Tiempo. Es decir, hay un Lenguaje A que se decide por TM $M$ $\in$ espacio (O(f(n)) pero no o(f(n)). véase: https://en.wikipedia.org/wiki/Space_hierarchy_theorem

ver: https://books.google.com/books? id=1aMKAAAAQBAJ&pg=PA364&lpg=PA364&dq=espacio+jerarquía+teorema+prueba+sipser&source=bl&ots=iDVTiKQedO&sig=ZVNVZ7Gkgp0y77FUcl66gvyTUfs&hl=es&sa=X&ved=0ahUKEwj81bbf4ZDLAhVFqB4KHabuCr44ChDoAQg7MAQ#v=onepage&q=espacio%20jerarquía%20teorema%20prueba%20sipser&f=false pág. 366

Answer 1

Intento averiguar a qué teorema te refieres; en cualquier caso, la respuesta que sigue sólo se basa en lo que escribiste en tu pregunta, es decir, el esquema de la demostración de este teorema, sin el enunciado correspondiente, que supongo que es el Teorema de la Hirerarquía Espacial ( Teorema 2 de estas notas ).

Si llega al paso 4, la entrada $w\in\{0,1\}^\ast$ es de la forma $w=\langle M \rangle x$ para alguna máquina de Turing válida $M$ y $x\in\in\{0,1\}^\ast$ .

A continuación, se ejecuta el paso 4 $M$ en $w$ dentro del límite de $t$ pasos temporales . Su pregunta es: ¿Y si $M=D$ ? . Pero esto sigue siendo válido: entonces se simula la ejecución de $M=D$ en la entrada $w$ . Su cuestión es "qué pasa si llegamos al Paso 5": pero eso no ocurrirá.

En el paso 4, se simula $D$ en $w$ que cuesta un cierto número de pasos. Luego, en la simulación, también se empieza a simular (dentro de la simulación) otra ejecución de $D$ en $w$ etc. En cada una de estas "subsimulaciones", cuyo inicio cuesta al menos unos pasos de tiempo en la ejecución original de $D$ se inicia una nueva simulación en el paso 4.

En otros términos, el paso 4 provoca (la primera ejecución de) $D$ al bucle. Así, el paso 4 de la "simulación original" se quedará sin tiempo (alcanzará el límite $t$ ) y rechazar. Nada llega nunca al paso 5.