University of Virginia Computer ScienceCS150: Computer Science, Fall 2005 |
(none)7 November 2005 |

- Now: Problem Set 7
- Tuesday, 8 November (11:59pm): Problem Set 8 project descriptions (note: extended one day from PS8 handout)
- Wednesday, 9 November, 7pm: Exam 2 review session
- Monday, 14 November: Exam 2 (out
**Friday 11 November**) - Monday, 5 December: Problem Set 8 Presentations/Final Reports

The Exam 2 Study Guide contains sample questions from previous Exams on the topics your Exam 2 will cover.

How do we prove a model of computation is equivalent to a Turing Machine?

**Lambda Calculus**

term::=variable|termterm|(term)|λvariable.term

**Alpha Reduction**: (renaming variables)

λWe can can change the name of a lambda variable, but replacing all occurances of the variable in the body term with a new name that does not appear in the body term.y.M→_{α}λv.M[y|→v]) wherevdoes not occur inM.

**Beta Reduction**: (substitution)

(λx.M)N→_{β}M[x|→N]

(λ *f* **.** ((λ x **.** *f*
(*x**x*)) (λ *x* **.** *f*
(*x**x*)))) λ *x* **.** *x*

**T** ≡ λ *x* (λ *y* **.** *x*)

**F** ≡ λ *xy* **.** *y*

**if** ≡ λ *pca* **.** *pca*

**cons** ≡ λ *xy* **.** (λ *z* **.** *zxy*)

**car** ≡ λ *p* **.** *p* **T**

**cdr** ≡ λ *p* **.** *p* **F**

**null** ≡ λ *p* **.** **T**

**null?** ≡
λ *x* **.** (*x* λ *y* **.**
λ *z* **.** **F**)

**zero?** ≡ **null?**

**pred** ≡ **cdr**

**succ** ≡ λ *x* **.** **cons** **F**
*x*

**0** ≡ **null**

**1** ≡ **succ** **0** ≡ **cons** **F** **null**

**2** ≡ **succ** **1** ≡ **cons** **F** (**cons** **F** **null**)

Guy L. Steele, *Growing
a Language*, OOPSLA 1998 Keynote. Guy Steele was a
co-designer of Scheme, and one of the leading proponents of Java (and
a co-author of the Java Language Specificaion). The second page shows
a machine that is equivalent to a Turing Machine. If you are bothered
by the sexist language in this paper (of course, unlike more authors
Steele had a particularly good reason for writing this way), read
Douglas Hofstadter's *A
Person Paper on Purity in Language*. If you weren't bothered
by the sexist language in this paper, you should especially read
Douglas Hofstadter's *A
Person Paper on Purity in Language*. Read the Post Scriptum
on this essay before you find it offensive.

My account of truth is realistic, and follows the epistemological dualism of common sense. Suppose I say to you 'The thing exists' -- is that true or not? How can you tell? Not till my statement has developed its meaning farther is it determined as being true, false, or irrelevant to reality altogether. But if now you ask 'what thing?' and I reply 'a desk'; if you ask 'where?' and I point to a place; if you ask 'does it exist materially, or only in imagination?' and I say 'materially'; if moreover I say 'I mean that desk,' and then grasp and shake a desk which you see just as I have described it, you are willing to call my statement true. But you and I are commutable here; we can exchange places; and, as you go bail for my desk, so I can go bail for yours.

William James' explanation ofThe Meaning of Truthin 1911.

We'll stick with theT≡ λx(λy.x) version.

CS 150: Computer ScienceUniversity of Virginia |
evans@cs.virginia.eduUsing these Materials |