ComboPost

\documentclass[12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amsfonts,amssymb,amscd,amsthm,xspace}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}


\renewcommand\qedsymbol{\Phi}

\begin{document}

\begin{center}
{\Large Combinators}\\
\text{Daniel Mandragona}\\ %You should put your name here
02/22/17 %You should write the date here.
\end{center}

\begin{enumerate}


\item Well we are finally here! We now have all the necessary knowledge to formally learn about combinators. \textbf{Combinators} are functions that possess only bound variables. Combinators do not have free variables. These functions produced a field of study called Combinatory Logic. An interesting fact about $\lambda$-Calculus is that although every lambda function is created by means of abstraction and application, abstraction is not required. Because of this fact, a similar calculus called combinatorial calculus was created. This calculus is computationally equivalent to $\lambda$-Calculus and thus Turing Complete, but only relies on combinators for means of computation. There are many different important combinators that we will now discuss.
\begin{itemize}
\item The identity combinator, $\mathbf{I}$. $\lambda x.x$. If we apply this combinator with any term $t$ then we get $t$ back. This combinator is usually denoted as $I x = x$ or $I(x) = x$.
\item The next combinator is the constant combinator, $\mathbf{K}$. $\mathbf{K} = \lambda x.(\lambda y.x)$. This combinator takes two arguments $x$ and $y$, and returns $x$ regardless of what the argument $y$ is. This is why it is referred to as the constant combinator. For all terms $x$ and $y$ in the lambda calculus, $\mathbf{K}\,x\,y = x$ or in alternative notation $\mathbf{K}(x,y) = x$.
\item The third combinator that we will cover is the substitution combinator, $\mathbf{S} = \lambda x.[\lambda y.[\lambda z.(xz)(yz)]]$. This combinator takes three arguments,$x,y,z$, and begins by applying the first two arguments with the third and then combines these two results. We need this combinator to make up for the lack of the abstraction tool in our combinatorial calculus. ????NOT SURE IF THIS IS TRUE THIS IS JUST A GUESS(need to check with fontaine)???? The reason why \textbf{S} is able to help us is that our current calculus is left associative, but certain computations require right associativity. Without \textbf{S} we could attempt to create the result of this combinator with just $xzyz$, but by association this would become $(((xz)y)z)$.
\item We can solve this abstraction issue with different combinators though. Consider X(X(X(XX))) = X(X(X[(((xS)KS)K)]
[((((XS)KS)KS)KS]K


\end{itemize}


\end{enumerate}


\end{document}