- #1

- 530

- 32

The most known proof of undecidability of the halting problem is about like that:

Now consider D(D). There are two cases:

case1:

If H1(D, D)==False then, by definition of D, D(D) must halt.

But if H1(D, D)==False then, by definition of H1, D(D) must never halt.

case2:

H1(D,D)==True , then by the definition of D, D(D) must never halt.

But if H1(D, D)==True, then, by definition of H1, D(D) must halt.

In either case, we have a contradiction.

Therefore function that determines whether any program P halts on any input i does not exist.

It proves that function (lets call this function H1) with following properties cannot exist:

I noticed that this proof would not prove that function (lets call this function F3) with following properties would not exist:

With very similar proof to most known proof of halting problem we could also prove that function (lets call this function G) with following properties would not exist:

Does function F3 exist or function with such properties can not exist?

Does this make you think that there is a wide spread missunderstanding about halting problem?

Code:

```
#assume we have an hypothetical function that can determine whether any program P would halt on input i.
def H1(P, i):
"""
H1 is a hypothetical function that determines whether program P halts on input i.
Returns True if P halts on i, and False if P runs forever on i.
"""
raise NotImplementedError
#We also have such function:
def D(P):
if H1(P, P):
while True:
pass # Loop indefinitely.
else:
return # Halt.
```

case1:

If H1(D, D)==False then, by definition of D, D(D) must halt.

But if H1(D, D)==False then, by definition of H1, D(D) must never halt.

case2:

H1(D,D)==True , then by the definition of D, D(D) must never halt.

But if H1(D, D)==True, then, by definition of H1, D(D) must halt.

In either case, we have a contradiction.

Therefore function that determines whether any program P halts on any input i does not exist.

It proves that function (lets call this function H1) with following properties cannot exist:

- it takes 2 arguments (lets call these x1 and x2)
- returns False if call x1(x2) stays in infinit loop.
- returns True if call x1(x2) ever returns.

I noticed that this proof would not prove that function (lets call this function F3) with following properties would not exist:

- accepts 2 arguments(lets call these x1 and x2).
- returns false if x1==x2.
- returns False if x1!=x2 and call x1(x2) stays in infinit loop.
- returns True if x1!=x2 and call x1(x2) ever returns.

With very similar proof to most known proof of halting problem we could also prove that function (lets call this function G) with following properties would not exist:

- accepts 1 argument(lets call it x).
- returns NOT x(x) .

Does function F3 exist or function with such properties can not exist?

Does this make you think that there is a wide spread missunderstanding about halting problem?

Last edited: