300 lines
24 KiB
TeX
300 lines
24 KiB
TeX
\documentclass[10pt,a4paper]{article}
|
||
\usepackage[utf8]{inputenc}
|
||
\usepackage[spanish]{babel}
|
||
\usepackage{amsmath}
|
||
\usepackage{amsfonts}
|
||
\usepackage{amssymb}
|
||
\usepackage{hyperref}
|
||
\usepackage{graphicx}
|
||
\usepackage{algpseudocode}
|
||
\usepackage[Algoritmo]{algorithm}
|
||
\usepackage{subcaption}
|
||
\usepackage{pgf}
|
||
\usepackage{tikz}
|
||
\usetikzlibrary{automata,positioning,arrows}
|
||
%\tikzset{->, % makes the edges directed
|
||
% >=stealth’, % makes the arrow heads bold
|
||
% node distance=3cm, % specifies the minimum distance between two nodes. Change if necessary.
|
||
% every state/.style={thick, fill=gray!10}, % sets the properties for each ’state’ node
|
||
% initial text=$ $ % sets the text that appears on the start arrow
|
||
% }
|
||
%\usetikzlibrary{arrows,automata}
|
||
%\usepackage[all,cmtip]{xy}
|
||
%\usepackage{graphicx}
|
||
\author{Autómatas y lenguajes formales}
|
||
\title{Otros formalismos}
|
||
\begin{document}
|
||
\maketitle
|
||
|
||
\section{Los otros modelos}
|
||
|
||
Ahora que estamos a la distancia y nos parece tan lejana la vida en la facultad (en algunas cosas para bien, en otras no) iniciaré esta nota con una anécdota. Tuve en la facultad un profesor de geometría y álgebra lineal que aún está ahí en el departamento de matemáticas. En su época de estudiante de ciencias la costumbre era estudiar las dos carreras de física y matemáticas (ya ven que en la facultad casi no se da eso), él por ser parte del ``hype'' entró a ambas carreras, originalmente estudiaba física.
|
||
|
||
Como era de esperar la demanda de tiempo y trabajo era demasiada, a medio semestre ya estaba flaco, ojeroso y sin ilusiones, no soportó tanto y decidió abandonar una carrera. Lo raro fue que no decidió abandonar la carrera extra, que era matemáticas, prefirió renunciar a física. Sus razones eran las siguientes: la ventaja de la matemática sobre la física es que puedes tomar varios caminos, el que te agrade, el que se te ocurra, y llegar al resultado, más de uno de esos caminos es correcto. En cambio en la física es todo más rígido, hay un sólo camino (por lo regular) y no hay mucha posibilidad para cambiar la ruta.
|
||
|
||
Esto se debe mucho a la experiencia que tuvo este profesor en ese entonces estudiante, seguro hay áreas de la física que dan libertad. Pero en lo que concuerdo completamente es que en las matemáticas hay un poco más de libertad para enfrentar un problema, más de una persona puede llegar al resultado correcto por caminos distintos y ser válido. Lo mismo sucede en teoría de la computación (que como han podido ver en este y otros cursos tiene un origen en común con las matemáticas), no sólo hay un único modelo computacional.
|
||
|
||
Ahora, sí yo quisiera hacer otro modelo ¿cómo podría saber que es correcto? '¿Cómo saber que en efecto estos modelos distintos hacen lo mismo? La idea de base es la \emph{computabilidad efectiva}, el rasgo en común que tienen estos modelos. La tesis de Church-Turing (que es más una afirmación) dice:
|
||
|
||
\newtheorem{church}{Tesis de Church-Turing}
|
||
\begin{church}
|
||
Toda función es calculable efectivamente sí y sólo sí es calculable por una máquina de Turing.
|
||
\end{church}
|
||
|
||
Aquí van a decir que ya cayó más pronto un hablador que un cojo, hay una posición preferente a la máquina de Turing ¿no que muy incluyente? Es cierto, la máquina de Turing tiene una posición preferente, de acuerdo al texto por su simplicidad y claridad, pero todos los modelos equivalentes pueden representarse por una máquina de Turing, entonces, como lo hemos hecho en el curso, la máquina de Turing es la que tomamos como paradigma, pero los formalismos que veremos son equivalentes. Si para ustedes no fue tan claro y les queda más claro por estos modelos, entonces podrán decir que se toma la máquina de Turing por pura formalidad. Lo que veremos en estas opciones es que en algunos casos son más parecidos a un lenguaje de programación de los que ahora usamos.
|
||
|
||
\section{Funciones recursivas $\mu$}
|
||
Una buena pregunta sería, ¿cuál es el mínimo de funciones necesarias para definir a todas las funciones computables? ¿Cuáles son las funciones de ese conjunto mínimo? De acuerdo a Gödel esas funciones numérico-teóricas ${\mathbb{N}}^k \rightarrow \mathbb{N} $ son:
|
||
|
||
\begin{enumerate}
|
||
\item \emph{Sucesor}. La función $\mathbf{s}:\mathbb{N} \rightarrow \mathbb{N}$ dadas por $\mathbf{s}(x)=x+1$ es computable.
|
||
\item \emph{Cero}. La función $\mathbf{z}: \mathbb{N}^0 \rightarrow \mathbb{N}$ dada por $\mathbb{z}()=0$ es computable.
|
||
\item \emph{Proyecciones}. Las funciones $\pi_k^n: \mathbb{N}^n \rightarrow \mathbb{N}$ dadas por $\pi_k^n(x_1,...,x_n) = x_k,\ 1\leq k \leq n$, son computables.
|
||
\item \emph{Composición}. Si $f:\mathbb{N}^k \rightarrow \mathbb{N}$ y $g_1,...g_k:\mathbb{N}^n \rightarrow \mathbb{N}$ son computables, entonces también lo es la función $f\circ (g_1,...,g_k):\mathbb{N}^n \rightarrow\mathbb{N}$ que en la entrada $\overline{x}= x_1,...,x_n$, da
|
||
\begin{equation*}
|
||
f(g_1(\overline{x}),...,g_k(\overline{x}))
|
||
\end{equation*}
|
||
\item \emph{Recursión primitiva}. Si $h_i:\mathbb{N}^{n} \rightarrow \mathbb{N}$ y $g_i:\mathbb{N}^{n+k+1} \rightarrow \mathbb{N}$ son computables, $1\leq i \leq k$, entonces también lo son las funciones $f_i:\mathbb{N}^{n+1} \rightarrow \mathbb{N},\ 1\leq i \leq k$, definidas por inducción mutua de la siguiente manera:
|
||
\begin{align*}
|
||
f_i(0,\overline{x}) &\overset{def}{=} h_i(x) \\
|
||
f_i(x+1,\overline{x}) &\overset{def}{=} g_i(x,\overline{x},f_1(x,\overline{x}),...,f_k(x,\overline{x})),
|
||
\end{align*}
|
||
donde $\overline{x}=x_1,...,x_n$.
|
||
|
||
\item \emph{Minimización no acotada}. Si $g:\mathbb{N}^{n+1} \rightarrow \mathbb{N}$ es computable, entonces también lo es la función $f:\mathbb{N}^n \rightarrow $ que con la entrada $\overline{x}=x_1,...,x_n$ de al menos $y$ tal que $g(z,\overline{x})$ esté definida para todas las $z\leq y$ y $g(y,\overline{x})=0$ si tal $y$, y está indefinida de otra manera. Esto se denota como:
|
||
\begin{equation*}
|
||
f(\overline{x})=\mu y.(g(y,\overline{x})=0)
|
||
\end{equation*}
|
||
\end{enumerate}
|
||
|
||
Algunas de estas funciones suenan demasiado enredadas, pero vamos viendo por pasos. Las primeras cuatro parecen bastante directas, el \emph{sucesor} nos da la posibilidad de construir cualquier número a partir de una base, e incluso nos es útil para definir operaciones más complicadas, como la suma de dos o más números, la multiplicación, el factorial (no se preocupen, lo vamos viendo). La operación lo que hace es sumar un $1$ al número que se le dé como entradad a la función.
|
||
|
||
La función \emph{cero}, $\mathbf{z}$, construye nuestro primer número, el cero, sin necesidad de una entrada, a partir de él podemos construir los demás naturales. La función \emph{proyección},$\pi_k^n$ elige el elemento $k$ (esta enumeración va de acuerdo a su posición en la lista) de una lista de $n$ elementos. Y la función \emph{composición} hace la composición que ya conocemos de dos funciones, así podemos componer \emph{proyección} con \emph{sucesor}, de forma que al elemento $k$ le sumemos un $1$ y eso de como resultado.
|
||
|
||
\begin{equation*}
|
||
s(\pi_k^n(\overline{x}))=x_k+1.
|
||
\end{equation*}
|
||
|
||
Para poder definir funciones más complicadas necesitamos de la recursión primitiva, aquí ya empieza a sonar a lenguaje de programación. Veamos como podemos armar la suma con estas funciones.
|
||
|
||
Vamos a llamarle la función $suma(x)$ y vamos a ponerla en forma de recursión primitiva. Siguiendo los pasos del quinto punto debemos tener una $h$ y una $g$. Sea $h=\pi_1^1$, la proyección de una lista de un miembro en la posición $1$ (no hace nada esta función más que darnos el mismo número que le hemos dado) y sea $g=\mathbf{s}\circ \pi_3^3$ la composición de la función sucesión con la proyección del tercer miembro de una lista de $3$. Noten que la función $h:\mathbb{N} \rightarrow \mathbb{N}$, va de la dimensión uno a la dimensión uno, $n=1$, y $g: \mathbb{N}^3 \rightarrow \mathbb{N}$, notemos que como $n=1$, entonces $k=1$ y así $n+k+1=3$.
|
||
|
||
¿Porqué se eligieron así las funciones? Para verlo lo ponemos en la forma de la recursión primitiva, \emph{suma} será nuestra función $f_i$, como $1 \leq i \leq k$ y en nuestro caso $k=1$ entonces $i=1$, sólo hay una $f=suma$:
|
||
\begin{align*}
|
||
suma(0,y) &\overset{def}{=} h(y) = \pi_1^1(y) = y \\
|
||
suma(x+1,y) &\overset{def}{=} g(x,y,suma(x,y)) = s(\pi_3^3(x,y,suma(x,y))) = s(suma(x,y))
|
||
\end{align*}
|
||
|
||
Y ahí con recursión se puede llegar a suma de cualquier par de números.
|
||
|
||
Ahora, a partir de la suma definimos la multiplicación:
|
||
|
||
\begin{align*}
|
||
mult(0,y) &\overset{def}{=} z() =0 \\
|
||
mult(x+1,y) &\overset{def}{=} suma(y,mult(x,y))
|
||
\end{align*}
|
||
|
||
De nueva cuenta hay una recursión inmiscuida para hacer cualquier operación.
|
||
|
||
Se dan una idea de cómo hacer más cosas ¿cierto? Ahora de tarea, para todxs lxs gamers, hagan el \textit{The Last of us} con puras funciones recursivas, debe quedarles algo como en la figura \ref{fig:lou}.
|
||
|
||
\begin{figure}[h!]
|
||
\begin{center}
|
||
\includegraphics[width=0.5\linewidth]{last_of_us.png}
|
||
\caption{\textit{The Last of Us} en 8 bits. Imagen de Rgznsk, tomada de: \url{https://www.it8bit.com/post/158114971533/the-last-of-us-pixel-art-created-by-rgznsk}}
|
||
\label{fig:lou}
|
||
\end{center}
|
||
\end{figure}
|
||
|
||
Bueno, después de mi chiste bobo y antes de pasar a cálculo $\lambda$, seguro se preguntarán ¿y la sexta función, la minimización no acotada, dónde se usa? Bueno, esta es una operación que como verán en la descripción está relacionada con hasta que punto está definida la función, esto se puede relacionar con el orden y la búsqueda en listas, no coman ansias, ya lo verán en análisis de algoritmos. Su utilidad es un poco menos intuitiva que las demás funciones, así que en este punto es importante que sepan que existe.
|
||
|
||
\section*{Calculo $\lambda$}
|
||
|
||
\emph{Lisp} y sus variaciones (\emph{scheme, common lisp}) son lenguajes de programación muy parecidos al cálculo $\lambda$. Este es el histórico, \emph{lisp} es uno de los lenguajes más antiguos y en verdad ahora se considera una familia. \emph{Haskell} es un lenguaje un poco más moderno (un poco menos moderno que ustedes, data de 1990 su primera versión), esto del calculo $\lambda$ seguro les va a parecer familiar si conocen \emph{haskell} o algún dialecto de \emph{lisp}. Y si son gamers han de saber que el estudio que hace \textit{The Last of Us} inició trabajando con su propio dialecto de \emph{lisp}, que ahora usan menos por cuestiones de portabilidad estando en una empresa más grande, \textit{sony}.
|
||
|
||
El cálculo $\lambda$ hace uso de un conjunto de objetos llamados $\lambda$-términos y algunas reglas para manejarlos. Por ejemplo, si queremos escribir la función sucesor de las funciones recursivas $\mu$, lo escribiríamos:
|
||
|
||
\begin{equation*}
|
||
\lambda x.(x+1),
|
||
\end{equation*}
|
||
|
||
\noindent que quiere decir "con la entrada $x$ calcula $(x+1)$", es decir, la función sucesor. Al aplicarlo a un número, digamos $4$, se escribiría $(\lambda x.(x+1))4 \rightarrow 4+1=5$. La composición sería:
|
||
|
||
\begin{equation*}
|
||
\lambda x.f(gx),
|
||
\end{equation*}
|
||
|
||
\noindent con la entrada $x$ le aplica $g$ y luego $f$, lo único que se le da como entrada a esta función es $x$; $g$ y $f$ ya están definidas dentro. Si quisiéramos darlas también como entradas de la función entonces se escribiría $\lambda f. \lambda g. \lambda x. f(gx)$. ¿Tienen una idea? Si no, no dejen de preguntar. Ahora veremos una versión refinada que llaman el cálculo $\lambda$ puro.
|
||
|
||
\section*{Calculo $\lambda$ puro}
|
||
|
||
En esta variante sólo hay variables y operadores para $\lambda$-abstracciones y aplicaciones. Para construir un $\lambda$-término de manera inductiva a partir de:
|
||
|
||
\begin{itemize}
|
||
\item Cualquier variable $x$ es un $\lambda$-término
|
||
\item Si $M$ y $N$ son $\lambda$-términos, entonces $MN$ es un $\lambda$-término (aplicación funcional, $M$ es la función que está a punto de ser aplicada a la entrada $N$)
|
||
\item Si $M$ es un $\lambda$-término y $x$ es una variable, entonces $\lambda x.M$ es un $\lambda$-término (abstracción funcional, $\lambda x.M$ es la función que con la entrada $x$ computa $M$).
|
||
\end{itemize}
|
||
|
||
Esto suena mucho a \emph{haskell} y como el mismo formalismo lo menciona, algo abstracto, vamos revisando.
|
||
|
||
\begin{itemize}
|
||
\item La aplicación funcional no es asociativa, y si se escribe sin paréntesis por convención las expresiones se asocian a la izquierda, es decir $MNP=(MN)P$
|
||
\item Los $\lambda$-términos sirven como funciones y datos (recuerden lo de universalidad y autoreferencia), de tal manera para definir la función sucesión debemos decodificarla de alguna manera.
|
||
\item Si tenemos funciones con más de una variable la podemos definir como:
|
||
\begin{equation*}
|
||
\lambda x_1 x_2...x_n.M \overset{def}{=} (\lambda x_1.(\lambda x_2.(...(\lambda x_n.M)...))),
|
||
\end{equation*}
|
||
los paréntesis mantienen el orden y podemos ver el orden de la abstracción.
|
||
\end{itemize}
|
||
|
||
¿Cómo realizamos la codificación del punto $2$? A la sustitución se le llama una $\beta$-reducción y funciona más o menos así: en un término mucho más grande y general se puede tener el subtérmino $(\lambda x.M)N$ puede ser substituido por $M_{[x/N]}$, este término abreviado denota a lo obtenido cuando:
|
||
|
||
\begin{enumerate}
|
||
\item renombrando las variables acotadas de $M$ (las $y$ que se dan como entrada a $M$ como un término $\lambda y$), así ninguna $x$ o $N$ aparezcan como acotadas a $M$. Así evitamos confundir variables.
|
||
\item Sustituyendo $N$ para todas las ocurrencias de $x$ en el término resultante (esta realmente es la sustitución, el anterior sólo es un paso previo).
|
||
\end{enumerate}
|
||
|
||
Como pueden ver en el término abreviado cualquier aplicación se hará sobre $M$, $x$ y $N$ van en la bolsa. Lo de renombrar variables en unos casos puede verse como una labor directa, por ejemplo en el término $\lambda y.xy$ podemos renombrar $y$ como $z$ y queda $\lambda z.xz$ que realmente no cambia en nada el término, pero si hubiera una doble aplicación nos ayudaría a diferenciar. Pero veamos un ejemplo, la función que duplica la entrada:
|
||
|
||
\begin{equation*}
|
||
(\lambda x.xx)z \underset{\beta}{\rightarrow} (xx)_{[x:=z]}=zz
|
||
\end{equation*}
|
||
|
||
Comparando con la $\beta$ reducción en esquema: $M$ es $xx$, $N$ es $z$ y $\lambda x$ es ella misma. Una vez que se ha aplicado la $\beta$-reducción el término está en su forma normal. La forma normal se traduce directamente a una función de transición en una máquina de Turing. No todos los términos tienen $\beta$-reducción.
|
||
|
||
Ahora convirtiendo las funciones recursivas $\mu$ a cálculo $\lambda$:
|
||
|
||
\begin{align*}
|
||
V_{bool} &\overset{def}{=} \lambda xy.x \\
|
||
F_{bool} &\overset{def}{=} \lambda xy.y \\
|
||
[M,N] &\overset{def}{=} \lambda z.zMN \\
|
||
\overline{0} &\overset{def}{=} \lambda x.x \\
|
||
\overline{n+1} &\overset{def}{=} [F,\overline{n}] \\
|
||
S &\overset{def}{=} \lambda x.[F,x] \\
|
||
P &\overset{def}{=} \lambda x.xF \\
|
||
C &\overset{def}{=} \lambda x.\overline{0} \\
|
||
Cero &\overset{def}{=} \lambda x.xV \\
|
||
\pi_i^n &\overset{def}{=} \lambda x_1,...,x_n.x_i \\
|
||
Y &\overset{def}{=} \lambda f .(\lambda x.f(xx))(\lambda x.f(xx))
|
||
\end{align*}
|
||
|
||
Con $\overline{0}$ y $\overline{n+1}$ construimos los números naturales (en las funciones recursivas $\mu$ no mostramos el constructor de los número naturales, pero pueden checarlo o intentar hacerlo). $S$ es la función sucesor y por facilidad agregamos la $P$ (predecesor, que también se puede contruir de funciones recursivas $\mu$), $V$ y $F$ los valores booleanos, por ahí también pueden ver la proyección, una función que comprueba si la entrada es igual a cero y da una salida booleana.
|
||
|
||
¿Para que sirve esa función $Y$? Es para la recursión. Veamos como definiríamos la recursión primitiva en cálculo $\lambda$. Pongamos de ejemplo que tenemos dos funciones $f:\mathbb{N}^k \rightarrow \mathbb{N}$ y un grupo de funciones $g_1,...,g_k: \mathbb{N}^n \rightarrow \mathbb{N}$, hacemos la $\beta$-reducción para estas funciones, entonces $f$ la pasamos a $F$ y las $g_1,...,g_k$ a $G_1,...,G_k$, la composición se escribiría como:
|
||
|
||
\begin{equation}
|
||
\lambda x_1...x_n.F(G_1 x_1...x_n)...(G_k x_1...x_n).
|
||
\end{equation}
|
||
|
||
Con esta base pasamos a la definición de la recursión primitiva (chequen líneas arriba), con las funciones dadas $h:\mathbb{N}^n \rightarrow \mathbb{N}$ y $g: \mathbb{N}^{n+2} \rightarrow \mathbb{N}$ computables que en $\beta$-reducción pasan a $H$ y $G$. Ahora la función recursiva $f:\mathbb{N}^{n+1} \rightarrow \mathbb{N}$ que se define a partir de $h$ y $g$, con sus respectivas $beta$-reducciones:
|
||
|
||
\begin{equation*}
|
||
Y \lambda f. \lambda yx_1...x_n.(Cero\ y)(H x_1...x_n)(G(P y)x_1...x_n(f(P y)x_1...x_n)).
|
||
\end{equation*}
|
||
|
||
Con esta estructura podemos construir la suma de forma recursiva en cálculo $\lambda$ (nuestra función $f$ será $SUMA$):
|
||
|
||
\begin{align*}
|
||
H &\overset{def}{=} \lambda x_1.x_1 \\
|
||
G &\overset{def}{=} \lambda z,x_1,x_2 . S((\lambda x_1,x_2,x_3 .x_3)zx_1x_2) \\
|
||
SUMA &\overset{def}{=} Y \lambda f. \lambda yx.(Cero\ y)(H x)(G(P y)x(f(P y)x)).
|
||
\end{align*}
|
||
|
||
Esto lo pueden ver sólo de sustituir en la estructura de arriba, tomando en cuenta que $k=1$ y $n=1$, es decir, sólo hay una $x$.
|
||
|
||
De manera similar pueden convertir la minimización no acotada.
|
||
|
||
\section*{Lenguaje IMP}
|
||
|
||
El lenguaje IMP es un modelo sencillo, aún con partes de abstracción, de un lenguaje de programación de ato nivel. Se pueden reconocer estructuras como el $if$ y el $while$ presentes en la mayoría de lenguajes de programación usados.
|
||
|
||
Se define como una gramática independiente de contexto, pero es un lenguaje Turing completo
|
||
|
||
\begin{align*}
|
||
P &\rightarrow skip \mid X:=A\mid (P;P)\mid (if\ B\ then\ P\ else\ P) \mid (while\ B\ do\ P) \\
|
||
A &\rightarrow Z\mid X\mid (A+A)\mid (A-A)\mid (A\times A) \\
|
||
B &\rightarrow v\mid f\mid (A=A)\mid (A < A)\mid \neg B\mid (B \wedge B)\mid (B\vee B) \\
|
||
X &\rightarrow x_N \\
|
||
N &\rightarrow 0\mid C \\
|
||
C &\rightarrow 1S\mid 2S\mid ...\mid 9S \\
|
||
S &\rightarrow 0S\mid 1S\mid ...\mid 9S\mid \epsilon \\
|
||
Z &\rightarrow N\mid -C \\
|
||
\end{align*}
|
||
|
||
\noindent donde podemos identificar las expresiones aritméticas($A$), las expresiones booleanas ($B$), la producción d elos números enteros $Z$, las localidades de memoria ($X$) y los comandos del lenguaje $P$.
|
||
|
||
En este caso no es necesario definir la suma desde una función más sencilla, pero lo que sí hay que definir es la recursión, eso se puede hacer a partir de $\mathbf{if}$ y $\mathbf{while}$.
|
||
|
||
Por ejemplo, si para el caso cero queremos evaluar una función $h$ lo hacemos como se puede ver en el algoritmo \ref{alg:ejem}
|
||
|
||
\begin{algorithm}
|
||
\caption{Evaluación diferenciada}\label{alg:ejem}
|
||
\begin{algorithmic}[1]
|
||
\State inicializaciones
|
||
\If {Condición inicial}
|
||
\State $h$ es evaluada
|
||
\Else $\ g$ es evaluada
|
||
\EndIf
|
||
\end{algorithmic}
|
||
\end{algorithm}
|
||
|
||
Lo pongo muy platicado, pero ya les toca a ustedes llenar los huecos.
|
||
|
||
Pero por poner un ejemplo ya sin recursión primitiva podemos definir la operación factorial de la forma como se ve en el algoritmo \ref{alg:fact}.
|
||
|
||
\begin{algorithm}
|
||
\caption{Función factorial de $n$}\label{alg:fact}
|
||
\begin{algorithmic}[1]
|
||
\State $x_0 := 1;$
|
||
\While $(x_1 < n) do$
|
||
\State $x_1:= (x_1 + 1);$
|
||
\State $x_0:= (x_0\times x_1)$
|
||
\EndWhile
|
||
\end{algorithmic}
|
||
\end{algorithm}
|
||
|
||
|
||
\section*{Programas While}
|
||
|
||
De nueva cuenta nos movemos a terrenos más conocidos de la programación, para ello definimos un lenguaje de programación sencillo.
|
||
\begin{enumerate}
|
||
\item asignación simple: $x:=0,\ x:=y+1,\ x:=y$
|
||
\item composición secuencial: $p:q$
|
||
\item condicional: $if\ x<y\ then\ p\ else\ p$
|
||
\item $for$ en ciclos: $for\ y\ do\ p$
|
||
\item $while$ en ciclos: $while\ x<y\ do\ p$
|
||
\end{enumerate}
|
||
|
||
\noindent con las relaciones $<,>,\leq,\geq, =, \neq$ intercambiables en los puntos 3 y 5.
|
||
|
||
Ya saben como funciona el $for$ y $while$, que incluso hasta cierto grado son intercambiables salvo que los programas con $for$ se detienen y el $while$ puede no detenerse y entrar en un ciclo infinito. Eso suena a una máquina de Turing bastante general y por eso nos centraremos en él.
|
||
|
||
Un estado o ambiente $\sigma$ es una asignación de un número natural a cada variable en el conjunto \textbf{Var}. Al conjunto de los ambientes le llamaremos \textbf{Env}. Al ejecutar el programa las variables irán cambiando, por lo que los ambientes también, pero todo dentro de los conjuntos definidos. En un programa las variables van cambiando, las asignaciones son dinámicas, entonces un programa es una función parcial que va de un ambiente a otro $[[p]]:\mathbf{Env} \rightarrow \mathbf{Env}$. Si el programa se detiene el ambiente final será $[[p]]\sigma$, de no detenerse esto no estará definido.
|
||
|
||
En este formalismo un programa $while$ se definiría a partir de $\sigma \in \mathbf{Env}$, $x \in \mathbf{Var}$ y $a \in \mathbb{N}$, siendo el ambiente $\sigma[x\leftarrow a]$ (el ambiente idéntico $\sigma$ excepto por el valor $x$ que es $a$). Formalmente:
|
||
|
||
\begin{align*}
|
||
\sigma[x\leftarrow a](y) &\overset{def}{=} \sigma (y) \textbf{ sí y no es x}\\
|
||
\sigma[x\leftarrow a](y) &\overset{def}{=} a
|
||
\end{align*}
|
||
|
||
|
||
\section*{Extra}
|
||
|
||
Ahora les van recomendaciones de libros que pueden descargar desde internet:
|
||
|
||
\emph{Editorial Tumbona}. Es una editorial independiente mexicana dedicada a el ensayo en su mayor parte. Es muy recomendable su colección \textbf{Versus} de ensayos cortos, entre ellos está un compendio llamado \textit{Contra el Copyright} con textos de Richard Stallman y la colectividad Wu Ming. De ahí debió nacer la idea de compartir varios de sus títulos, no sólo de esa colección. Muy recomendable \textit{Contra el copyright} y también \textit{Contra la televisión} de Heriberto Yépez, autor tijuanense. Quizá ya hoy en día la televisión esté muy superada, pero es un libro interesante donde el autor desarrolla sus ideas sobre el daño que la televisión le ha hecho a la sociedad mexicana, le llama la \emph{telefísica}. Echen un ojo al catálogo y llévense el que les agrade, como decía, los ensayos de \textbf{Versus} son cortos por lo que no será tan incómodo leerlos con pausas en una pantalla. La página es: \url{http://tumbonaediciones.com/descarga-de-libros/}.
|
||
|
||
\emph{Crunch editores}. Era una editorial mexicana dedicada a editar puros libros electrónicos, en un principio en pdf, después ya en epub. Su página oficial ya no existe y los libros sólo se encuentran en el \emph{internet archive}, por suerte siempre fueron gratis y de libre distribución. Les recomiendo \textit{La gente se droga} de otro escritor de Tijuana, Rafa Saavedra. Es un libro muy corto pero bastante experimental, sin perder contenido. Echen un ojo al catálogo, son libros cortos. En el internet archive la búsqueda: \url{https://archive.org/search.php?query=crunch%20editores}.
|
||
|
||
\emph{Librería del Partido Interdimensional Pirata}. Seguro ya conocen al partido Pirata, con sedes en varios países, desde el principio han estado a favor de compartir libremente la cultura. En su librería hay textos políticos en su mayoría, algunos zines, todo en descarga libre y en varios formatos. Aquí sí no puedo recomendarles nada, he ojeado varios de estos libros, los he empezado a leer, conozco otros de algunos de los autores, pero no puedo decirles más. Si les es útil, quieren conocer estas ideas y seguro si las comparten les dará gusto saber que no son los únicos que piensan así. La página: \url{https://utopia.partidopirata.com.ar/}.
|
||
|
||
Hay muchos libros que se encuentran en dominio público y valen la pena, es fácil encontrarlos en distintas ediciones electrónicas. \textit{El Juguete Rabioso} del escritor argentino Roberto Arlt es una novela centrada en la vida de un joven a principios del siglo XX, sin mucho futuro, algo molesto con la vida. Anterior a John Fante, me parece una novela muy cercana a \textit{Espera la Primavera Bandinni}, pero en versión latinoaméricana. La historia no es parecida, pero el estilo que posteriormente llamaron realismo sucio me parece ya se notaba desde Arlt. Es un libro más extenso, quizá si llama su atención pueda convenir conseguirlo impreso (debe haber edición ya en editoriales muy baratas), pero por si gustan y tienen la posibilidad pueden bajar la versión escaneada de aquí: \url{https://archive.org/details/RobertoArltElJugueteRabioso}.
|
||
|
||
\begin{thebibliography}{10}
|
||
\bibitem{Kozen} Kozen, Dexter C. ``Automata and Computability'' Springer (1997)
|
||
\end{thebibliography}
|
||
|
||
\end{document}
|