MC inicio tema 3

2 files changed, 587 insertions, 0 deletions

diff --git a/mc/n.lyx b/mc/n.lyx
index 4b2dfbd..dbbddde 100644
--- a/mc/n.lyx
+++ b/mc/n.lyx
@@ -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