In this file, we introduce a very simple problem and prove that it is undecidable.
We start by assuming that you know what a Pascal program is. We use Pascal because it is simple-minded.
What version of Pascal? Well, of course it really doesn't matter, so let's say, the one that is used by the compiler "pc" on our system.
If you don't know that language, just replace the word "Pascal" by the name of your favorite programming language.
Let L_pascal be the Pascal language itself. The alphabet will be the set of all ASCII symbols. A string is in L_pascal if it is a Pascal program.
We imagine that a Pascal program runs on a machine with unlimited resources. That means that no program is too large, and the machine will run until the program halts or crashes, or will run forever, and the machine will never run out of dynamic memory. Such a machine is called a Pascal machine. Obviously, since it has unlimited resources, you cannot build a Pascal machine.
A pascal program sometimes reads from a standard file called "input." This file could be the program itself.
We define L_d to be the language of all Pascal programs w such that, with input w itself, w does not halt.
The program w_2 is not in L_d.
Can you decide whether the program w_3 is in L_d? Don't look at the answer until you try to figure it out on your own.
You will not be able to figure out whether the program w_4 is in L_d.
Theorem: L_d is not recursively enumerable.
Proof: By contradiction. Assume that L_d is recursively enumerable. Then there is a Turing Machine M which accepts L_d.
Since you can write a Pascal program that emulates any given Turing machine, there must be a Pascal program p that halts on input w if and only if w is a member of the language L_d.
We now ask, is p a member of the language L_d? If it is, then p will detect that by halting if given p as its input. But if it halts with itself as input, then, by the definition of L_d, it is not a member of the language L_d.
On the other hand, if p is not a member of the language L_d, then, by definition of p, it cannot halt when given p as its input. But then, by definition of L_d, it is a member of the language L_d.
Note that p cannot be a member of L_d, but it also cannot be not a member of L_d. This is a contradiction.
We conclude that the assumption that L_d is recursively enumerable must be false.
Since L_d is not recursively enumerable, it is also not recursive, since that is a subclass. Recall that a language is recursive if and only if it is decidable.
Given a Pascal program w and an input file x, we would like to know whether w halts if given x as its input. This problem is undecidable, as we prove below.
Theorem: The Halting Problem is undecidable.
Proof: By contradiction. Assume that the Halting Problem is decidable. Then, given any Pascal program w, we can decide whether w halts if given itself as its input file, since that is a special case of the Halting Problem. That, of course, would allow us to decide whether w is a member of the language L_d. Since L_d is undecidable, this is a contradiction.
We conclude that the Halting Problem is undecidable.