Institut for Matematik og Datalogi Odense Universitet February 16, 1995

JFB

DM15 – F95 – Week 18

Lecture, February 13

We finished chapter 8 and covered through definition 9.2.2 of chapter 9 in Sudkamp.

Lecture, February 20

We will cover through section 9.5 in chapter 9 in Sudkamp.

Lecture, February 27

We will finish chapter 9 and probably most of chapter 10 in Sudkamp.

Problems to be discussed in week 9

• Do problem 10 on page 233 of Sudkamp.

• Do problem 12 on page 234 of Sudkamp.

• Do problem 17 on page 234 of Sudkamp.

• Do problem 18 on page 234 of Sudkamp.

• Do problem 19 on page 234 of Sudkamp.

• Do problem 24 on page 235 of Sudkamp. See problem 23 on the previous page for a definition of what it means for a TM to generate a set.

• For problems 18 and 19 on page 234, you will have to describe a TM. You may sketch the description, rather than giving all the details.