the halting problem

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Yat
Posts: 120
Joined: Tue Feb 03, 2009 2:05 pm UTC

the halting problem

Postby Yat » Wed Aug 05, 2015 12:16 pm UTC

Hello

I apologize in advance for how trivial this may seem for anyone that truly understands the halting problem and/or if this question has already been answered here, but my searches were not conclusive.

There is something I don't get in the halting problem, and none of the explanations I've read seem to cover it directly enough for me to understand. Basically, it is the fact that the inputs of the paradoxal machine would have to include the machine itself an infinite number of times for it to be a paradox. Now, let me just try and explain what I understand then where my problem is:

Let h(p,i) be a program that solves the halting problem, meaning that it returns 1 if the program p halts with input i, 0 otherwise.

The goal is to prove that no such h program can exist, so we imagine another program x(p,i) that internally uses h and works this way:
-if program p halts with input i, loop forever
-if program p does not halt, return 1

If h can exist, then we can easily implement x, so proving that x can't exist is enough to prove that h can't either.

Now, by feeding this program x to itself, we are supposed to reach a barber paradox type of thing, if x halts then it does not halt and so on.

OK, but x has inputs, so how exactly are we supposed to feed x to itself?

I understand that running x(x) does not make sense, because x takes a program and its input. But then, when we call x(x,x), the inputs of this calls are the program, which is x, and its inputs, which are x. That means that x(x,x) will do something about what happens when we launch x(x), which is not the same thing as x(x,x).

So, with my current understanding of the process, it is impossible to launch program x on itself, launched in the same context with a finite string of inputs, because there it peels a layer on each subsequent call.

Basically, as I understand it, we just need to know wether the empty program halts with no input or not. If the empty program halts with no input, then:
x() loops forever
x(x) returns 1
x(x,x) loops forever
x(x,x,x) returns 1
and so on.
If the empty program never halts, then it's just the opposite,but my point is that with this poor understanding of things that I have, there is no paradox in the fact that x(x,x) loops forever, because it is not a contradiction with the fact that x(x) or x(x,x,x) returns 1.

So, can anybody clarify how this works?

dalcde
Posts: 173
Joined: Fri Apr 06, 2012 5:49 am UTC

Re: the halting problem

Postby dalcde » Wed Aug 05, 2015 12:25 pm UTC

Yat wrote: OK, but x has inputs, so how exactly are we supposed to feed x to itself?


Why not? Real world example that does not explode:

Code: Select all

def func (input):
    print("Hello World!")
    return

func(func) # Prints Hello World!

Yat
Posts: 120
Joined: Tue Feb 03, 2009 2:05 pm UTC

Re: the halting problem

Postby Yat » Wed Aug 05, 2015 1:06 pm UTC

That is a function that does not use its input. What does it have to do with my question?

dalcde
Posts: 173
Joined: Fri Apr 06, 2012 5:49 am UTC

Re: the halting problem

Postby dalcde » Wed Aug 05, 2015 1:11 pm UTC

Yat wrote:That is a function that does not use its input. What does it have to do with my question?

It doesn't matter. Your function x does not have to evaluate itself with itself as an input. It merely receives the program and input, and checks whether it halts. For example, you could be passing x as a string (the source code), and x-as-a-program runs some checks on the string to decide whether it halts or not.

Yat
Posts: 120
Joined: Tue Feb 03, 2009 2:05 pm UTC

Re: the halting problem

Postby Yat » Wed Aug 05, 2015 1:24 pm UTC

dalcde wrote:It doesn't matter. Your function x does not have to evaluate itself with itself as an input. It merely receives the program and input, and checks whether it halts.
Wel... I obviously was not clear at all in my first explanations, this has nothing to do with my point. Let me try to reformulate based on your next sentence
dalcde wrote: For example, you could be passing x as a string (the source code), and x-as-a-program runs some checks on the string to decide whether it halts or not.
Ok, but with what inputs? By definition, x halts or not depending on its input. Here, x is supposed to decide wether x halts or not. But with which inputs ?
I mean, knowing wether x halts or not does not mean anything if you don't scpecify its intputs.

dalcde
Posts: 173
Joined: Fri Apr 06, 2012 5:49 am UTC

Re: the halting problem

Postby dalcde » Wed Aug 05, 2015 1:33 pm UTC

Yat wrote:
dalcde wrote:It doesn't matter. Your function x does not have to evaluate itself with itself as an input. It merely receives the program and input, and checks whether it halts.
Wel... I obviously was not clear at all in my first explanations, this has nothing to do with my point. Let me try to reformulate based on your next sentence
dalcde wrote: For example, you could be passing x as a string (the source code), and x-as-a-program runs some checks on the string to decide whether it halts or not.
Ok, but with what inputs? By definition, x halts or not depending on its input. Here, x is supposed to decide wether x halts or not. But with which inputs ?
I mean, knowing wether x halts or not does not mean anything if you don't scpecify its intputs.

I was responding specifically to how you can make x an input of itself. Might have had some miscommunication here.

I'm not sure where you got this proof from, but the explanation on Wikipedia seems pretty clear to me (and different from yours).

DISCLAIMER: I'm not an expert in anything related to computability.

Yat
Posts: 120
Joined: Tue Feb 03, 2009 2:05 pm UTC

Re: the halting problem

Postby Yat » Wed Aug 05, 2015 1:43 pm UTC

dalcde wrote:I was responding specifically to how you can make x an input of itself. Might have had some miscommunication here.
Indeed, sorry about that! feeding a function to itself was really not the problem.
dalcde wrote:I'm not sure where you got this proof from, but the explanation on Wikipedia seems pretty clear to me (and different from yours).
Well, from various places, including the wikipedia article. Can you tell me how it is different from mine ? Wikipedia's h is the same as my h, my x(i,i) would be wikipedia's g(i), with only inverting the output value, but it does not seem relevant as the point is just to see wether it halts or not.
dalcde wrote:DISCLAIMER: I'm not an expert in anything related to computability.
No problem, as long as the real proof is clear for you, that's good enough for me, I feel like I am the only one who does not understand it.

dalcde
Posts: 173
Joined: Fri Apr 06, 2012 5:49 am UTC

Re: the halting problem

Postby dalcde » Wed Aug 05, 2015 1:48 pm UTC

Yat wrote:Well, from various places, including the wikipedia article. Can you tell me how it is different from mine ? Wikipedia's h is the same as my h, my x(i,i) would be wikipedia's g(i), with only inverting the output value, but it does not seem relevant as the point is just to see wether it halts or not.


The wikipedia proof does not attempt to run x at all. It just uses your x as a test case to show that h is not the same as any other f.

User avatar
Xanthir
My HERO!!!
Posts: 5202
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: the halting problem

Postby Xanthir » Wed Aug 05, 2015 1:50 pm UTC

It sounds like you're not familiar with quines, which are programs that can print their own source code. They are similarly "impossible" - if the entire source code is in a string passed to a print statement, then there must be code in the program beyond just the string (at minimum, some quotes, and the print statement). Yet it's actually quite trivial to make quines in any language (in fact, there's a tool to automatically produce toy "quine rings" - program A print the source code to B, B print the code to C, ..., Z print the source code of A - for any combination/ordering of languages from a huge list). Tho many you'll find are just cheap tricks, there are plenty (infinite numbers, in fact) that are real-looking programs that could actually do real work, in addition to printing their own source code.

If you can print your own source code, you could write the program a little differently to do anything else to the source code you'd like, such as analyze it to determine if it halts.

Do not feel bad about this being non-obvious - I was blown away by quines when I first learned of them.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Yat
Posts: 120
Joined: Tue Feb 03, 2009 2:05 pm UTC

Re: the halting problem

Postby Yat » Wed Aug 05, 2015 1:55 pm UTC

Xanthir wrote:It sounds like you're not familiar with quines, which are programs that can print their own source code.
Well, I actually am, wrote one years ago in C, discovered recently that it was possible with compressed files too. The very last part is the one that really blew my mind. I mean, the fact that someone went through the effort of generating a zip file containing itself of course. Not the fact that it was theoretically possible :wink:

radams
Posts: 90
Joined: Fri May 14, 2010 12:49 pm UTC

Re: the halting problem

Postby radams » Wed Aug 05, 2015 2:08 pm UTC

Change your definition of x to this. x takes just one input, and:

x(p) internally uses h and works this way:
-if program p halts with input p, loop forever
-if program p does not halt with input p, return 1

Now x(x) halts if and only if x(x) does not halt.

There is an important point here: this is the moment where diagonalization appears in the proof. x must make use of its input p twice, once as code and once as data. It is this diagonalization that allows x to "use itself an infinite number of times".

Yat
Posts: 120
Joined: Tue Feb 03, 2009 2:05 pm UTC

Re: the halting problem

Postby Yat » Wed Aug 05, 2015 2:28 pm UTC

radams wrote:Change your definition of x to this. x takes just one input, and:

x(p) internally uses h and works this way:
-if program p halts with input p, loop forever
-if program p does not halt with input p, return 1

Now x(x) halts if and only if x(x) does not halt.

There is an important point here: this is the moment where diagonalization appears in the proof. x must make use of its input p twice, once as code and once as data. It is this diagonalization that allows x to "use itself an infinite number of times".

Well, I really don't know how this could have happened, but I actually just repeatedly missed the fact that the input was duplicated. Even in the wikipedia article I was stuck at the fact that h(h) did not make sense, which is not relevant.

Thank you for your patience! See, it did not take an expert in computability to pull my mind out of its own bias :?

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: the halting problem

Postby ahammel » Wed Aug 05, 2015 2:51 pm UTC

Yat wrote:
Xanthir wrote:It sounds like you're not familiar with quines, which are programs that can print their own source code.
Well, I actually am, wrote one years ago in C, discovered recently that it was possible with compressed files too. The very last part is the one that really blew my mind. I mean, the fact that someone went through the effort of generating a zip file containing itself of course. Not the fact that it was theoretically possible :wink:

I once ran across a quine that ran its own listing through Blowfish and decrypted it.
He/Him/His/Alex
God damn these electric sex pants!

Derek
Posts: 2136
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: the halting problem

Postby Derek » Fri Aug 07, 2015 6:12 pm UTC

Yat wrote:discovered recently that it was possible with compressed files too. The very last part is the one that really blew my mind. I mean, the fact that someone went through the effort of generating a zip file containing itself of course. Not the fact that it was theoretically possible :wink:

Holy shit that's amazing. I'm not surprised that it's possible, but I'm impressed that someone found one. Here is one, for the curious. (Strictly speaking this is not a quine, since it decompresses to an image plus another copy of itself, but it's the same idea.)

User avatar
Xanthir
My HERO!!!
Posts: 5202
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: the halting problem

Postby Xanthir » Fri Aug 07, 2015 10:25 pm UTC

It's still a quine *if* you start by placing it in a directory with that image. ^_^
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
phillip1882
Posts: 93
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

Re: the halting problem

Postby phillip1882 » Sun Aug 23, 2015 7:07 pm UTC

saw a video on you tube that explained it pretty well.
lets say you have 3 machines.
the halting program- always determines if a program will loop forever on a input or return some output. if it loops forever return "stuck" if halts with out put return "not stuck"
the negate - goes into infinite loop if receives the message "not stuck", halt and return "not stuck" if receive message "stuck"
the copy - takes a program, copies it converts the copy to a string, and submits both.

now we'll have the copy machine, send its output to the halting program, have the halting program send its output to the negate, and call this whole program X.

for the purposes of this explanation, we'll make he halting program simple. if the program contains a while true: is the only determing factor .

now well feed the program x into itself. so first program x gets copied so that halt program can read the input. and the program. now halt will only return "not stuck" if both the halt program and the negate don't contain a while true: in them. however, when not stuck reaches the negate, the negate goes into an infinite loop. so the halt program would be wrong. if either the halt program or the negate do contian a while true: then the halt program will return "stuck" but then the negate will not be stuck. in both cases halt program will be wrong about program X.
bitcoin address: 1B73mjAguoK9ATwVjGcy2LasyfG9xtLGsq

quantropy
Posts: 189
Joined: Tue Apr 01, 2008 6:55 pm UTC
Contact:

Re: the halting problem

Postby quantropy » Mon Aug 24, 2015 1:50 pm UTC

Yat wrote:OK, but x has inputs, so how exactly are we supposed to feed x to itself?

You're not, x takes two inputs, one of which is a program taking one input. So none of x(),x(x), x(x,x) makes sense.
Rather you need to define x(p) that internally uses h and works this way:
-if program p halts with input p, loop forever
-if program p does not halt, return 1

Then you can look at x(x) and so deduce a contradiction

My thought is that it's sorting out such details which are the important parts of Turing's and Gödel's proofs, rather than the contradictions due to self reference, which were known about beforehand.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 3 guests