Problem Sheets

Each week a problem sheet will be posted which you should either complete or work at for 2 hours (whichever is shorter). The schedule is designed so that you can attempt the problem sheet already after watching the first lecture of each week. In weeks 1 and 2, I recommend also watching the supplementary lecture before attempting the problem sheet because you will be asked to prove some simple logical statements.

You will only succeed on this unit by carefully attempting the problem sheets.

The problems are graded from 1 to 3 stars. A 1-star problem is usually just a matter of calculation after a close reading of the relevant definitions. A 2-star problem requires some thought and possibly a proof, but it follows a similar pattern to something we saw in lectures. A 3-star problem requires some new insight and probably an element of trial and error (a.k.a luck) because you have not seen problems of a similar shape before.

As extra practice, try to prove that the pure, untyped lambda calculus is Turing-complete by following Eddie’s exercises here.

Marking and the Problem Class

It is highly recommended that you submit your solutions to Eddie and Sam for marking. You can do this by emailing a copy to your TA with deadline 5pm on Thursday. Your sheet will be returned to you in the problem class.

This means you should probably try to block out 2-3 hours of time to work on the problems on Wednesday or Thursday.

• Samantha Frohlich: sf16540
• Eddie Jones: ej16147

You have been allocated to one of the two problem classes. It will take the form of a video call hosted on Teams, in the Class E (for Eddie) or Class S (for Sam) channel. To attend, go to the channel at 4pm on Tuesdays and wait until a new meeting post appears and you will find a little “Join” button to one side. Click this button to enter the class.