- #1

olgerm

Gold Member

- 533

- 34

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:

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.
```

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.

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

- 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: