Lecture 24

The problem on the homework showed clearly. It is pretty easy to write a Turing program that writes as many 1's on the Turing tape as possible. It is however pretty difficult to get it to stop.

This observation begs the question, if it is possible to write a Turing program that decides if another given as input in some form terminates or not. The main result of this lecture will be that it is not.

Reading: Invitation to Computer Science Chapter 10.7.
Algorithmics Pages 204-209.