## the halting problem

**Moderators:** phlip, Moderators General, Prelates

### the halting problem

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?

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?

### Re: the halting problem

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!

### Re: the halting problem

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

### Re: the halting problem

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.

### Re: the halting problem

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

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

I mean, knowing wether x halts or not does not mean anything if you don't scpecify its intputs.

### Re: the halting problem

Yat wrote: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 sentencedalcde 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.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 ?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.

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.

### Re: the halting problem

Indeed, sorry about that! feeding a function to itself was really not the problem.dalcde wrote:I was responding specifically to how you can make x an input of itself. Might have had some miscommunication here.

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:I'm not sure where you got this proof from, but the explanation on Wikipedia seems pretty clear to me (and different from yours).

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 wrote:DISCLAIMER: I'm not an expert in anything related to computability.

### Re: the halting problem

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.

- Xanthir
- My HERO!!!
**Posts:**5228**Joined:**Tue Feb 20, 2007 12:49 am UTC**Location:**The Googleplex-
**Contact:**

### Re: the halting problem

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.

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

### Re: the halting problem

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 possibleXanthir wrote:It sounds like you're not familiar with quines, which are programs that can print their own source code.

### Re: the halting problem

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

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

### Re: the halting problem

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

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

### Re: the halting problem

Yat wrote: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 possibleXanthir wrote:It sounds like you're not familiar with quines, which are programs that can print their own source code.

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!

### Re: the halting problem

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

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

- Xanthir
- My HERO!!!
**Posts:**5228**Joined:**Tue Feb 20, 2007 12:49 am UTC**Location:**The Googleplex-
**Contact:**

### Re: the halting problem

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

- phillip1882
**Posts:**95**Joined:**Fri Jun 14, 2013 9:11 pm UTC**Location:**geogia-
**Contact:**

### Re: the halting problem

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.

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

### Re: the halting problem

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.

Opharmia Blog:Why I would opt for a classical economy

### Who is online

Users browsing this forum: No registered users and 5 guests