From 8e44c44aff96736ab0d529c44cfcd5cfdac68dfa Mon Sep 17 00:00:00 2001 From: Juan Marin Noguera Date: Wed, 25 Jan 2023 12:53:51 +0100 Subject: Erratas MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Esta vez en algunas asignaturas no llegué a comprobar erratas: - En funcional a partir de 2.11 - En DSI - En conmutativa a partir de la enumeración antes del lema de Artin en 3.8 --- mc/n1.lyx | 25 +++-- mc/n2.1.dot | 4 +- mc/n2.1.tex | 4 +- mc/n2.lyx | 351 ++++++++++++++++++++++++++++-------------------------------- mc/n3.lyx | 200 ++++++++++++++-------------------- mc/n4.lyx | 37 +++---- mc/n5.lyx | 125 ++++++++++++---------- mc/n6.lyx | 39 ++----- mc/n7.lyx | 153 +++++++++++++------------- mc/n8.lyx | 88 ++++++++------- 10 files changed, 471 insertions(+), 555 deletions(-) (limited to 'mc') diff --git a/mc/n1.lyx b/mc/n1.lyx index 24a340a..7ca4884 100644 --- a/mc/n1.lyx +++ b/mc/n1.lyx @@ -103,7 +103,7 @@ cadena \end_inset es un elemento de -\begin_inset Formula $\Sigma^{*}\coloneqq \bigcup_{n\in\mathbb{N}}\Sigma^{n}$ +\begin_inset Formula $\Sigma^{*}\coloneqq\bigcup_{n\in\mathbb{N}}\Sigma^{n}$ \end_inset , que solemos escribir como @@ -136,7 +136,11 @@ concatenación \begin_inset Formula $\Sigma^{*}$ \end_inset - es un monoide con la concatenación de cadenas. + es un monoide con la concatenación de cadenas, y llamamos +\begin_inset Formula $\epsilon$ +\end_inset + + a su elemento neutro. Dada \begin_inset Formula $u=u_{1}\cdots u_{n}\in\Sigma^{*}$ \end_inset @@ -902,7 +906,7 @@ Para dibujar un NFA \begin_inset Formula $q\in Q$ \end_inset - con su etiqueta dentro, o un círculo doble si + con su etiqueta dentro, o un doble círculo si \begin_inset Formula $q\in F$ \end_inset @@ -966,7 +970,7 @@ También podemos representar un NFA con una tabla con un estado por fila, \begin_inset Formula $\epsilon$ \end_inset - cuyas celdas contienen los valores de la función de transición. +, cuyas celdas contienen los valores de la función de transición. \end_layout \begin_layout Section @@ -2154,7 +2158,7 @@ Demostración: es final. Finalmente, -\begin_inset Formula $L\cap M=\overline{\overline{L}\cap\overline{M}}$ +\begin_inset Formula $L\cap M=\overline{\overline{L}\cup\overline{M}}$ \end_inset y @@ -2248,7 +2252,7 @@ Demostración: \end_inset con -\begin_inset Formula $|w|\geq p$ +\begin_inset Formula $n\coloneqq|w|\geq p$ \end_inset y @@ -2259,7 +2263,8 @@ Demostración: \begin_inset Formula $q_{i+1}=\delta(q_{i},w_{i+1})$ \end_inset -, como +. + Como \begin_inset Formula $\{q_{0},\dots,q_{p}\}\subseteq Q$ \end_inset @@ -2293,7 +2298,7 @@ Demostración: \end_inset , -\begin_inset Formula $|y|\geq0$ +\begin_inset Formula $|y|>0$ \end_inset , @@ -2388,8 +2393,8 @@ pumping length \end_layout \begin_layout Standard -Los autómatas sencillos son demasiado sencillos como para teorizar sobre - lo computable o no computable debido a su falta de memoria. +Los autómatas finitos son demasiado sencillos para teorizar sobre lo computable + o no computable debido a su falta de memoria. \end_layout \end_body diff --git a/mc/n2.1.dot b/mc/n2.1.dot index c7c9b48..59eb2ff 100644 --- a/mc/n2.1.dot +++ b/mc/n2.1.dot @@ -5,8 +5,8 @@ digraph G { q4[shape=doublecircle, label=""] begin -> q1 q1 -> q2[label="e, e->$",texlbl="$\epsilon, \epsilon \to \$$"] - q2 -> q2[label="0, e->0",texlbl="$\begin{matrix}0, \epsilon \to 0\\1, \epsilon \to 1\\\ \end{matrix}$"] + q2 -> q2[label="0, e->#",texlbl="$0, \epsilon \to \#$"] q2 -> q3[label="c, e->e",texlbl="$c, \epsilon \to \epsilon$"] - q3 -> q3[label="0, 0->x",texlbl="$\begin{matrix}0, 0 \to \epsilon\\1, 1 \to \epsilon\\\ \end{matrix}$"] + q3 -> q3[label="1, #->e",texlbl="$1, \# \to \epsilon$"] q3 -> q4[label="e, $->e",texlbl="$\epsilon, \$ \to \epsilon$"] } diff --git a/mc/n2.1.tex b/mc/n2.1.tex index 3feb215..2a38805 100644 --- a/mc/n2.1.tex +++ b/mc/n2.1.tex @@ -9,13 +9,13 @@ \draw (120.6bp,29.5bp) node {$\epsilon, \epsilon \to \$$}; % Edge: q2 -> q2 \draw [->] (172.45bp,37.167bp) .. controls (169.37bp,47.664bp) and (172.76bp,58.0bp) .. (182.6bp,58.0bp) .. controls (189.06bp,58.0bp) and (192.74bp,53.549bp) .. (192.75bp,37.167bp); - \draw (182.6bp,65.5bp) node {$\begin{matrix}0, \epsilon \to 0\\1, \epsilon \to 1\\\ \end{matrix}$}; + \draw (182.6bp,65.5bp) node {$0, \epsilon \to \#$}; % Edge: q2 -> q3 \draw [->] (200.79bp,22.0bp) .. controls (220.49bp,22.0bp) and (253.02bp,22.0bp) .. (286.44bp,22.0bp); \draw (243.6bp,29.5bp) node {$c, \epsilon \to \epsilon$}; % Edge: q3 -> q3 \draw [->] (294.45bp,37.167bp) .. controls (291.37bp,47.664bp) and (294.76bp,58.0bp) .. (304.6bp,58.0bp) .. controls (311.06bp,58.0bp) and (314.74bp,53.549bp) .. (314.75bp,37.167bp); - \draw (304.6bp,65.5bp) node {$\begin{matrix}0, 0 \to \epsilon\\1, 1 \to \epsilon\\\ \end{matrix}$}; + \draw (304.6bp,65.5bp) node {$1, \# \to \epsilon$}; % Edge: q3 -> q4 \draw [->] (322.86bp,22.0bp) .. controls (342.7bp,22.0bp) and (375.68bp,22.0bp) .. (410.35bp,22.0bp); \draw (366.6bp,29.5bp) node {$\epsilon, \$ \to \epsilon$}; diff --git a/mc/n2.lyx b/mc/n2.lyx index 8d6a8db..d05fa25 100644 --- a/mc/n2.lyx +++ b/mc/n2.lyx @@ -196,7 +196,7 @@ PDA \series default ) es una tupla -\begin_inset Formula $(Q,\Sigma,\Gamma,\delta,A_{0},q_{0},F)$ +\begin_inset Formula $(Q,\Sigma,\Gamma,\delta,A_{0},q_{0})$ \end_inset similar a un PDA pero sin @@ -371,7 +371,8 @@ Podemos suponer que una transición añade o elimina más de un elemento de \begin_inset Formula $\delta:Q\times\Sigma_{\epsilon}\times\Gamma^{*})\to{\cal P}(Q\times\Gamma^{*})$ \end_inset -), lo que equivale a añadir algunos estados intermedios en la transición. +), lo que equivale a tener varios estados intermedios en la transición para + primero quitar elementos y luego añadir. \end_layout \begin_layout Standard @@ -544,31 +545,31 @@ GLC \begin_inset Formula $(V,\Sigma,{\cal R},S)$ \end_inset -, donde -\begin_inset Formula $\Sigma$ -\end_inset - - es un alfabeto de + formada por un \series bold -símbolos terminales +alfabeto de variables \series default -, + \begin_inset Formula $V$ \end_inset - es un alfabeto de +, un alfabeto de \series bold -variables +símbolos terminales \series default + +\begin_inset Formula $\Sigma$ +\end_inset + disjunto de \begin_inset Formula $V$ \end_inset -, +, un conjunto finito \begin_inset Formula ${\cal R}$ \end_inset - es un conjunto finito de + de \series bold reglas de producción \series default @@ -580,14 +581,14 @@ reglas de producción \begin_inset Formula $S\to w$ \end_inset -, y -\begin_inset Formula $S\in V$ -\end_inset - - es la +, y una \series bold variable inicial \series default + +\begin_inset Formula $S\in V$ +\end_inset + . Se puede representar con una línea por cada variable \begin_inset Formula $T\in V$ @@ -602,7 +603,7 @@ variable inicial \end_inset , donde -\begin_inset Formula $\{w_{1},\dots,w_{n}\}=\{w\mid(T,w)\in V\}$ +\begin_inset Formula $\{w_{1},\dots,w_{n}\}=\{w\mid(T,w)\in{\cal R}\}$ \end_inset . @@ -625,22 +626,6 @@ Dadas \begin_inset Formula $(R\to x)\in{\cal R}$ \end_inset -, y -\begin_inset Formula $v\Rightarrow^{*}w$ -\end_inset - - si -\begin_inset Formula $v=w$ -\end_inset - - o existe -\begin_inset Formula $x\in(V\cup\Sigma)^{*}$ -\end_inset - - tal que -\begin_inset Formula $v\Rightarrow x\Rightarrow^{*}w$ -\end_inset - . Una \series bold @@ -658,6 +643,18 @@ derivación \begin_inset Formula $v_{i}\Rightarrow v_{i+1}$ \end_inset +, y escribimos +\begin_inset Formula $v\Rightarrow w$ +\end_inset + + si existe una derivación que empieza por +\begin_inset Formula $v$ +\end_inset + + y termina por +\begin_inset Formula $w$ +\end_inset + . El \series bold @@ -709,8 +706,8 @@ Dada una GLC \begin_inset Formula $uRv\Rightarrow uxv$ \end_inset - en la derivación de -\begin_inset Formula $S$ + en la derivación +\begin_inset Formula $S\Rightarrow^{*}w$ \end_inset , aristas de @@ -726,7 +723,7 @@ Dada una GLC \series bold derivación por la izquierda \series default - es una derivación en la que, en cada paso + es una en la que, en cada paso \begin_inset Formula $uRv\Rightarrow uxv$ \end_inset @@ -805,7 +802,7 @@ Para{$A \backslash to \backslash -lambda +epsilon \backslash in{ \backslash @@ -818,7 +815,7 @@ cal R}$}{ \backslash to \backslash -varepsilon$ de ${ +epsilon$ de ${ \backslash cal R}$ \backslash @@ -859,16 +856,11 @@ cal R}$ para cada $w'$ resultante de \begin_layout Plain Layout - excepción de que si habíamos eliminado $B + excepción de que no añadimos $B \backslash to \backslash -lambda$ no la -\end_layout - -\begin_layout Plain Layout - - volvemos a añadir +epsilon$ \backslash ; \end_layout @@ -1234,17 +1226,21 @@ in F$}{% \begin_layout Plain Layout - añadir $(q_{ + añadir $q \backslash -text a}, +to^{ \backslash -epsilon)$ a $ +epsilon, \backslash -delta(q, +epsilon \backslash -epsilon, +to +\backslash +epsilon}q_{ \backslash -epsilon)$} +text a}$ a $ +\backslash +delta$} \end_layout \begin_layout Plain Layout @@ -1275,17 +1271,21 @@ Gamma$}{% \begin_layout Plain Layout - añadir $(q_{ + añadir $q_{ \backslash -text a}, +text a} \backslash -epsilon)$ a $ +to^{ \backslash -delta(q_{ +epsilon,x \backslash -text a}, +to +\backslash +epsilon}q_{ +\backslash +text a}$ a $ \backslash -epsilon,x)$} +delta$} \end_layout \begin_layout Plain Layout @@ -1532,19 +1532,23 @@ epsilon \begin_layout Plain Layout - (r,u) + p \backslash -in +to^{q, \backslash -delta(p,a, +epsilon \backslash -epsilon);(q, +to u}r,s \backslash -epsilon) +to^{b,u +\backslash +to +\backslash +epsilon}q \backslash in \backslash -delta(s,b,u)% +delta% \end_layout \begin_layout Plain Layout @@ -1624,18 +1628,10 @@ Nótese que sólo probamos \end_inset equivale al PDAD -\begin_inset Formula $(Q,\Sigma,\{\$\},\delta',\$,q_{0},F)$ -\end_inset - - con -\begin_inset Formula -\begin{align*} -\delta'(q,a\in\Sigma,\epsilon) & =\{(\delta(q,a),\epsilon)\}; & \delta'(q,a,x) & =\emptyset. -\end{align*} - +\begin_inset Formula $(Q,\Sigma,\{\$\},\{(q,a,\epsilon,\delta(q,a),\epsilon)\}_{q\in Q}^{a\in\Sigma},\$,q_{0},F)$ \end_inset -(En esta notación se usa la primera expresión aplicable, por columnas.) +. \end_layout \begin_layout Description @@ -1646,7 +1642,21 @@ Nótese que sólo probamos \begin_inset Formula $L=\{0^{n}c1^{n}\}_{n\in\mathbb{N}}$ \end_inset - no es un lenguaje regular. + es reconocido por el PDAD +\size small +de la figura +\begin_inset CommandInset ref +LatexCommand ref +reference "fig:pdad" +plural "false" +caps "false" +noprefix "false" + +\end_inset + + +\size default +, pero no es regular. Si lo fuera, tendría una \emph on \lang english @@ -1686,18 +1696,18 @@ pumping length \end_inset . - Sin embargo, -\begin_inset Formula $L$ -\end_inset - -, es reconocido por el -\size small -PDAD \end_layout \begin_deeper \begin_layout Standard \align center +\begin_inset Float figure +wide false +sideways false +status open + +\begin_layout Plain Layout +\align center \begin_inset ERT status open @@ -1732,6 +1742,33 @@ end{tikzpicture} \end_inset +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "fig:pdad" + +\end_inset + +PDAD de +\begin_inset Formula $\{0^{n}c1^{n}\}_{n\in\mathbb{N}}$ +\end_inset + +. +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + \end_layout \end_deeper @@ -1760,10 +1797,9 @@ end{tikzpicture} con \begin_inset Formula -\begin{align*} -\delta'(q_{\text{s}},\epsilon,\epsilon) & =\{(q_{0},A_{0})\}; & \delta'(q\in F,\epsilon,\epsilon) & =\delta(q,\epsilon,\epsilon)\cup\{(q_{\text{e}},\epsilon)\};\\ -\delta'(q_{\text{e}},\epsilon,x) & =\{(q_{\text{e}},\epsilon)\}; & \delta'(q\in Q,a,x) & =\delta(q,a,x); & \delta'(q,a,x) & =\emptyset. -\end{align*} +\[ +\delta'\coloneqq\delta\cup\{(q_{\text{s}},\epsilon,\epsilon,q_{0},A_{0})\}\cup\{(q,\epsilon,a,q_{\text{e}},\epsilon)\}_{q\in F\cup\{q_{\text{e}}\}}^{a\in\Gamma}. +\] \end_inset @@ -1922,10 +1958,9 @@ En efecto, si con \begin_inset Formula -\begin{align*} -\delta'(q_{\text{s}},\epsilon,\epsilon) & =\{(q_{0},A_{0})\}; & \delta'(q\in Q,a,x\in\Sigma\cup\{\epsilon\}) & =\delta(q,a,x);\\ -\delta'(q\in Q,\epsilon,\$) & =\{(q_{\text{e}},\epsilon)\}; & \delta'(q,a,x) & =\emptyset. -\end{align*} +\[ +\delta'\coloneqq\delta\cup\{(q_{\text{s}},\epsilon,\epsilon,q_{0},A_{0})\}\cup\{(q,\epsilon,\$,q_{\text{e}},\epsilon)\}_{q\in Q}. +\] \end_inset @@ -2056,7 +2091,7 @@ noprefix "false" , luego para que siempre que se acepte una cadena, se pueda aceptar con la pila vacía, y finalmente para que todas las transiciones añadan o eliminen - un elemento de la pila pero no ambos, usando estados intermedios. + un elemento de la pila pero no ambos. Entonces queremos ver que, para \begin_inset Formula $p,q\in Q$ \end_inset @@ -2385,10 +2420,9 @@ Si la secuencia de acciones tiene 0 pasos, debe ser de la forma con \begin_inset Formula -\begin{align*} -\delta(s,\epsilon,A_{0}) & =(l,A_{0}S); & \delta(l,\epsilon,x\in V) & =\{(l,w^{\text{R}})\}_{(x,w)\in{\cal R}};\\ -\delta(l,a,a) & =(l,\epsilon); & \delta(l,\epsilon,A_{0}) & =(e,\epsilon); & \delta(q,a,x) & =\emptyset -\end{align*} +\[ +\delta\coloneqq\{(s,\epsilon,A_{0},l,A_{0}S),(\ell,\epsilon,A_{0},e,\epsilon)\}\cup\{(\ell,a,a,\ell,\epsilon)\}_{a\in\Sigma}\cup\{(\ell,\epsilon,x,l,w^{\text{R}})\}_{(x,w)\in{\cal R}} +\] \end_inset @@ -2586,15 +2620,16 @@ Sean \series bold Lema del bombeo \series default - ( + o \series bold \emph on \lang english pumping lemma -\series default \emph default \lang spanish -): Si +: +\series default + Si \begin_inset Formula $L\in{\cal CF}$ \end_inset @@ -2647,11 +2682,11 @@ Demostración: \begin_inset Formula $b\coloneqq\max_{(A\to v)\in{\cal R}}|v|$ \end_inset -, en cualquier árbol de derivación por +, en cualquier árbol de derivación de \begin_inset Formula $G$ \end_inset -, ningún nodo tiene más de + ningún nodo tiene más de \begin_inset Formula $b$ \end_inset @@ -2700,7 +2735,7 @@ Demostración: \begin_inset Formula $w$ \end_inset - con número de nodos mínimo, cuya altura sera al menos + con número de nodos mínimo, cuya altura será al menos \begin_inset Formula $|V|+1$ \end_inset @@ -2834,7 +2869,7 @@ Demostración: \end_inset una descomposición en las condiciones de dicho lema. - Si o + Si \begin_inset Formula $v$ \end_inset @@ -2859,7 +2894,7 @@ Demostración: \end_inset contienen cada una un sólo tipo de símbolo y, como al menos una de las - 2 no es vacía y hay un tipo de símbolo no contenido en ninguna, + 2 no es vacía, hay un tipo de símbolo no contenido en ninguna, luego \begin_inset Formula $uv^{2}xy^{2}z\in L$ \end_inset @@ -2871,23 +2906,15 @@ Demostración: \end_layout \begin_layout Standard -Dados -\begin_inset Formula $L_{1},L_{2}\in{\cal CF}$ -\end_inset - -: -\end_layout - -\begin_layout Enumerate -\begin_inset Formula $L_{1}\cup L_{2}\in{\cal CF}$ +\begin_inset Formula ${\cal CF}$ \end_inset -. -\end_layout - -\begin_deeper -\begin_layout Standard -Dadas gramáticas + es cerrado para la unión, concatenación y clausura. + +\series bold +Demostración: +\series default + Dadas gramáticas \begin_inset Formula $(V_{1},\Sigma_{1},{\cal R}_{1},S_{1})$ \end_inset @@ -2937,19 +2964,7 @@ Dadas gramáticas \end_inset . -\end_layout - -\end_deeper -\begin_layout Enumerate -\begin_inset Formula $L_{1}L_{2}\in{\cal CF}$ -\end_inset - -. -\end_layout - -\begin_deeper -\begin_layout Standard -La gramática + \begin_inset Formula $G\coloneqq(V_{1}\sqcup V_{2}\sqcup\{S\},\Sigma_{1}\cup\Sigma_{2},{\cal R}_{1}\cup{\cal R}_{2}\cup\{S\to S_{1}S_{2}\},S)$ \end_inset @@ -3011,19 +3026,7 @@ La gramática \end_inset . -\end_layout - -\end_deeper -\begin_layout Enumerate -\begin_inset Formula $L_{1}^{*}\in{\cal CF}$ -\end_inset - -. -\end_layout - -\begin_deeper -\begin_layout Standard -La gramática + Finalmente, \begin_inset Formula $G\coloneqq(V_{1}\sqcup\{S\},\Sigma_{1},{\cal R}_{1}\cup\{S\to S_{1}S,S\to\epsilon\},S)$ \end_inset @@ -3104,17 +3107,16 @@ La gramática . \end_layout -\end_deeper -\begin_layout Enumerate -En general -\begin_inset Formula $L_{1}\cap L_{2}\notin{\cal CF}$ +\begin_layout Standard +\begin_inset Formula ${\cal CF}$ \end_inset -. -\end_layout - -\begin_deeper -\begin_layout Standard + no es cerrado para la intersección, el complemento y la diferencia. + +\series bold +Demostración: +\series default + \begin_inset Formula $L_{1}\coloneqq\{a^{n}b^{n}c^{m}\}_{n,m\in\mathbb{N}}$ \end_inset @@ -3153,49 +3155,18 @@ B & \to bBc\mid\epsilon \end_inset . -\end_layout - -\end_deeper -\begin_layout Enumerate -En general -\begin_inset Formula $\overline{L_{1}}\notin{\cal CF}$ -\end_inset - -. -\end_layout - -\begin_deeper -\begin_layout Standard -Si lo fuera, sería siempre -\begin_inset Formula $L_{1}\cap L_{2}=\overline{\overline{L_{1}}\cup\overline{L_{2}}}\in{\cal CF}\#$ -\end_inset - -. -\end_layout - -\end_deeper -\begin_layout Enumerate -En general -\begin_inset Formula $L_{1}\setminus L_{2}\notin{\cal CF}$ -\end_inset - -. -\end_layout - -\begin_deeper -\begin_layout Standard -Si lo fuera, como -\begin_inset Formula $\Sigma^{*}\in{\cal CF}$ + Si fuera cerrado para la diferencia, lo sería para el complemento ya que + +\begin_inset Formula $\overline{L}=\Sigma^{*}\setminus L$ \end_inset - sería siempre -\begin_inset Formula $\overline{L_{1}}=\Sigma^{*}\setminus L_{1}\in{\cal CF}$ +, y entonces lo sería para la intersección ya que +\begin_inset Formula $L_{1}\cap L_{2}=\overline{\overline{L_{1}}\cup\overline{L_{2}}}$ \end_inset . \end_layout -\end_deeper \begin_layout Standard Los autómatas de pila no son un buen modelo de computación, pues un ordenador puede reconocer si una cadena está en diff --git a/mc/n3.lyx b/mc/n3.lyx index 22fb847..e3663c0 100644 --- a/mc/n3.lyx +++ b/mc/n3.lyx @@ -111,8 +111,7 @@ 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 + algoritmos, Church a partir de su \series bold cálculo \series default @@ -312,37 +311,25 @@ posición de la cabeza de lectura/escritura . Podemos representar una configuración -\begin_inset Formula $(c_{0}\cdots c_{n}\text{BB}\cdots\text{B}\cdots,q,k)$ -\end_inset - -, donde -\begin_inset Formula $k\leq n$ -\end_inset - - y solo se da -\begin_inset Formula $c_{n}=\text{B}$ -\end_inset - - si -\begin_inset Formula $c_{j}=\text{B}$ -\end_inset - - para todo -\begin_inset Formula $c_{j}\geq k$ +\begin_inset Formula $(c,q,p)$ \end_inset -, como + como \begin_inset Quotes cld \end_inset -\begin_inset Formula $c_{0}\cdots c_{k-1}qc_{k}\cdots c_{n}$ +\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 @@ -356,19 +343,7 @@ configuración inicial \end_inset es -\begin_inset Formula $(c,q_{0},0)$ -\end_inset - - con -\begin_inset Formula $c_{0},\dots,c_{|w|-1}=w$ -\end_inset - - y -\begin_inset Formula $c_{k}=\text{B}$ -\end_inset - - para -\begin_inset Formula $k\geq|w|$ +\begin_inset Formula $q_{0}w$ \end_inset . @@ -448,7 +423,7 @@ rechaza \begin_inset Formula $w$ \end_inset -, o bien no termina. +, y puede no terminar. \end_layout \begin_layout Standard @@ -556,11 +531,11 @@ Ejecutar una u otra instrucción según el símbolo leído y los \begin_inset Formula $n$ \end_inset - anteriores para cierto + anteriores para \begin_inset Formula $n$ \end_inset -. + fijo. \end_layout \begin_deeper @@ -586,7 +561,7 @@ Se mueve \begin_inset Formula $\overline{x_{1}x_{2}}$ \end_inset -, etc., hasta llegar a la posición inicial en el estado +, etc., hasta llegar al estado \begin_inset Formula $\overline{x_{1}\cdots x_{n}}$ \end_inset @@ -600,7 +575,7 @@ Ejecutar una instrucción mientras el símbolo leído cumpla una condición. \begin_deeper \begin_layout Standard -Para estos símbolos, pasar a la instrucción, que termina volviendo a la +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 @@ -629,7 +604,7 @@ Se añade un nuevo estado inicial \begin_inset Formula $\$$ \end_inset - y, en bucle, se mueve a la derecha y se escribe el símbolo en la posición + 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 $\$$ @@ -644,7 +619,7 @@ Se añade un nuevo estado inicial \begin_inset Formula $\$$ \end_inset - al principio, de modo que detectar el límite izquierdo de la cinta es detectar + al principio, con lo que detectar el límite izquierdo de la cinta es detectar \begin_inset Formula $\$$ \end_inset @@ -684,12 +659,8 @@ Se usan 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, si se detecta el símbolo se hace - la acción a realizar cada -\begin_inset Formula $n$ -\end_inset - - apariciones. + 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 @@ -838,7 +809,7 @@ menos expresivo \begin_inset Formula $\text{MOD}_{1}$ \end_inset -; +, en cuyo caso es \series bold equivalente \series default @@ -851,10 +822,6 @@ equivalente \end_inset , si -\begin_inset Formula $\text{MOD}_{1}\preceq\text{MOD}_{2}$ -\end_inset - - y \begin_inset Formula $\text{MOD}_{2}\preceq\text{MOD}_{1}$ \end_inset @@ -870,15 +837,7 @@ estrictamente menos expresivo \begin_inset Formula $\text{MOD}_{1}\prec\text{MOD}_{2}$ \end_inset -, si -\begin_inset Formula $\text{MOD}_{1}\preceq\text{MOD}_{2}$ -\end_inset - - pero -\begin_inset Formula $\text{MOD}_{2}\npreceq\text{MOD}_{1}$ -\end_inset - -. +, en otro caso. \end_layout \begin_layout Standard @@ -944,7 +903,6 @@ stay \begin_deeper \begin_layout Standard -Claramente \begin_inset Formula $\text{MT}\subseteq\text{SMT}$ \end_inset @@ -956,7 +914,7 @@ Claramente \begin_inset Formula $\text{MT}$ \end_inset - sustituyendo una transición con S con una que primero se mueve a la derecha + cambiando cada transición con S por una que primero se mueve a la derecha y luego a la izquierda. \end_layout @@ -1136,60 +1094,56 @@ máquinas de Turing multicinta \end_inset es -\begin_inset Formula $(q_{0},w\text{B}\cdots,(\text{B}\cdots)^{k-1})$ +\begin_inset Formula $(q_{0},(w\text{B}\cdots,0),(\text{B}\cdots,0)^{k-1})$ \end_inset . - Definiendo -\begin_inset Formula $\nu:(\Gamma^{\mathbb{N}}\times\mathbb{N})\times(\Gamma\times\{\text{L},\text{R}\})\to\Gamma^{\mathbb{N}}\times\mathbb{N}$ -\end_inset - - de forma que, para -\begin_inset Formula $a,b\in\Gamma$ + Una configuración +\begin_inset Formula $(q,(u_{1},n_{1}),\dots,(u_{k},n_{k}))$ \end_inset -, -\begin_inset Formula $n\in\mathbb{N}$ + lleva a otra +\begin_inset Formula $(r,(v_{1},m_{1}),\dots,(v_{k},m_{k}))$ \end_inset -, -\begin_inset Formula $u\in\Gamma^{n}$ + 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 - y -\begin_inset Formula $v\in\Gamma^{\mathbb{N}}$ +, para +\begin_inset Formula $i\in\{1,\dots,k\}$ \end_inset , -\begin_inset Formula $\nu((uav,n),(b,\text{R}))=(ubv,n+1)$ +\begin_inset Formula $v_{i}$ \end_inset - y, si -\begin_inset Formula $n>0$ + es como +\begin_inset Formula $u_{i}$ \end_inset -, -\begin_inset Formula $\nu((uav,n),(b,\text{L}))=(ubv,n-1)$ + pero cambiando el término +\begin_inset Formula $n_{i}$ \end_inset -, una configuración -\begin_inset Formula $(q,(u_{1},n_{1}),\dots,(u_{k},n_{k}))$ +-ésimo por +\begin_inset Formula $c$ \end_inset - lleva a otra -\begin_inset Formula $(r,(v_{1},m_{1}),\dots,(v_{k},m_{k}))$ + y, bien +\begin_inset Formula $d_{i}=\text{L}$ \end_inset - dada por -\begin_inset Formula $\delta(q,u_{1n_{1}},u_{2n_{2}},\dots,u_{kn_{k}})=(r,t_{1},\dots,t_{k})$ + y +\begin_inset Formula $m_{i}=n_{i}-1$ \end_inset - y -\begin_inset Formula $(v_{i},m_{i})=\nu((u_{i},n_{i}),t_{i})$ +, bien +\begin_inset Formula $d_{i}=\text{R}$ \end_inset - para cada -\begin_inset Formula $i$ + y +\begin_inset Formula $m_{i}=n_{i}+1$ \end_inset . @@ -1261,7 +1215,7 @@ Claramente una \end_inset por -\begin_inset Formula $\#w(\#\dot{\text{B}})^{k-1}$ +\begin_inset Formula $\#\dot{w}_{1}w_{2}\cdots w_{|w|}(\#\dot{\text{B}})^{k-1}$ \end_inset , vuelve al principio y pasa a @@ -1325,7 +1279,7 @@ Si \end_inset por -\begin_inset Formula $a_{i}$ +\begin_inset Formula $s_{i}$ \end_inset . @@ -1346,6 +1300,22 @@ Si \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 @@ -1473,8 +1443,8 @@ Toda \begin_inset Formula $(Q,\Sigma,\Gamma,\delta,q_{0},q_{\text{F}})$ \end_inset - e intentamos convertirla en una 3-MT, que guardará la entrada en la cinta - 1, simulará la + y la convertimos en una 3-MT, que guardará la entrada en la cinta 1, simulará + la \begin_inset Formula $\text{MTND}$ \end_inset @@ -1500,7 +1470,7 @@ Escribir \begin_inset Formula $c\gets\text{FALSE}$ \end_inset -en el estado del 3-MT. + en el estado. \end_layout \begin_layout Enumerate @@ -1510,7 +1480,7 @@ name "enu:begin-step" \end_inset -Copiar la cinta 1 en la cinta 2, escribiendo +Copiar la cinta 1 en la 2, escribiendo \begin_inset Formula $\#$ \end_inset @@ -1578,7 +1548,7 @@ noprefix "false" \begin_inset Formula $i>|\delta(q,a)|$ \end_inset -, escribir B y moverse a la izquierda en la cinta 3 e ir al paso +, escribir B, moverse a la izquierda en la cinta 3 e ir al paso \begin_inset CommandInset ref LatexCommand ref reference "enu:next-step" @@ -1725,7 +1695,7 @@ Kurt Gödel tesis de Church-Turing \series default , que afirma que esta definición de algoritmo se corresponde con la noción - intuitiva, o la máquina de Turing es el modelo de computación más expresivo + intuitiva, o que la máquina de Turing es el modelo de computación más expresivo posible y todos los modelos suficientemente expresivos son equivalentes a este. \end_layout @@ -1744,12 +1714,12 @@ máquinas con infinitos registros \series bold lenguaje S \series default - (simple), todas equivalentes a las máquinas de Turing. + (simple), todas equivalentes a MT. Un lenguaje de programación es \series bold Turing completo \series default - si es equivalente a las máquinas de Turing. + si es equivalente a MT. \end_layout \begin_layout Section @@ -1820,7 +1790,6 @@ Si se lee B, rechazar (longitud 0). \begin_layout Enumerate Si solo hay un 0, se acepta. - Se vuelve al principio. \end_layout \begin_layout Enumerate @@ -1879,7 +1848,7 @@ Se va leyendo la cadena de izquierda a derecha y, si hay una \begin_inset Formula $c$ \end_inset -, aceptando si no hay ninguno, se vuelve al principio de la cinta, se marca +, aceptando si no hay ninguna, se vuelve al principio de la cinta, se marca con \begin_inset Formula $\#$ \end_inset @@ -2112,8 +2081,7 @@ Tomamos una \begin_inset Formula $\text{MTND}$ \end_inset - que al inicio, de forma no determinista, se quede donde está ejecute una - + que al inicio, de forma no determinista, ejecute una \begin_inset Formula $\text{MT}$ \end_inset @@ -2121,7 +2089,7 @@ Tomamos una \begin_inset Formula $L_{1}$ \end_inset - o una que ejecute + o una que enumere \begin_inset Formula $L_{2}$ \end_inset @@ -2154,11 +2122,7 @@ Sean \begin_inset Formula ${\cal M}_{2}$ \end_inset - una -\begin_inset Formula $\text{MT}$ -\end_inset - - que enumera + una que enumera \begin_inset Formula $L_{2}$ \end_inset @@ -2171,7 +2135,7 @@ Sean \end_inset a la vez sobre dos copias de la entrada (alternándolas), aceptando cuando - ambas hayan aceptado y rechazando si una termina. + ambas hayan aceptado y rechazando si una rechaza. \end_layout \end_deeper @@ -2200,11 +2164,11 @@ Similar al caso decidible pero haciendo todas las simulaciones en paralelo: \begin_deeper \begin_layout Standard -\begin_inset Formula $L_{1}^{*}=\{\lambda\}\cup(L_{1}\setminus\{\lambda\})^{*}$ +\begin_inset Formula $L_{1}^{*}=\{\epsilon\}\cup(L_{1}\setminus\{\epsilon\})^{*}$ \end_inset , por lo que si la entrada es -\begin_inset Formula $\lambda$ +\begin_inset Formula $\epsilon$ \end_inset aceptamos y, en otro caso, hacemos como en el caso anterior pero iterando @@ -2228,8 +2192,8 @@ Algoritmos \end_layout \begin_layout Standard -Las máquinas de Turing y mecanismos generales no solo permiten reconocer - cadenas, sino ejecutar algoritmos en general. +Las máquinas de Turing no solo permiten reconocer cadenas, sino ejecutar + algoritmos en general. La entrada siempre es una cadena, por lo que para que otro tipo de objeto actúe de entrada hay que representarla como una cadena y la máquina de Turing debe decodificar esta representación. @@ -2245,7 +2209,7 @@ Las máquinas de Turing y mecanismos generales no solo permiten reconocer \begin_inset Formula $O$ \end_inset -, y dados objetos + en cierta representación, y dados objetos \begin_inset Formula $O_{1},\dots,O_{n}$ \end_inset @@ -2257,7 +2221,7 @@ Las máquinas de Turing y mecanismos generales no solo permiten reconocer \begin_inset Formula $(O_{1},\dots,O_{n})$ \end_inset -, en cierta representación. +. La \begin_inset Formula $\text{MT}$ \end_inset diff --git a/mc/n4.lyx b/mc/n4.lyx index a4fb314..7e6efca 100644 --- a/mc/n4.lyx +++ b/mc/n4.lyx @@ -439,7 +439,7 @@ input \end_inset que reconoce -\begin_inset Formula $K\coloneqq\{\langle{\cal A},w\rangle\mid \text{la MT \ensuremath{{\cal A}} acepta \ensuremath{w}}\}$ +\begin_inset Formula $K\coloneqq\{\langle{\cal A},w\rangle\mid\text{la MT \ensuremath{{\cal A}} acepta \ensuremath{w}}\}$ \end_inset . @@ -1953,7 +1953,7 @@ Algunos lenguajes decidibles: \end_layout \begin_layout Enumerate -\begin_inset Formula $\text{Acc}^{\text{DFA}}\coloneqq\{\langle{\cal A},w\rangle\mid \text{el DFA \ensuremath{{\cal A}} acepta la cadena \ensuremath{w}}\}$ +\begin_inset Formula $\text{Acc}^{\text{DFA}}\coloneqq\{\langle{\cal A},w\rangle\mid\text{el DFA \ensuremath{{\cal A}} acepta la cadena \ensuremath{w}}\}$ \end_inset . @@ -2044,7 +2044,7 @@ fun m q0 finals w -> contains (==) (sim m w q0) finals \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{Acc}^{\text{NFA}}\coloneqq\{\langle{\cal A},w\rangle\mid \text{el NFA \ensuremath{{\cal A}} acepta la cadena \ensuremath{w}}\}$ +\begin_inset Formula $\text{Acc}^{\text{NFA}}\coloneqq\{\langle{\cal A},w\rangle\mid\text{el NFA \ensuremath{{\cal A}} acepta la cadena \ensuremath{w}}\}$ \end_inset . @@ -2275,7 +2275,7 @@ fun (states, syms, m, r0, finals) -> \end_layout \begin_layout Enumerate -\begin_inset Formula $\text{Acc}^{\text{PDA}}\coloneqq\{\langle{\cal A},w\rangle\mid \text{el PDA \ensuremath{{\cal A}} acepta la cadena \ensuremath{w}}\}$ +\begin_inset Formula $\text{Acc}^{\text{PDA}}\coloneqq\{\langle{\cal A},w\rangle\mid\text{el PDA \ensuremath{{\cal A}} acepta la cadena \ensuremath{w}}\}$ \end_inset . @@ -2322,7 +2322,7 @@ forma normal de Chomsky \end_layout \begin_layout Enumerate -\begin_inset Formula $\text{Empty}^{\text{DFA}}\coloneqq\{\langle{\cal A}\rangle\mid \text{el DFA }{\cal A}\text{ no acepta ninguna cadena}\}$ +\begin_inset Formula $\text{Empty}^{\text{DFA}}\coloneqq\{\langle{\cal A}\rangle\mid\text{el DFA }{\cal A}\text{ no acepta ninguna cadena}\}$ \end_inset . @@ -2433,7 +2433,7 @@ fun (trans, q0, finals) -> anystring trans finals nil (cons q0 nil) \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{Empty}^{\text{NFA}}\coloneqq\{\langle{\cal A}\rangle\mid \text{el NFA }{\cal A}\text{ no acepta ninguna cadena}\}$ +\begin_inset Formula $\text{Empty}^{\text{NFA}}\coloneqq\{\langle{\cal A}\rangle\mid\text{el NFA }{\cal A}\text{ no acepta ninguna cadena}\}$ \end_inset . @@ -2446,7 +2446,7 @@ Análogo. \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{Empty}^{\text{PDA}}\coloneqq\{\langle{\cal A}\rangle\mid \text{el PDA }{\cal A}\text{ no acepta ninguna cadena}\}$ +\begin_inset Formula $\text{Empty}^{\text{PDA}}\coloneqq\{\langle{\cal A}\rangle\mid\text{el PDA }{\cal A}\text{ no acepta ninguna cadena}\}$ \end_inset . @@ -2580,7 +2580,7 @@ numeración de Gödel \series bold computables \series default -, es decir existe una +, es decir, existe una \begin_inset Formula $\text{MT}$ \end_inset @@ -2609,19 +2609,15 @@ Demostración: \begin_inset Formula $f:A\to{\cal P}(A)$ \end_inset -, sea +, sean \begin_inset Formula $B\coloneqq\{x\in A\mid x\notin f(x)\}$ \end_inset -, existe -\begin_inset Formula $y\in A$ -\end_inset - - con -\begin_inset Formula $f(y)=B$ + e +\begin_inset Formula $Y\coloneqq f^{-1}(B)$ \end_inset -, pero si +, si \begin_inset Formula $y\in B$ \end_inset @@ -2641,7 +2637,7 @@ Demostración: \end_layout \begin_layout Standard -Existen lenguajes no recursivamente enumerables, pues el conjunto lenguajes +Existen lenguajes no recursivamente enumerables, pues el conjunto de lenguajes sobre un alfabeto \begin_inset Formula $\Sigma$ \end_inset @@ -2767,7 +2763,7 @@ status open \begin_layout Standard \begin_inset Formula \[ -K\coloneqq\{\langle{\cal M},w\rangle\mid \text{la MT }{\cal M}\text{ acepta con entrada }w\}\in{\cal RE}\setminus{\cal DEC}. +K\coloneqq\{\langle{\cal M},w\rangle\mid\text{la MT }{\cal M}\text{ acepta con entrada }w\}\in{\cal RE}\setminus{\cal DEC}. \] \end_inset @@ -2806,7 +2802,7 @@ Demostración: \end_inset que decide -\begin_inset Formula $\{\langle{\cal M}\rangle\mid {\cal H}\text{ rechaza }\langle{\cal M},\langle{\cal M}\rangle\rangle\}$ +\begin_inset Formula $\{\langle{\cal M}\rangle\mid{\cal H}\text{ rechaza }\langle{\cal M},\langle{\cal M}\rangle\rangle\}$ \end_inset , pero entonces @@ -2854,7 +2850,8 @@ Para un lenguaje \begin_inset Formula $\overline{L}$ \end_inset - hasta que una termine y aceptar o rechazar según cuál termine. + hasta que una termine y aceptar o rechazar según cuál termine y con qué + resultado. \end_layout \begin_layout Standard diff --git a/mc/n5.lyx b/mc/n5.lyx index 03d0675..3312684 100644 --- a/mc/n5.lyx +++ b/mc/n5.lyx @@ -80,48 +80,6 @@ \begin_body -\begin_layout Standard -Un -\series bold -oráculo -\series default - para un lenguaje -\begin_inset Formula $L$ -\end_inset - - es una caja negra que decide -\begin_inset Formula $L$ -\end_inset - -. - Un lenguaje -\begin_inset Formula $A$ -\end_inset - - se -\series bold -reduce -\series default - a un lenguaje -\begin_inset Formula $B$ -\end_inset - - si existe una -\begin_inset Formula $\text{MT}$ -\end_inset - - que decide -\begin_inset Formula $A$ -\end_inset - - usando un oráculo de -\begin_inset Formula $B$ -\end_inset - -. - -\end_layout - \begin_layout Standard Una \series bold @@ -144,26 +102,38 @@ reducción \end_inset . - Una función -\begin_inset Formula $f:\Sigma_{1}^{*}\to\Sigma_{2}^{*}$ + Una MT +\begin_inset Formula ${\cal M}$ \end_inset - es + \series bold -computable +computa \series default - si existe una -\begin_inset Formula $\text{MT}$ + una función +\begin_inset Formula $f:\Sigma_{1}^{*}\to\Sigma_{2}^{*}$ \end_inset - que siempre termina y que, para una entrada + si siempre termina y, para \begin_inset Formula $w\in\Sigma_{1}^{*}$ \end_inset -, termina conteniendo en su cinta únicamente +, +\begin_inset Formula ${\cal M}$ +\end_inset + + termina conteniendo en su cinta únicamente \begin_inset Formula $f(w)$ \end_inset +, y entonces +\begin_inset Formula $f$ +\end_inset + + es +\series bold +computable +\series default . Una \series bold @@ -210,6 +180,46 @@ reducir , y esta relación es claramente transitiva. \end_layout +\begin_layout Standard +Equivalentemente, un +\series bold +oráculo +\series default + para un lenguaje +\begin_inset Formula $L$ +\end_inset + + es una caja negra que decide +\begin_inset Formula $L$ +\end_inset + +, y un lenguaje +\begin_inset Formula $A$ +\end_inset + + +\series bold +se reduce +\series default + a un lenguaje +\begin_inset Formula $B$ +\end_inset + + si existe una +\begin_inset Formula $\text{MT}$ +\end_inset + + con un oráculo de +\begin_inset Formula $B$ +\end_inset + + que decide +\begin_inset Formula $A$ +\end_inset + +. +\end_layout + \begin_layout Standard \series bold @@ -327,7 +337,7 @@ Problema de la parada. \begin_inset Formula \[ -\text{HALT}^{\text{MT}}\coloneqq\{\langle{\cal M},w\rangle\mid {\cal M}\text{ es una MT que para con entrada }w\}\notin{\cal DEC}. +\text{HALT}^{\text{MT}}\coloneqq\{\langle{\cal M},w\rangle\mid{\cal M}\text{ es una MT que para con entrada }w\}\notin{\cal DEC}. \] \end_inset @@ -341,7 +351,7 @@ Sea \begin_inset Formula ${\cal M}'$ \end_inset - es una + una \begin_inset Formula $\text{MT}$ \end_inset @@ -380,7 +390,7 @@ mapping \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{EMPTY}^{\text{MT}}\coloneqq\{\langle{\cal M}\rangle\mid {\cal M}\text{ es una MT que no acepta ninguna cadena}\}\notin{\cal DEC}$ +\begin_inset Formula $\text{EMPTY}^{\text{MT}}\coloneqq\{\langle{\cal M}\rangle\mid{\cal M}\text{ es una MT que no acepta ninguna cadena}\}\notin{\cal DEC}$ \end_inset . @@ -454,7 +464,7 @@ mapping \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{Pass}\coloneqq\{\langle{\cal M},w,q\rangle\mid {\cal M}\text{ es una MT que, con entrada }w\text{, pasa por el estado \ensuremath{q}}\}\notin{\cal DEC}$ +\begin_inset Formula $\text{Pass}\coloneqq\{\langle{\cal M},w,q\rangle\mid{\cal M}\text{ es una MT que, con entrada }w\text{, pasa por el estado \ensuremath{q}}\}\notin{\cal DEC}$ \end_inset . @@ -512,7 +522,6 @@ mapping \end_deeper \begin_layout Standard -Un lenguaje \begin_inset Formula $L\in{\cal RE}$ \end_inset @@ -674,7 +683,7 @@ Teorema de Rice: no trivial, \begin_inset Formula \[ -{\cal L}_{P}\coloneqq\{\langle{\cal M}\rangle\mid {\cal M}\text{ es una MT con }L(M)\in P\}\notin{\cal DEC}. +{\cal L}_{P}\coloneqq\{\langle{\cal M}\rangle\mid{\cal M}\text{ es una MT con }L(M)\in P\}\notin{\cal DEC}. \] \end_inset @@ -713,7 +722,7 @@ Demostración: \end_inset . - Si, por ejemplo, + Si \begin_inset Formula $L_{2}=\emptyset$ \end_inset @@ -808,7 +817,7 @@ mapping \begin_inset Formula $L_{1}=\emptyset$ \end_inset - esto permite probar que + por este argumento \begin_inset Formula ${\cal RE}\setminus{\cal L}_{P}\notin{\cal DEC}$ \end_inset diff --git a/mc/n6.lyx b/mc/n6.lyx index 3adbae2..6dbb810 100644 --- a/mc/n6.lyx +++ b/mc/n6.lyx @@ -170,7 +170,7 @@ límite superior asintótico \begin_layout Standard Para -\begin_inset Formula $t:\mathbb{N}\to\mathbb{R}^{+}$ +\begin_inset Formula $t:\mathbb{N}\to\mathbb{R}^{\geq0}$ \end_inset , llamamos @@ -190,8 +190,7 @@ clase de complejidad \end_inset . - Nótese que esta magnitud se refiere al lenguaje o problema, no a un algoritmo - concreto. + Esta magnitud se refiere al lenguaje o problema, no a un algoritmo concreto. En general, la clase de complejidad de un problema depende del modelo de computación usado, aun para modelos equivalentes. Este orden no difiere mucho entre modelos deterministas, pero sí entre @@ -252,7 +251,7 @@ Demostración: y luego para aplicarla, actualizando el contenido de las celdas y las posicione s de los cursores. Cada cinta tiene tamaño como mucho -\begin_inset Formula $O(t(n))$ +\begin_inset Formula $O(\max\{t(n),n\})=O(t(n))$ \end_inset , pues en cada transición se añade como mucho un caracter en cada cinta, @@ -265,11 +264,7 @@ s de los cursores. \end_inset de estos, el tiempo total es -\begin_inset Formula $O(t(n)^{2}+n)=O(t(n)^{2})$ -\end_inset - -, usando que -\begin_inset Formula $t(n)\geq n$ +\begin_inset Formula $O(t(n)^{2})$ \end_inset . @@ -383,16 +378,7 @@ backtracking \lang spanish y para evitar la interferencia entre una simulación y la siguiente, por lo que el total de transiciones es como mucho -\begin_inset Formula $O(n+mc^{m})=O(n+f(n)c^{f(n)})$ -\end_inset - -, usando que -\begin_inset Formula $n\leq f(n)$ -\end_inset - -. - Entonces el total es -\begin_inset Formula $O(f(n)c^{f(n)})=O(2^{\log_{2}f(n)+f(n)\log_{2}c})=2^{O(\log_{2}f(n)+f(n)\log_{2}c})=2^{O(f(n))}$ +\begin_inset Formula $O(n+mc^{m})=O(n+f(n)c^{f(n)})=O(f(n)c^{f(n)})=O(2^{\log_{2}f(n)+f(n)\log_{2}c})=2^{O(\log_{2}f(n)+f(n)\log_{2}c)}=2^{O(f(n))}$ \end_inset , y por el teorema anterior, al simular esto en un @@ -419,16 +405,7 @@ Nótese que \begin_inset Formula $3^{n}\neq O(2^{n})$ \end_inset - pero -\begin_inset Formula $3^{n}=2^{\log_{2}3^{n}}=2^{n\log_{2}3}=2^{O(n)}$ -\end_inset - -. - En efecto, claramente -\begin_inset Formula $n\log_{2}3\in O(n)$ -\end_inset - -, pero para cualesquiera + porque para cualesquiera \begin_inset Formula $c,n_{0}\in\mathbb{N}$ \end_inset @@ -444,6 +421,10 @@ Nótese que \begin_inset Formula $n>\log_{\frac{3}{2}}c$ \end_inset +, pero +\begin_inset Formula $3^{n}=2^{\log_{2}3^{n}}=2^{n\log_{2}3}=2^{O(n)}$ +\end_inset + . \end_layout diff --git a/mc/n7.lyx b/mc/n7.lyx index 2c77bac..f97eed9 100644 --- a/mc/n7.lyx +++ b/mc/n7.lyx @@ -135,31 +135,6 @@ Los problemas en esta clase se consideran tratables, y el resto intratables. \begin_layout Standard Una -\begin_inset Formula $\text{MT}$ -\end_inset - - -\series bold -computa -\series default - una función -\begin_inset Formula $f:D\subseteq\Sigma^{*}\to\Sigma^{*}$ -\end_inset - - si decide -\begin_inset Formula $D$ -\end_inset - - y, para -\begin_inset Formula $w\in D$ -\end_inset - -, termina conteniendo solo -\begin_inset Formula $f(w)$ -\end_inset - - en su cinta. - Una \series bold función polinómica \series default @@ -219,10 +194,15 @@ representación interna Las formas que hemos usado para representar autómatas, grafos, etc. son razonables, pero no lo es la representación unaria de números, pues - es exponencialmente más larga que una representación en base 2 o más. + es exponencialmente más larga que una representación en base 2 o más que + sí es razonable. \end_layout \begin_layout Standard +\begin_inset Note Comment +status open + +\begin_layout Plain Layout \begin_inset Float algorithm wide false sideways false @@ -362,7 +342,7 @@ Suma \end_layout -\begin_layout Standard +\begin_layout Plain Layout \begin_inset Float algorithm wide false sideways false @@ -506,7 +486,7 @@ Resta saturada \end_layout -\begin_layout Standard +\begin_layout Plain Layout \begin_inset Float algorithm wide false sideways false @@ -648,7 +628,7 @@ Producto \end_layout -\begin_layout Standard +\begin_layout Plain Layout \begin_inset Float algorithm wide false sideways false @@ -842,6 +822,11 @@ Cociente entero \end_inset +\end_layout + +\end_inset + + \end_layout \begin_layout Standard @@ -886,7 +871,7 @@ in L(G)$, rechaza en otro caso.} \backslash SSi{$w= \backslash -lambda$}{ +epsilon$}{ \end_layout \begin_layout Plain Layout @@ -897,7 +882,7 @@ lSSi{$S \backslash to \backslash -lambda +epsilon \backslash in{ \backslash @@ -922,7 +907,17 @@ $T \backslash gets \backslash -emptyset$ +{((i,j), +\backslash +emptyset) +\backslash +}_{1 +\backslash +leq i +\backslash +leq j +\backslash +leq n}$ \end_layout \begin_layout Plain Layout @@ -931,15 +926,7 @@ emptyset$ \backslash tcp*{{ \backslash -rm Para $ -\backslash -{(i,j) -\backslash -}_{1 -\backslash -leq i