Comp Sci "Halting problem is undecidable" -- proof confusion

[shivajikobardan]

Homework Statement

Halting problem

Relevant Equations

None

https://slideplayer.com/slide/10708471/
This is the context I am talking about.

What contradiction occur here? We begin by telling that there is a Turing machine H that solves the halting problem. So how does this contradicts? Can you tell me about that?

 

[TeethWhitener]

This slide is a mess. There are plenty of good proofs of the undecidability of the halting problem online, but the basic idea is very straightforward (albeit somewhat unintuitive).

Start by assuming toward a contradiction that the halting problem is decidable. Essentially what that means is that there’s a program, $\text{Halt}(P(i))$ which takes an arbitrary program $P$ and the input to that program $i$ as its input and returns “True” if the program halts and “False” if the program runs forever. So for example, let’s say we have a program $X(n)$ that takes an input $n$ like so:

program x
do {
  n++;
} while (n > 10);
return 0;

Clearly if we enter $n=15$ as an input to this program, it will simply loop forever, adding 1 to $n$ over and over. If we enter $n=1$, then the program will halt immediately. So in this case, $\text{Halt}(X(15))=\text{False}$ and $\text{Halt}(X(1))=\text{True}$.

Now we consider another program $Q$ whose input is itself a program $P$:

program q
if Halt(p,p)=True then
  loop forever
else
  halt

This program halts if the halting program returns false (that is, if $P(P)$ loops forever) and loops forever if the halting program returns true (that is, if $P(P)$ halts). (NB--this part can be tricky to conceptualize; I'll try to explain in more detail at the bottom).

But now what happens when we put Q as its own input to Q: $Q(Q)$? Now if Q halts, then $\text{Halt}(Q(Q))=\text{True}$ and Q loops forever. And vice versa, if Q doesn't halt, then $\text{Halt}(Q(Q))=\text{False}$ and Q halts. We get our contradiction, which means such a halting function cannot exist. QED

More technical addendum: When I was first learning about this stuff, I always got stuck on the question "Why do we allow a program to take itself as an input?" For heuristic purposes, we can think of a program P in two different ways: first, as a function that takes a number i as an input and produces some output; or second, as a number. How does this work? Well, remember, all the programs stored in your computer are ultimately written in 0's and 1's--that is, they are represented as numbers. So at the machine code level, any program can be represented as a number. Thus, a program can have its own number as its input. (Note--There's a more formal way to do this, known as Godel numbering, but I feel like I'm already digressing too much.) We can try to illustrate this with our first example, the program $X(n)$. In your computer's memory, the program $X$ will be stored as a series of 0's and 1's, giving a number $x$. Let's assume WLOG that $x>10$. Now we have that $\text{Halt}(X(x))=\text{False}$; that is, $X$ runs forever with $x$ as an input. So what we're really saying with the halt function is that $\text{Halt}(a,b)$ takes two numbers as input and returns either True or False. The first number ($a$ in this case) is the number associated with the program--whether through machine code or Godel numbering or what have you. The second number $b$ is the number that gets put into the function $A$ that is represented by the number $a$.

Whew, that's a lot; I think I'll stop here for now.

 

[bhobba]

Just as a summary, assume you have a program called HALT (X). X is a program. HALT returns true if the program X halts else false if it loops.

Consider the following program P

Input X
If Halt(X)
Loop Forever
Else
Stop.

Case 1: Program P halts on input P. Hence, HALT returns true on input P. Hence, P loops forever. Contradiction

Case 2: Program P loops forever on input P. Hence, HALT returns false, and halts. Contradiction.

This means HALT does not exist.

Thanks
Bill

 

[SSequence]

@bhobba
I think there is a slight nuance in it (unless I am missing something). When we define the function HALT with only one parameter the problem becomes that we generally assume that the program P given as parameter to HALT(P) is given empty or 0 input. Now when you wrote:
"Case 1: Program P halts on input P. Hence, HALT returns true on input P."
and
"Case 2: Program P loops forever on input P. Hence, HALT returns false, and halts."

One problem that I see here is that, given your definition of HALT, value of HALT(P) doesn't depend on what input is given to the constructed program P. Perhaps I am missing something.========================================In the other thread I defined a function $G:\mathbb{N} \rightarrow \{0,1\}$. Let me call this function $halt_1:\mathbb{N} \rightarrow \{0,1\}$ here (since that is more suggestive).
(1) If the program with index $x$ loops forever when given the input $0$ then $halt_1(x)=0$.
(2) If the program with index $x$ halts when given the input $0$ then$halt_1(x)=1$.Also, consider the standard halt function based on two inputs. Let's write it as $halt_2:\mathbb{N}^2 \rightarrow \{0,1\}$. Often it is also written as $Halt:\mathbb{N}^2 \rightarrow \{0,1\}$ etc. too [as in post#2], but here let's use $halt_2:\mathbb{N}^2 \rightarrow \{0,1\}$. To avoid any confusion. Let's write its definition too:
(1) If the program with index $x$ loops forever when given the input $y$ then $halt_2(x,y)=0$.
(2) If the program with index $x$ halts when given the input $y$ then $halt_2(x,y)=1$.

There are at least two standard ways of showing that $halt_1:\mathbb{N} \rightarrow \{0,1\}$ is not a (total) computable function.
(a) We can use Rice's theorem probably I think. But honestly, it has been more than few years since I last looked at this stuff so I will have to double check the statement of the theorem and also whether it is directly applicable. In general that theorem can be used to show number of functions as non-computable.

(b) The more direct method is to first show that $halt_2:\mathbb{N}^2 \rightarrow \{0,1\}$ is not a (total) computable function. Now let's suppose that $halt_1:\mathbb{N} \rightarrow \{0,1\}$ was a (total) computable function. Now we can show that if $halt_1:\mathbb{N} \rightarrow \{0,1\}$ was computable then $halt_2:\mathbb{N} \rightarrow \{0,1\}$ must be computable too. This allows us to conclude that our assumption of $halt_1:\mathbb{N} \rightarrow \{0,1\}$ being a computable function was false.========================================Finally regarding the point as to why $halt_2:\mathbb{N} \rightarrow \{0,1\}$ must be computable if $halt_1:\mathbb{N} \rightarrow \{0,1\}$ was computable. It is a bit difficult to explain for me. The usual result that is used in it is formally called "s-m-n theorem" or "parameter theorem". But honestly, I have kind of forgotten its precise statement too [though I re-call the theorem being easy once you know the underlying notation]. The theorem is essentially a more precise form of intuition of placing inputs in the beginning (which I try to describe below). Nevertheless if one has some specific language setup in mind then the idea below could also be implemented directly.In any case, here is the basic idea behind showing the result in previous paragraph. Suppose you have to determine the halting of function f(100) where we have:
int f (int x)
**body of funtion f**
end

We can use a slight trick here. We construct a slightly modified function g such that g(0) halts iff f(100) halts.
int g(int x)
y:=100
**body of funtion f with variable x replaced with y**
endThe point here being that whenever we have to determine that $halt_2(a,100)$ is true essentially we modify the program P1 with index $a$ to form another program P2 with index $c$. Program P2 has the same body as program P1. However, in the body of P2, the input variable is replaced with some other variable $t$. Also, at the beginning of program we place a statement of the form:
$t:=100$

Now the program P2 halts on input $0$ iff the program P1 halts on input $100$.

 

[bhobba]

Nice reply and I gave it my like.

I see your point. It is nonsense to try and check if a routine that accepts a parameter halts or loops because what it will do depends on the parameter passed. No program can ever determine that. That is why you require HALT to accept two parameters - one parameter is the routine to be checked (P), and that routine requires one parameter. And the other parameter is the parameter to be passed (I).

Here is hopefully a better proof.

Halt (P, I) returns True if and only if P halts on I otherwise it returns false.

Z (X)
If Halt(X, X) then
Loop Forever
Else Halt.

Consider what happens when Z is run with input Z. This does not have the same problem because Z has an input which is simply a string.

Case 1: Program Z halts on input Z. Hence, by the correctness of the Halt program, Halt returns true on input Z, Z. Hence, program Z loops forever on input Z. Contradiction.

Case 2: Program Z loops forever on input Z. Hence, by the correctness of the Halt program, Halt returns false on input Z, Z. Hence, program Z halts on input Z. Contradiction.

Hopefully this is better. Fingers crossed.

Thanks
Bill