4-8-2025 - Lambda-Calc and Turing Machines

Turing Machines

Sharpie and an Infinitely Long Roll of Toilet Paper

Lambda Calc

$$\begin{array}{r}S\to x\text{ (variable)}\\ |\lambda x.S\text{ (function)}\\ |SS\text{ (application/function call)}\\ |(S)\end{array}$$

Valid Sentences “a” b x $\lambda x.x$ $\lambda x.y$ $\lambda x.\lambda y.a$

Beta Reduction

To apply or call a function (to reduce the expression)

Beta Normal Form (BNF): a property of a lambda calc expression A expression is in Beta Normal Form if it cannot be reduced any further. Weak-Head Normal Form (WHNF)

$$\lambda x.xa\ne (\lambda x.x)a$$ $$a(\lambda x.x)=a\lambda x.x$$

Rule 1: Scoping of Functions

The body of a function extends to the end of the expression or the context dependent closing right parenthesis.

Rule 2: Lambda Calculus is Left-Associative

Bound Variable (bound by a lambda expression) Free Variable Free variables always stay free, bound variables always stay bound

Alpha Conversion

Convert bound variables to be unique