Formalism 101
Escaping local optima on a random walk through life.
1 Formal Languages
1.1 An alphabet
1.2 Words over an alphabet
1.3 The empty word
1.4 Concatenating two words over
1.5 The Kleene star
We define it inductively:
If
and ,
then
The elements
1.6 A formal language
2 Grammars
2.1 A grammar
is an alphabet of nonterminal symbols, is an alphabet of terminal symbols, is a finite set of production rules, which are elements and for . is the start symbol.
Note that
2.2 Every grammar
The binary relation
3 Formal Systems
3.1 A formal system
- an alphabet
, which is a finite set of symbols, - a grammar
over , which describes how valid formulas can be built from the symbols in the alphabet ( is the set of valid formulas), - a set of axioms and axiom schemata
, which are valid formulas that are assumed to be true, and - a set of inference rules
for inferring theorems from the axioms and one another.
Schemata are formulas in the metalanguage of the system that generalize formulas in that systems language and thus allow the formulation of an infinite amount of axioms of the same structure. A good example is the induction schema of the Peano axioms for the natural numbers.
Within such a system, we can use its grammar to build valid formulas from the symbols contained in its alphabet and we can use its inference rules to derive theorems from its axioms and thus prove them.
4 The Lambda Calculus
4.1 The lambda calculus is a formal system for expressing computation. Like Turing machines, it’s a universal model for doing so, i.e. the lambda calculus is turing complete. However, it’s a lot simpler and in my opinion also more elegant than the bulky Turing machines. It’s also the fundament to functional programming languages, like Haskell.
We can now use the basic concepts defined above to define the untyped lambda calculus.
The untyped lambda calculus is the formal system
, , defined inductively, , , as defined below.
5 Lambda Expressions
5.1 We’re writing
- Variables: All variables
are lambda expressions, so . - Abstraction: For every variable
and every , we have as well. - Application: For every
, we also have .
Sometimes the
We can also define