Institut for Matematik og Datalogi Odense Universitet March 14, 1995

JFB

DM15 – F95 – Week 22

Lecture, March 13

We finished through section 11.6 of chapter 11 in Sudkamp, and introduced the Post correspondence problem.

Lecture, March 20

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

Lecture, March 27

We will finish chapter 12 and most of chapter 13 in Sudkamp.

Problems to be discussed in week 13

• Do problem 13c on page 278 of Sudkamp.

• Do problem 14a on page 278 of Sudkamp.

• Do problem 15 on page 278 of Sudkamp.

• Do problem 16 on page 278 of Sudkamp.

• Do problem 17 on page 278 of Sudkamp.

• Prove that the following problem is undecidable; given a Thue system S and a string x, does x ⇒^{∗} λ in S? A Thue system is very similar to a semi-Thue system except that if u ⇒ v is a rule, then v ⇒ u is also rule, and this is written u = v. The only other difference is that either u or v may be λ.

• The following appeared in the newsgroup comp.theory recently. The poster seems to be looking for a DM15 student to help him out. See what help you could give him.

From: rjk@max.tiac.net (Robert J. Kolker) Newsgroups: comp.theory Subject: To Show the Equivalence Problem is Unsolvable Date: 4 Mar 95 02:06:53 GMT First of all what I am about to ask is not in connection with any course work since I am not enrolled in any school.

The problem: To show that it is recursively unsolvable to show when two turing machines are equivalent. That is both stop on the same inputs and give the same result or both run forever on the same inputs. I have tried to cast this in the same way as showing the stopping problem is unsolvable, but I have not succeeded. Any help you care to give will be greatly appreciated. Thank you. Bob Kolker