CS200: Computer Science, Spring 2004
Notes: Monday 5 April 2004
- Wednesday, 7 April: Problem Set 7
- Wednesday, 7 April: Problem Set 8 Team Requests
- Exam 2 will be handed out on 14 April and due on 19 April.
NotesUniversal Turing Machine
A Turing Machine that can simulate any other Turing Machine on an input: TMU (P, I) = the output of running TM-P on input I
What is a calculus?
What properties make Scheme too complex to be a good model of computation?
Lambda Calculus is a set of rules for manipulating symbols. They can be given meanings that map well to computation.
Lambda Calculus Term Grammarterm ::= variable
term ::= term term
term ::= ( term )
term ::= λ variable . term
RulesAlpha Reduction: (renaming variables)Uninteresting Reduction Rulesλ y . M →α λ v . M [y |→ v]) where v does not occur in M.We can change the name of a lambda variable by replacing all occurances of the variable in the body term with a new name that does not appear in the body term.
Beta Reduction: (substitution)(λ x . M) N →β M [ x |→ N ]All computation can be modeled using Beta Reduction!
M → M
PM → PN if M → N
MP → NP if M → N
λ x . M → λ x . N → if M → N
M → P if M → N and N → P
Identity and Composition
I ≡ λ x . x
C ≡ λ x . (λ y . yx)
CII = (λx.(λy. yx)) (λx.x) (λx.x)
λ f . ((λ x . f (xx)) (λ x . f (xx)))