Saltar al contenido principal
Library homepage
 
LibreTexts Español

12.6: Estados de detención

  • 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.


    This page titled 12.6: Estados de detención is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .