#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