I have a very basic exposure to algorithms. I am a graduate in Mathematics. I was reading Halting Problem in the book Discrete Mathematics with applicationbs by Susanna Epp. It has a following theorem :
Theorem : There is no computer algorithm that will accept any algorithm X and data set D as input and then will output "halts" or "loops forever" to indicate whether or not X terminates in a finite number of steps when X is run with data set D.
Proof : Suppose there is an algorithm, call it CheckHalt, such that if an algorithm X and a data set D are input, then CheckHalt prints "halts" if X terminates in a finite number of steps when run with the data set D or "loops forever" if X does notterminate in a finite number of steps when run with data set D.
Now next lines are those which I don't understand in this proof
Observe that the sequence of characters making up an algorithm X can be regarded as a data set itself. Thus it is possible to consider running a CheckHalt with input (X,X).
So I have understood that CheckHalt essentially gets input as an algorithm X and a data set D. It tells whether if we run the algorithm X with that data set D as it's (X's) input, then X will halt or loop forever. Thus CheckHalt(X,D) seems good.
My question is how can an algorithm X have an input X itself i.e how can we call an algorithm as a data set?
What is the meaning of the sentence "sequence of characters making up an algorithm X"?
I can understand CheckHalt(X,D). But what is CheckHalt(X,X)?
Thanks.
When it talks about an algorithm X, it is talking about a set of instructions ... for example, when I tell you how to do addition of two numbers, I might say 'start with the two digits on the right, add those up, and write down the sum and the possibly carry-over. Then, ....'
Now, notice that these instructions are expressed in English, but I could have used any other language as well. Computers of course have their own language too, usually binary. Anyway, it is some language we ar using, and the computer program is a string of symbols following that language.
So, don't think of X as the actual 'running program', but rather as the description of what needs to be done: a program is just a description of a process, and only when the program is being executed will that process actually take place.
In sum: the algorithm/computer program X is a string of characters that happens to be a set of instructions.
But the 'data set' D is any kind of string of symbols. That of course does not mean that D is a set of instructions, but it could be. Hence, you can use X as a specific kind of data set; a data set that happens to be a computer program.
And so we can pass X as an argument to the CheckHalt routine, which will treat the first argument X as a computer program, and the second argument (also X) as a string of symbols that the computer program X is supposed to work with (that is, CheckHalt is going to try and determine whether the computer program X, when it is being executed and will work on input symbol string X will halt or not)