12.6: Estados de detención

Última actualización
Guardar como PDF

Page ID: 103663

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Si bien hemos definido nuestras máquinas para que se detengan solo cuando no hay instrucción para llevar a cabo, las representaciones comunes de las máquinas Turing tienen un estado de detención dedicado\(h\),, tal que\(h \in Q\).

La idea detrás de un estado de detención es simple: cuando la máquina ha terminado de funcionar (está lista para aceptar entrada, o ha terminado de escribir la salida), entra en un estado\(h\) donde se detiene. Algunas máquinas tienen dos estados de detención, uno que acepta entrada y otro que rechaza entrada.

Ejemplo\(\PageIndex{1}\)

Estados de detención. Para dilucidar este concepto, comencemos con una alteración de la máquina par. En lugar de que la máquina se detenga en estado\(q_0\) si la entrada es pareja, podemos agregar una instrucción para enviar la máquina a un estado de detención.

12.6.1_evenhalt.png

Ampliemos aún más el ejemplo. Cuando la máquina determina que la entrada es impar, nunca se detiene. Podemos alterar la máquina para incluir un estado de rechazo reemplazando la instrucción de ciclo con una instrucción para pasar a un estado de rechazo\(r\).

12.6.2_incluso.png

Agregar un estado de detención dedicado puede ser ventajoso en casos como este, donde hace explícito cuando la máquina acepta/rechaza ciertas entradas. Sin embargo, es importante tener en cuenta que no se obtiene potencia informática al agregar un estado de detención dedicado. De igual manera, una noción menos formal de detener tiene sus propias ventajas. La definición de detención utilizada hasta ahora en este capítulo hace que la prueba del problema de la detención sea intuitiva y fácil de demostrar. Por ello, seguimos con nuestra definición original.