Institut for Matematik og Datalogi Odense Universitet March 13, 1995

JFB

DM15 – F95 – Week 21

Lecture, March 6

We finished chapter 10 and through section 11.4 of chapter 11 in Sudkamp.

Lecture, March 13

We will finish through section 11.6 of chapter 11 in Sudkamp.

Lecture, March 20

We will finish chapter 11 in Sudkamp, and begin on chapter 12, probably covering the first three sections.

Problems to be discussed in week 12

• Do problem 7 on page 277 of Sudkamp.

• Do problem 8 on page 277 of Sudkamp.

• Do problem 9 on page 277 of Sudkamp.

• Do problem 11 on page 277 of Sudkamp. (Your solution to this problem can be given to Peter Høyer for comments in week 13.)

• Do the following question from a past DM15 exam:

Vis, at det generelt (dvs. for vilkårlige M og c) er uafgørligt, om en Turing-maskine M nogensinde skriver båndsymbolet c, hvis den startes på et tomt bånd.

• Do the following question from a past DM15 exam:

Vis, at det er afgørligt, om en Turing-maskine M nogensinde skriver et symbol, som ikke er blank, hvis den startes på et tomt bånd. Man skal altså beskrive en algoritme, der tager en Turing-maskine M som input, og som så svarer på, om den nogensinde skriver et symbol, som ikke er blank, hvis den startes på et tomt bånd.