University of Virginia Computer Science CS150: Computer Science, Fall 2005 |
(none) 26 October 2005 |
Structured like a newspaper, the talk and the book on which it's based investigate the mathematical angles of stories in the news and offer novel perspectives, questions, and ideas to those who can't get along without their daily paper.
A Turing Machine that can simulate any other Turing Machine on an input: TM_{U} (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 Grammar
term ::= variable
term ::= term term
term ::= ( term )
term ::= λ variable . term
Rules
Alpha 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)
→_{β}
Example
λ f . ((λ x . f (xx)) (λ x . f (xx)))
(Note: you may need some more space to finish this one.)
CS 150: Computer Science University of Virginia |
evans@cs.virginia.edu Using these Materials |