#LyX 2.3 created this file. For more info see http://www.lyx.org/ \lyxformat 544 \begin_document \begin_header \save_transient_properties true \origin unavailable \textclass book \begin_preamble \input{../defs} \usepackage[x11names, svgnames, rgb]{xcolor} \usepackage[utf8]{inputenc} \usepackage{tikz} \usetikzlibrary{snakes,arrows,shapes} \end_preamble \use_default_options true \maintain_unincluded_children false \language spanish \language_package default \inputencoding auto \fontencoding global \font_roman "default" "default" \font_sans "default" "default" \font_typewriter "default" "default" \font_math "auto" "auto" \font_default_family default \use_non_tex_fonts false \font_sc false \font_osf false \font_sf_scale 100 100 \font_tt_scale 100 100 \use_microtype false \use_dash_ligatures true \graphics default \default_output_format default \output_sync 0 \bibtex_command default \index_command default \paperfontsize default \spacing single \use_hyperref false \papersize default \use_geometry false \use_package amsmath 1 \use_package amssymb 1 \use_package cancel 1 \use_package esint 1 \use_package mathdots 1 \use_package mathtools 1 \use_package mhchem 1 \use_package stackrel 1 \use_package stmaryrd 1 \use_package undertilde 1 \cite_engine basic \cite_engine_type default \biblio_style plain \use_bibtopic false \use_indices false \paperorientation portrait \suppress_date false \justification true \use_refstyle 1 \use_minted 0 \index Index \shortcut idx \color #008000 \end_index \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \paragraph_indentation default \is_math_indent 0 \math_numbering_side default \quotes_style french \dynamic_quotes 0 \papercolumns 1 \papersides 1 \paperpagestyle default \tracking_changes false \output_changes false \html_math_output 0 \html_css_as_file 0 \html_be_strict false \end_header \begin_body \begin_layout Standard En 1928, David Hilbert planteó el \series bold problema de decisión \series default o \series bold \emph on \lang ngerman Entscheidungsproblem \series default \emph default \lang spanish , consistente en encontrar un proceso mecánico para determinar, en una cantidad finita de pasos, si una proposición lógica de primer orden es un teorema o no. Hilbert asumía que tal proceso existía, pero en 1936, Alonzo Church en \lang english Princeton \lang spanish y Alan Turing en \lang english Cambridge \lang spanish probaron, de forma independiente, que no. Para ello tuvieron que definir formalmente este tipo de procesos, llamados algoritmos, Church a partir de su \series bold cálculo \series default \begin_inset Formula $\lambda$ \end_inset , un lenguaje formal para escribir funciones computables, y Turing a partir de sus \series bold \emph on \lang english computing machines \series default \emph default \lang spanish o \series bold máquinas de Turing \series default , una extensión de los autómatas de pila que permite moverse a través de la memoria. \end_layout \begin_layout Section Máquinas de Turing \end_layout \begin_layout Standard Un \series bold modelo de computación \series default \begin_inset Formula $\text{MOD}$ \end_inset es una clase de autómatas en la que cada uno tiene asociado un alfabeto \begin_inset Formula $\Sigma$ \end_inset y dos conjuntos disjuntos \begin_inset Formula $L_{\text{A}},L_{\text{R}}\in\Sigma^{*}$ \end_inset de cadenas que \series bold acepta \series default y que \series bold rechaza \series default , respectivamente. \end_layout \begin_layout Standard Una \series bold máquina de Turing \series default (MT) es una tupla \begin_inset Formula ${\cal M}=(Q,\Sigma,\Gamma,\delta,q_{0},q_{\text{F}})$ \end_inset formada por un conjunto finito de \series bold estados \series default \begin_inset Formula $Q$ \end_inset , un alfabeto de la \series bold entrada \series default \begin_inset Formula $\Sigma$ \end_inset que no contiene al \series bold símbolo blanco \series default \begin_inset Formula $\text{B}$ \end_inset , un alfabeto de la \series bold cinta \series default \begin_inset Formula $\Gamma\supseteq\Sigma\cup\{\text{B}\}$ \end_inset , una \series bold función de transición \series default \begin_inset Formula $\delta:D\subseteq(Q\times\Gamma)\to Q\times\Gamma\times\{\text{L},\text{R}\}$ \end_inset , un \series bold estado inicial \series default \begin_inset Formula $q_{0}$ \end_inset y un \series bold estado final \series default o \series bold de aceptación \series default \begin_inset Formula $q_{\text{F}}$ \end_inset . La representación gráfica es similar a la de una PDA, representando una transición \begin_inset Formula $\delta(q,x)=(r,y,d)$ \end_inset con la línea \begin_inset Quotes cld \end_inset \begin_inset Formula $x:y,d$ \end_inset \begin_inset Quotes crd \end_inset sobre una flecha de \begin_inset Formula $q$ \end_inset a \begin_inset Formula $r$ \end_inset . \end_layout \begin_layout Standard Una \series bold configuración \series default de \begin_inset Formula ${\cal M}$ \end_inset es una tupla \begin_inset Formula $(c,q,p)$ \end_inset formada por el \series bold contenido de la cinta \series default \begin_inset Formula $c\in\Gamma^{\mathbb{N}}$ \end_inset , el \series bold estado actual \series default \begin_inset Formula $q\in Q$ \end_inset y la \series bold posición de la cabeza de lectura/escritura \series default \begin_inset Formula $p\in\mathbb{N}$ \end_inset , y tal que casi todos los \begin_inset Formula $c_{i}=\text{B}$ \end_inset . Podemos representar una configuración \begin_inset Formula $(c,q,p)$ \end_inset como \begin_inset Quotes cld \end_inset \begin_inset Formula $c_{0}\cdots c_{p-1}qc_{p}\cdots c_{n}$ \end_inset \begin_inset Quotes crd \end_inset , donde \begin_inset Formula $n\ge\max(\{n\mid c_{n}\neq\text{B}\}\cup\{p-1\})$ \end_inset . \end_layout \begin_layout Standard La \series bold configuración inicial \series default para una \begin_inset Formula $w\in\Sigma^{*}$ \end_inset es \begin_inset Formula $q_{0}w$ \end_inset . Sean \begin_inset Formula $a,b,c\in\Gamma$ \end_inset , \begin_inset Formula $u,v\in\Gamma^{*}$ \end_inset y \begin_inset Formula $q,r\in Q$ \end_inset , la configuración \begin_inset Formula $uaqbv$ \end_inset lleva a \begin_inset Formula $uqacv$ \end_inset si \begin_inset Formula $\delta(q,b)=(q,c,\text{L})$ \end_inset , y la configuración \begin_inset Formula $uqbv$ \end_inset lleva a \begin_inset Formula $ucqv$ \end_inset si \begin_inset Formula $\delta(q,c)=(q,c,\text{R})$ \end_inset . Una \series bold configuración final \series default , \series bold aceptante \series default o \series bold de aceptación \series default es una con estado \begin_inset Formula $q_{\text{F}}$ \end_inset . La secuencia de configuraciones de \begin_inset Formula $w$ \end_inset es la que empieza por su configuración inicial y, desde cada configuración no final, la siguiente es la configuración a la que esta lleva. Esta termina en la primera configuración final, en cuyo caso la MT \series bold acepta \series default \begin_inset Formula $w$ \end_inset , o la primera que no lleva a ninguna, en cuyo caso la MT \series bold rechaza \series default \begin_inset Formula $w$ \end_inset , y puede no terminar. \end_layout \begin_layout Standard Una versión equivalente termina solo cuando la configuración no lleva a ninguna otra, y entonces acepta la cadena si dicha configuración tiene un estado en un conjunto de estados finales \begin_inset Formula $F\subseteq Q$ \end_inset y la rechaza en otro caso. Otra tiene, en vez de \begin_inset Formula $q_{\text{F}}$ \end_inset , dos estados \begin_inset Formula $q_{\text{accept}}$ \end_inset y \begin_inset Formula $q_{\text{reject}}$ \end_inset , de modo que \begin_inset Formula $\delta:Q\times\Gamma\to Q\times\Gamma\times\{\text{L},\text{R}\}$ \end_inset es total y la MT termina aceptando si llega a \begin_inset Formula $q_{\text{accept}}$ \end_inset o rechazando si termina en \begin_inset Formula $q_{\text{reject}}$ \end_inset . Otra variación equivalente, compatible con las otras, consiste en tener una cinta que se extiende infinitamente a ambos lados, no solo a uno, con lo que si \begin_inset Formula $\delta(q,b)=(q,c,\text{L})$ \end_inset , la configuración \begin_inset Formula $qbv$ \end_inset lleva a \begin_inset Formula $q\text{B}cv$ \end_inset . \end_layout \begin_layout Standard Es común describir una MT de forma algorítmica, con instrucciones de más alto nivel, pudiendo usar una instrucción de alto nivel si se puede implementar en una MT. Son instrucciones de alto nivel: \end_layout \begin_layout Enumerate Una secuencia de instrucciones. \end_layout \begin_deeper \begin_layout Standard Para terminar una instrucción, se establece el estado al de inicio de la siguiente. \end_layout \end_deeper \begin_layout Enumerate Moverse sin escribir. \end_layout \begin_deeper \begin_layout Standard Se escribe lo mismo que se leyó. \end_layout \end_deeper \begin_layout Enumerate Escribir un símbolo y quedarse en la misma posición. \end_layout \begin_deeper \begin_layout Standard Escribir y moverse a la derecha, luego moverse incondicionalmente a la izquierda. \end_layout \end_deeper \begin_layout Enumerate Ejecutar una u otra instrucción, o ninguna, según el símbolo leído. \end_layout \begin_deeper \begin_layout Standard Para estos símbolos, se mueve al inicio de la instrucción correspondiente, que termina en el inicio de la siguiente. Para los que no se hace ninguna, se pasa directamente al inicio de la siguiente. \end_layout \end_deeper \begin_layout Enumerate Ejecutar una u otra instrucción según el símbolo leído y los \begin_inset Formula $n$ \end_inset anteriores para \begin_inset Formula $n$ \end_inset fijo. \end_layout \begin_deeper \begin_layout Standard Se mueve \begin_inset Formula $n$ \end_inset veces a la izquierda. Si se lee \begin_inset Formula $x_{1}$ \end_inset , se mueve a la derecha y se pasa a un cierto estado \begin_inset Formula $\overline{x_{1}}$ \end_inset , desde el que si se lee \begin_inset Formula $x_{2}$ \end_inset , se mueve a la derecha y se pasa a \begin_inset Formula $\overline{x_{1}x_{2}}$ \end_inset , etc., hasta llegar al estado \begin_inset Formula $\overline{x_{1}\cdots x_{n}}$ \end_inset . \end_layout \end_deeper \begin_layout Enumerate Ejecutar una instrucción mientras el símbolo leído cumpla una condición. \end_layout \begin_deeper \begin_layout Standard Para estos símbolos, pasar a la instrucción, que al terminar vuelve a la comprobación. Para el resto, pasar a la siguiente. \end_layout \end_deeper \begin_layout Enumerate Detectar el límite izquierdo de la cinta. \end_layout \begin_deeper \begin_layout Standard Se añade un nuevo estado inicial \begin_inset Formula $q_{\text{i}}$ \end_inset y el símbolo \begin_inset Formula $\$$ \end_inset al alfabeto de la cinta. Desde \begin_inset Formula $q_{\text{i}}$ \end_inset se escribe \begin_inset Formula $\$$ \end_inset y, en bucle, se mueve a la derecha y se escribe el símbolo de la posición anterior, hasta que este sea B. Entonces se va moviendo a la izquierda hasta encontrar \begin_inset Formula $\$$ \end_inset , y luego una posición a la derecha y se pasa a \begin_inset Formula $q_{0}$ \end_inset . Esto mueve la cadena una posición a la derecha y escribe \begin_inset Formula $\$$ \end_inset al principio, con lo que detectar el límite izquierdo de la cinta es detectar \begin_inset Formula $\$$ \end_inset . \end_layout \end_deeper \begin_layout Enumerate Volver al principio de la cinta. \end_layout \begin_deeper \begin_layout Standard Una vez hecho lo anterior, ir a la izquierda hasta que se lea \begin_inset Formula $\$$ \end_inset . \end_layout \end_deeper \begin_layout Enumerate Recorrer una cadena detectando una de cada \begin_inset Formula $n\in\mathbb{N}^{*}$ \end_inset apariciones de un cierto símbolo. \end_layout \begin_deeper \begin_layout Standard Se usan \begin_inset Formula $n$ \end_inset estados en ciclo. Mientras no se lea B, se pasa al estado siguiente si se lee el símbolo o al mismo en otro caso, y se mueve a la derecha. En el último estado, antes de hacer esto, se detecta si está el símbolo y se actúa en consecuencia. \end_layout \end_deeper \begin_layout Enumerate Ejecutar una instrucción u otra según el número de apariciones de cierto símbolo módulo un \begin_inset Formula $n\in\mathbb{N}^{*}$ \end_inset fijo. \end_layout \begin_deeper \begin_layout Standard Se hace un ciclo como el anterior y, cuando se lee B, se ejecuta una u otra instrucción según el estado. \end_layout \end_deeper \begin_layout Enumerate Contar el número de apariciones de un cierto símbolo hasta un límite \begin_inset Formula $n$ \end_inset . \end_layout \begin_deeper \begin_layout Standard Se usan los estados \begin_inset Formula $c_{0},\dots,c_{n}$ \end_inset en ciclo. En \begin_inset Formula $c_{i}$ \end_inset , si se lee B, se realiza la acción para \begin_inset Formula $i$ \end_inset apariciones; si se lee el símbolo, se pasa a \begin_inset Formula $c_{i+1}$ \end_inset y se mueve a la derecha o, si \begin_inset Formula $i=n$ \end_inset , se ejecuta la acción para más de \begin_inset Formula $n$ \end_inset apariciones; en otro caso se mueve a la derecha. \end_layout \end_deeper \begin_layout Section Tesis de Church-Turing \end_layout \begin_layout Standard Un modelo de computación \begin_inset Formula $\text{MOD}$ \end_inset \series bold decide \series default un lenguaje \begin_inset Formula $L$ \end_inset si existe un \begin_inset Formula ${\cal M}\in\text{MOD}$ \end_inset con \begin_inset Formula $L_{\text{A}}=L$ \end_inset y \begin_inset Formula $L_{\text{R}}=\overline{L}$ \end_inset , y \series bold enumera \series default \begin_inset Formula $L$ \end_inset si existe un \begin_inset Formula ${\cal M}\in\text{MOD}$ \end_inset con \begin_inset Formula $L_{\text{R}}=\overline{L}$ \end_inset . Claramente \begin_inset Formula $\text{MOD}$ \end_inset enumera todas las cadenas que decide. \end_layout \begin_layout Standard Dados dos modelos de computación \begin_inset Formula $\text{MOD}_{1}$ \end_inset y \begin_inset Formula $\text{MOD}_{2}$ \end_inset , \begin_inset Formula $\text{MOD}_{1}$ \end_inset es \series bold menos expresivo \series default que \begin_inset Formula $\text{MOD}_{2}$ \end_inset , \begin_inset Formula $\text{MOD}_{1}\preceq\text{MOD}_{2}$ \end_inset , si \begin_inset Formula $\text{MOD}_{2}$ \end_inset enumera todo lenguaje enumerado por \begin_inset Formula $\text{MOD}_{1}$ \end_inset y decide todo lenguaje decidido por \begin_inset Formula $\text{MOD}_{1}$ \end_inset , en cuyo caso es \series bold equivalente \series default a \begin_inset Formula $\text{MOD}_{2}$ \end_inset , \begin_inset Formula $\text{MOD}_{1}\equiv\text{MOD}_{2}$ \end_inset , si \begin_inset Formula $\text{MOD}_{2}\preceq\text{MOD}_{1}$ \end_inset , y \series bold estrictamente menos expresivo \series default que \begin_inset Formula $\text{MOD}_{2}$ \end_inset , \begin_inset Formula $\text{MOD}_{1}\prec\text{MOD}_{2}$ \end_inset , en otro caso. \end_layout \begin_layout Standard Son equivalentes a \begin_inset Formula $\text{MT}$ \end_inset : \end_layout \begin_layout Enumerate Las \series bold máquinas de Turing con \emph on \lang english stay \series default \emph default \lang spanish ( \begin_inset Formula $\text{SMT}$ \end_inset ), como las \begin_inset Formula $\text{MT}$ \end_inset pero con función de transición de la forma \begin_inset Formula $\delta:Q\times\Gamma\to Q\times\Gamma\times\{\text{L},\text{R},\text{S}\}$ \end_inset , donde S corresponde a no moverse en la cinta, es decir, si \begin_inset Formula $q,r\in Q$ \end_inset , \begin_inset Formula $a,b\in\Gamma$ \end_inset , \begin_inset Formula $u\in\Gamma^{*}$ \end_inset y \begin_inset Formula $v\in\Gamma^{\mathbb{N}}$ \end_inset , \begin_inset Formula $uqav$ \end_inset lleva a \begin_inset Formula $urbv$ \end_inset si \begin_inset Formula $\delta(q,a)=(r,b,\text{S})$ \end_inset . \end_layout \begin_deeper \begin_layout Standard \begin_inset Formula $\text{MT}\subseteq\text{SMT}$ \end_inset , y toda \begin_inset Formula $\text{SMT}$ \end_inset se puede convertir en una \begin_inset Formula $\text{MT}$ \end_inset cambiando cada transición con S por una que primero se mueve a la derecha y luego a la izquierda. \end_layout \end_deeper \begin_layout Enumerate Las \series bold máquinas de Turing con \emph on \lang english return \series default \emph default \lang spanish ( \begin_inset Formula $\text{RMT}$ \end_inset ), como las \begin_inset Formula $\text{MT}$ \end_inset pero con función de transición de la forma \begin_inset Formula $\delta:Q\times\Gamma\to Q\times\Gamma\times\{\text{E},\text{R}\}$ \end_inset , donde E corresponde a volver al principio de la cinta, es decir, si \begin_inset Formula $q,r\in Q$ \end_inset , \begin_inset Formula $a,b\in\Gamma$ \end_inset , \begin_inset Formula $u\in\Gamma^{*}$ \end_inset y \begin_inset Formula $v\in\Gamma^{\mathbb{N}}$ \end_inset , \begin_inset Formula $uqav$ \end_inset lleva a \begin_inset Formula $rubv$ \end_inset si \begin_inset Formula $\delta(q,a)=(r,u,\text{E})$ \end_inset . \begin_inset Note Comment status open \begin_layout Plain Layout Sabemos que en las \begin_inset Formula $\text{MT}$ \end_inset es posible volver al principio de la cinta. Para lo contrario, añadimos símbolos \begin_inset Formula $\#$ \end_inset y \begin_inset Formula $\$$ \end_inset al alfabeto de la cinta de modo que, para simular una transición \begin_inset Formula $\delta(q,a)=(r,b,\text{L})$ \end_inset , primero guardamos \begin_inset Formula $a$ \end_inset como parte del estado (añadiendo \begin_inset Formula $|\Gamma|$ \end_inset estados), lo cambiamos por \begin_inset Formula $\#$ \end_inset y vamos al principio. Si en el principio leemos \begin_inset Formula $\#$ \end_inset , rechazamos (no podemos ir a la izquierda); si en la posición 1 leemos \begin_inset Formula $\#$ \end_inset , lo cambiamos por el valor guardado, vamos al principio de la cinta y pasamos a \begin_inset Formula $r$ \end_inset ; en otro caso, vamos al principio de la cinta, guardamos el símbolo leído en el estado, lo cambiamos por \begin_inset Formula $\$$ \end_inset volviendo al principio de la cinta y ejecutamos lo siguiente en bucle: moverse hasta encontrar \begin_inset Formula $\$$ \end_inset , moverse 2 posiciones a la derecha, y entonces, si se lee \begin_inset Formula $\#$ \end_inset , cambiarlo por el valor guardado y volver al principio, moverse hasta encontrar \begin_inset Formula $\$$ \end_inset , cambiarlo por el valor guardado y moverse a la derecha pasando a \begin_inset Formula $r$ \end_inset , y en otro caso volver al principio, moverse hasta encontrar \begin_inset Formula $\$$ \end_inset , cambiarlo por el valor guardado y moverse a la derecha, guardar el valor en esa posición y cambiarlo por \begin_inset Formula $\$$ \end_inset volviendo al principio. \end_layout \end_inset \end_layout \begin_layout Enumerate Las \series bold máquinas de Turing multicinta \series default , \begin_inset Formula $k\text{-MT}$ \end_inset para cierto \begin_inset Formula $k\in\mathbb{N}^{*}$ \end_inset , como las \begin_inset Formula $\text{MT}$ \end_inset pero con función de transición \begin_inset Formula $\delta:Q\times\Gamma^{k}\to Q\times(\Gamma\times\{\text{L},\text{R}\})^{k}$ \end_inset y configuraciones en \begin_inset Formula $Q\times(\Gamma^{\mathbb{N}}\times\mathbb{N})^{k}$ \end_inset , de modo que hay \begin_inset Formula $k$ \end_inset cintas cada una con su propio lector independiente y en cada transición se puede escribir y mover en cada una de las cintas. La configuración inicial para una entrada \begin_inset Formula $w\in\Sigma^{*}$ \end_inset es \begin_inset Formula $(q_{0},(w\text{B}\cdots,0),(\text{B}\cdots,0)^{k-1})$ \end_inset . Una configuración \begin_inset Formula $(q,(u_{1},n_{1}),\dots,(u_{k},n_{k}))$ \end_inset lleva a otra \begin_inset Formula $(r,(v_{1},m_{1}),\dots,(v_{k},m_{k}))$ \end_inset si, siendo \begin_inset Formula $\delta(q,u_{1n_{1}},\dots,u_{kn_{k}})=(r,(c_{1},d_{1}),\dots,(c_{k},d_{k}))$ \end_inset , para \begin_inset Formula $i\in\{1,\dots,k\}$ \end_inset , \begin_inset Formula $v_{i}$ \end_inset es como \begin_inset Formula $u_{i}$ \end_inset pero cambiando el término \begin_inset Formula $n_{i}$ \end_inset -ésimo por \begin_inset Formula $c$ \end_inset y, bien \begin_inset Formula $d_{i}=\text{L}$ \end_inset y \begin_inset Formula $m_{i}=n_{i}-1$ \end_inset , bien \begin_inset Formula $d_{i}=\text{R}$ \end_inset y \begin_inset Formula $m_{i}=n_{i}+1$ \end_inset . \end_layout \begin_deeper \begin_layout Standard Claramente una \begin_inset Formula $\text{MT}$ \end_inset puede ser simulada por una \begin_inset Formula $k\text{-MT}$ \end_inset que en todas las cintas salvo la primera simplemente se mueve a la derecha. Una \begin_inset Formula $k\text{-MT}$ \end_inset \begin_inset Formula $(Q,\Sigma,\Gamma,\delta,q_{0},q_{\text{F}})$ \end_inset puede ser simulada por una \begin_inset Formula $\text{MT}$ \end_inset con alfabeto de la cinta \begin_inset Formula $\Gamma\sqcup\Gamma\sqcup\{\#\}$ \end_inset , donde un símbolo \begin_inset Formula $x$ \end_inset del segundo \begin_inset Formula $\Gamma$ \end_inset lo representamos por \begin_inset Formula $\dot{x}$ \end_inset . La idea es que cada cinta con contenido \begin_inset Formula $u\text{B}\cdots$ \end_inset se representa por \begin_inset Formula $\#u$ \end_inset pero sustituyendo el símbolo \begin_inset Formula $x$ \end_inset apuntado en esa cinta por \begin_inset Formula $\dot{x}$ \end_inset . Al inicio, la \begin_inset Formula $\text{MT}$ \end_inset sustituye la entrada \begin_inset Formula $w$ \end_inset por \begin_inset Formula $\#\dot{w}_{1}w_{2}\cdots w_{|w|}(\#\dot{\text{B}})^{k-1}$ \end_inset , vuelve al principio y pasa a \begin_inset Formula $q_{0}$ \end_inset . En un estado \begin_inset Formula $q\in Q$ \end_inset , hace lo siguiente: \end_layout \begin_layout Enumerate Ir al principio e ir moviéndose a la derecha guardando en el estado las \begin_inset Formula $k$ \end_inset primeras apariciones de símbolos del segundo \begin_inset Formula $\Gamma$ \end_inset , \begin_inset Formula $\dot{a}_{1},\dots,\dot{a}_{k}$ \end_inset , volviendo al principio al llegar a la \begin_inset Formula $k$ \end_inset -ésima. \end_layout \begin_layout Enumerate Si \begin_inset Formula $\delta(q,a_{1},\dots,a_{k})=(r,(s_{1},d_{1}),\dots,(s_{k},d_{k}))$ \end_inset , para \begin_inset Formula $i$ \end_inset de 1 a \begin_inset Formula $k$ \end_inset : Mientras no se lea \begin_inset Formula $\#$ \end_inset , ir a la derecha. Mientras no se lea \begin_inset Formula $\dot{a}_{i}$ \end_inset , ir a la derecha. Cambiar \begin_inset Formula $\dot{a}_{i}$ \end_inset por \begin_inset Formula $s_{i}$ \end_inset . Si \begin_inset Formula $d_{i}=\text{L}$ \end_inset , ir a la izquierda, y si \begin_inset Formula $d_{i}=\text{R}$ \end_inset , ir a la derecha. Leer \begin_inset Formula $x$ \end_inset y cambiarlo por \begin_inset Formula $\dot{x}$ \end_inset , o si \begin_inset Formula $x=\#$ \end_inset , rechazar si \begin_inset Formula $d_{i}=\text{L}$ \end_inset o insertar antes \begin_inset Formula $\dot{\text{B}}$ \end_inset desplazando el resto a la derecha si \begin_inset Formula $d_{i}=\text{R}$ \end_inset . \end_layout \begin_layout Enumerate Pasar al estado \begin_inset Formula $r$ \end_inset . \end_layout \end_deeper \begin_layout Enumerate Las \series bold máquinas de Turing no deterministas \series default ( \begin_inset Formula $\text{MTND}$ \end_inset ), como las máquinas de Turing pero con función de transición \begin_inset Formula $\delta:Q\times\Gamma\to{\cal P}(Q\times\Gamma\times\{L,R\})$ \end_inset . Para \begin_inset Formula $a,b,c\in\Gamma$ \end_inset , \begin_inset Formula $u,v\in\Gamma^{*}$ \end_inset y \begin_inset Formula $q,r\in Q$ \end_inset , la configuración \begin_inset Formula $uaqbv$ \end_inset lleva a \begin_inset Formula $uqacv$ \end_inset si \begin_inset Formula $(q,c,\text{L})\in\delta(q,b)$ \end_inset , y la configuración \begin_inset Formula $uqbv$ \end_inset lleva a \begin_inset Formula $ucqv$ \end_inset si \begin_inset Formula $(q,c,r)\in\delta(q,c)$ \end_inset . La \begin_inset Formula $\text{MTND}$ \end_inset acepta una cadena \begin_inset Formula $w$ \end_inset si, de todas las secuencias de configuraciones que empiezan con la configuració n inicial para dicha cadena y cada configuración de la secuencia lleva a la siguiente, existe una finita que acaba en \begin_inset Formula $q_{\text{F}}$ \end_inset , y la rechaza si toda secuencia de este tipo es finita y no acaba en \begin_inset Formula $q_{\text{F}}$ \end_inset . \end_layout \begin_deeper \begin_layout Standard Toda \begin_inset Formula $\text{MT}$ \end_inset es equivalente a una \begin_inset Formula $\text{MTND}$ \end_inset con función de transición \begin_inset Formula $\delta'$ \end_inset dada por \begin_inset Formula $\delta'(q,a)=\{n\}$ \end_inset si \begin_inset Formula $(q,a)\in D$ \end_inset y \begin_inset Formula $\delta(q,a)=n$ \end_inset y \begin_inset Formula $\delta'(q,a)=\emptyset$ \end_inset si \begin_inset Formula $(q,a)\notin D$ \end_inset . Para el recíproco, consideramos una \begin_inset Formula $\text{MTND}$ \end_inset \begin_inset Formula $(Q,\Sigma,\Gamma,\delta,q_{0},q_{\text{F}})$ \end_inset y la convertimos en una 3-MT, que guardará la entrada en la cinta 1, simulará la \begin_inset Formula $\text{MTND}$ \end_inset en la cinta 2 recorriendo en anchura el árbol de posibilidades y guardará en la cinta 3 el camino actual en dicho árbol. Sea \begin_inset Formula $b\coloneqq\max_{q\in Q}^{a\in\Gamma}|\delta(q,a)|$ \end_inset , el alfabeto de la cinta será \begin_inset Formula $\Gamma\sqcup\{p_{1},\dots,p_{b}\}\sqcup\{\$,\#\}$ \end_inset , y hará lo siguiente: \end_layout \begin_layout Enumerate Escribir \begin_inset Formula $\$p_{1}$ \end_inset en la cinta 3 y guardar \begin_inset Formula $c\gets\text{FALSE}$ \end_inset en el estado. \end_layout \begin_layout Enumerate \begin_inset CommandInset label LatexCommand label name "enu:begin-step" \end_inset Copiar la cinta 1 en la 2, escribiendo \begin_inset Formula $\#$ \end_inset tras el final de la cadena, y volver al principio en ambas, usando \begin_inset Formula $\$$ \end_inset como marca de inicio. Guardar \begin_inset Formula $q\gets q_{0}$ \end_inset en el estado del 3-MT. \end_layout \begin_layout Enumerate Si \begin_inset Formula $q=q_{\text{F}}$ \end_inset , aceptar. Leer \begin_inset Formula $a$ \end_inset de la cinta 2 y \begin_inset Formula $p_{i}$ \end_inset de la 3. Si \begin_inset Formula $a=\#$ \end_inset , \begin_inset Formula $a\coloneqq\text{B}$ \end_inset , escribir B, ir a la derecha, escribir \begin_inset Formula $\#$ \end_inset e ir a la izquierda. Si \begin_inset Formula $p_{i}=\text{B}$ \end_inset , hacer \begin_inset Formula $c\gets\text{TRUE}$ \end_inset (indicando que existe una rama por la que se puede seguir si se da un paso más), moverse a la izquierda en la cinta 3 e ir al paso \begin_inset CommandInset ref LatexCommand ref reference "enu:next-step" plural "false" caps "false" noprefix "false" \end_inset . Si \begin_inset Formula $i>|\delta(q,a)|$ \end_inset , escribir B, moverse a la izquierda en la cinta 3 e ir al paso \begin_inset CommandInset ref LatexCommand ref reference "enu:next-step" plural "false" caps "false" noprefix "false" \end_inset . Si \begin_inset Formula $i\leq|\delta(q,a)|$ \end_inset , sea \begin_inset Formula $(r,b,d)$ \end_inset el \begin_inset Formula $i$ \end_inset -ésimo elemento de \begin_inset Formula $\delta(q,a)$ \end_inset , escribir \begin_inset Formula $b$ \end_inset en la cinta 2, moverla en la dirección \begin_inset Formula $d$ \end_inset , guardar \begin_inset Formula $q\coloneqq r$ \end_inset y, si se lee \begin_inset Formula $\$$ \end_inset , ir al paso \begin_inset CommandInset ref LatexCommand ref reference "enu:next-step" plural "false" caps "false" noprefix "false" \end_inset , y si no mover la cinta 3 a la derecha y repetir este paso. \end_layout \begin_layout Enumerate \begin_inset CommandInset label LatexCommand label name "enu:next-step" \end_inset Si en la cinta 3 se lee \begin_inset Formula $p_{b}$ \end_inset , escribir B, moverse a la izquierda y repetir este paso. Si se lee \begin_inset Formula $\$$ \end_inset , si \begin_inset Formula $c=\text{TRUE}$ \end_inset , hacer \begin_inset Formula $c\gets\text{FALSE}$ \end_inset , ir a la izquierda y escribir \begin_inset Formula $p_{1}$ \end_inset hasta que se lea B, sobrescribiendo la primera B, y si \begin_inset Formula $c=\text{FALSE}$ \end_inset , rechazar. Si se lee \begin_inset Formula $p_{i}$ \end_inset con \begin_inset Formula $i