diff options
| -rw-r--r-- | mc/n.lyx | 41 | ||||
| -rw-r--r-- | mc/n3.lyx | 546 |
2 files changed, 587 insertions, 0 deletions
@@ -163,6 +163,33 @@ Introduction to the Theory of Computation, 3rd. (2013). \end_layout +\begin_layout Itemize + +\lang english +Wikipedia, the Free Encyclopedia +\lang spanish +. + +\emph on +\lang english +Turing Machine +\emph default +\lang spanish +. + Recuperado de +\begin_inset Flex URL +status open + +\begin_layout Plain Layout + +https://en.wikipedia.org/wiki/Turing_machine +\end_layout + +\end_inset + + a fecha de 11 de septiembre de 2022. +\end_layout + \begin_layout Chapter Lenguajes regulares \end_layout @@ -191,5 +218,19 @@ filename "n2.lyx" \end_layout +\begin_layout Chapter +Máquinas de Turing +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "n3.lyx" + +\end_inset + + +\end_layout + \end_body \end_document diff --git a/mc/n3.lyx b/mc/n3.lyx new file mode 100644 index 0000000..b3801e7 --- /dev/null +++ b/mc/n3.lyx @@ -0,0 +1,546 @@ +#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 Section +Historia +\end_layout + +\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 Standard +Church además probó que el cálculo +\begin_inset Formula $\lambda$ +\end_inset + + es equivalente a las +\series bold +funciones recursivas +\series default +, propuestas por Kurt Gödel en 1931, y Turing, cuyo artículo salió después, + probó que las +\emph on +\lang english +computing machines +\emph default +\lang spanish + son equivalentes al cálculo +\begin_inset Formula $\lambda$ +\end_inset + +, en el sentido de que las mismas funciones se pueden expresar en los 3 + formalismos. + Esto llevó a la +\series bold +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 + posible y todos los modelos suficientemente expresivos son equivalentes + a este. +\end_layout + +\begin_layout Standard +Posteriormente aparecieron otras definiciones formales de algoritmo, como + las +\series bold +funciones parciales +\series default +, las +\series bold +máquinas con infinitos registros +\series default + o el +\series bold +lenguaje S +\series default + (simple), todas equivalentes a las máquinas de Turing. + Un lenguaje de programación es +\series bold +Turing completo +\series default + si es equivalente a las máquinas de Turing. +\end_layout + +\begin_layout Section +Definiciones +\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_{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$ +\end_inset + +, como +\begin_inset Quotes cld +\end_inset + + +\begin_inset Formula $c_{0}\cdots c_{k-1}qc_{k}\cdots c_{n}$ +\end_inset + + +\begin_inset Quotes crd +\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 $(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|$ +\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 + +, o bien no termina. +\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 +\begin_inset Note Note +status open + +\begin_layout Plain Layout +diapo 15 +\end_layout + +\end_inset + + +\end_layout + +\end_body +\end_document |