@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##.
