Isn't the Halting Problem easily solvable?

[shivajikobardan]

Homework Statement

"halting problem is undecidable" proof

Relevant Equations

none

I mean just look at the loop and do an analysis if x=y (if there is a loop while(x=y)..)..I don't know why it is unsolvable. Can you give me some inituition, I will ask proof question later on.

 

[pbuk]

I mean just look at the loop and do an analysis if x=y

How will you compute every possible value of x and y?

 

[pbuk]

Anyway the (informal) proof that the halting problem is undecidable is simple by example.

# Assume the following function exists:
def halts(candidate):
    '''Returns True if `candidate` halts, otherwise False.'''

# Does the following function halt?
def undecideable():
    if halts(undecideable):
        while True:
            pass

 

[shivajikobardan]

Anyway the (informal) proof that the halting problem is undecidable is simple by example.

# Assume the following function exists:
def halts(candidate):
    '''Returns True if `candidate` halts, otherwise False.'''

# Does the following function halt?
def undecideable():
    if halts(undecideable):
        while True:
            pass

https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_21.pdf
this site has proved halting problem is undecidable, are they correct?

 

[Ibix]

are they correct?

Well, if they've proved it, yes, obviously.

There are trivial cases where you can see by inspection whether a program halts or not (e.g. while(true){ } or print "Hello world!") but it's undecidable in general, as shown by @pbuk's example of a program that is paradoxical if the halting problem is decideable.

 

[shivajikobardan]

Well, if they've proved it, yes, obviously.

There are trivial cases where you can see by inspection whether a program halts or not (e.g. while(true){ } or print "Hello world!") but it's undecidable in general, as shown by @pbuk's example of a program that is paradoxical if the halting problem is decideable.

this video uses some short method to prove this

source-:
This proof seems simple to me, is this correct? (Asking as there are lots of spams in youtube these days, can't trust anything naively).

 

[Ibix]

Have you compared the proofs to one another and to pbuk's version?

 

[shivajikobardan]

Have you compared the proofs to one another and to pbuk's version?

i didn't get it quite...maybe because my programming are bit rusty.

 

[pbuk]

Are you familar with other self-referential paradoxes such as "this statement is false" ?

i didn't get it quite...maybe because my programming are bit rusty.

 

[Jarvis323]

It's important to consider that the configuration space of a Turing machine is unbounded. This means that there is no limit to how many different configurations the the machine could go through as it performs a computation on an input, and it can run forever without repeating configurations (this is because they have an unlimited amount of tape/memory). And you should also consider that there are an unbounded number of possible Turing machines (or possible computer programs), the same as the set of natural numbers. If there were an algorithm that decides the halting problem, it would mean that there would be a single finite length program that, given any of the infinitely many possible programs, could answer yes or no if it will halt eventually.

To maybe understand why it would be hard, you can imagine trying to determine if the content of this thread up until now is written in binary somewhere within the digits of PI. While it may be possible to determine this analytically, it is still an open question. So at the moment, unless someone comes up with a proof, the only way to know would be to keep calculating more an more digits of PI and looking at them. It is perhaps likely that at some point this thread would be in there, but if so it would likely be very far off into into the digits and there would be know way to know for sure unless you look. And since there are infinitely many digits in PI, it is impossible to exhaustively search. We can only keep on looking, and as long as we don't find it we don't stop, and so if it's not there, then we never halt.

I don't know for sure if this is actually true for the question I posed about PI, but it is proven to be true of some other problems, that a search over an infinite space is the only way to possibly answer it. And any search over an infinite space will fail when the thing you are looking for doesn't exist.

As others have pointed out, there is a fairly simple proof that the halting problem is undecidable, based on self reference. It would be good to focus on understanding that.

In real life, machines usually have a bounded finite amount of memory and thus the number of possible configurations is limited. So it would be determinable whether a specific, real life, modern computer would halt on an input at some point (ignoring unpredictable external events) since a repeated cycle of configurations would imply it would never halt, and that would be guaranteed to happen if it doesn't halt.

 

[Jarvis323]

https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_21.pdf
this site has proved halting problem is undecidable, are they correct?

Here is another example modified from pbuks post:

def halts( candidate, y ):
    '''Returns True if `candidate` halts on input y, otherwise False.'''

def undecideable( x ):
    if halts( x, x ):
        run forever
    else: stop

Then consider what is the result of passing undecidable its own source code:

undecidable( <undecidable> )

Undecidable asks Halt if undecidable halts with itself as an input, and if it does, then it runs forever. This means that if undecidable halts on input <undecidable>, then undecidable doesn't halt on input <undecidable> and vice versa, which is a contradiction.

 

[shivajikobardan]

Are you familar with other self-referential paradoxes such as "this statement is false" ?

yes I'm familiar with self reference method of proof. that is what has been used in many places.

 

[pbuk]

So use it here:

Anyway the (informal) proof that the halting problem is undecidable is simple by example.

# Assume the following function exists:
def halts(candidate):
    '''Returns True if `candidate` halts, otherwise False.'''

# Does the following function halt?
def undecideable():
    if halts(undecideable):
        while True:
            pass

We assume that the halting problem is decidable i.e. that halts(candidate) works as defined.

If undecidable() halts then halts(undecidable) must return True, in which case undecidable() enters an infinite loop and does not halt at line 8, contradicting the assertion at the beginning of this sentence.

Can you complete this proof?