Halting Undecidability proof faulty?

[Kriminal99]

Ok time to summarize this thread:

1) For the vast majority of programs that anyone is actually going to write (especially if they are not number theorists), the halting problem is decidable.

2) The so called proof of undecidability (by contradiction) makes use of a very convaluted setup that is not representitive of a program that anyone would actually write.

The halting proof diagnolization argument implies an algorithm that simulates an input machine on it's own encoding. This is the realization of "diagonolization". This algorithm takes one input, copies it, and then gives the original input code the copy as input. It must do so in order to ensure that the program runs only on itself. Call this machine G.

Because of the fact that the halting algorithm needs algorithm "code" and input to that code, it is necessary that the halting algorithm traces the input machine to some degree. It must be traced a certain amount in order for it to gain meaningful information. I claim that the amount required ensures it would trace it through the action of copying the input and running H in the case of Machine G.

So, G recieves (G) as input. (G) is the code of G. G copies the (G) and gives (G)(G) to the halting algorithm. The halting algorithm traces G on (G). And we are back where we started - an infinite loop.


This infinite trace loop that causes the halting machine to break down is completely unique to this kind of unrealistic setup. It would not even occur if a halting machine ran on itself without the copying preprocessor, because then the trace loop would stop when the input of what to trace ran out.

Because undecidability is technically defined such that it is something that is true or not true for ALL machines, theorists maintain that the proof is valid. However, all this proof shows is that the problem is undecidable for the single machine B. For every other machine it says nothing at all.

So Undecidable contains one nonsense element, and decidable contains infinite pratical elements. And then there are some more impratical elements to undecidable, which involve things like using a computer program to answer unanswered questions in number theory.

[Buffy]

Originally Posted by Kriminal99

A halting machine attempting to operate upon itself would cease it's normal function and simply always loop.

A function which gives 0 if the input function is defined would cease it's normal function and always loop if operated upon itself.

The Halting Problem requires *both* the function and a *finite* input. If as you suggest, you do an infinite regress of feeding the halting algorithm itself with the input to the algorithm itself, with the input to the algorithm itself, with the input to the algorithm itself, ad nauseum, then you've really only proved the theorem correct!

The Halting Problem theorem is only saying that a *general* algorithm cannot be developed that works for *all* function/finite-input pairs. You could feed the algorithm to itself with a *different* finite input, and it would halt. The fact that the infinite regress case does not work simply proves the theorem.

So,

Originally Posted by Kriminal99

Every Halting problem undecidability proof asks us to assume that such functions could operate on themselves.

is not at all an "assumption" its the fact that proves the theorem....

People seldom see the halting and painful steps by which the most insignificant success is achieved,
Buffy

[Kriminal99]

Originally Posted by Buffy

The Halting Problem requires *both* the function and a *finite* input. If as you suggest, you do an infinite regress of feeding the halting algorithm itself with the input to the algorithm itself, with the input to the algorithm itself, with the input to the algorithm itself, ad nauseum, then you've really only proved the theorem correct!

The Halting Problem theorem is only saying that a *general* algorithm cannot be developed that works for *all* function/finite-input pairs. You could feed the algorithm to itself with a *different* finite input, and it would halt. The fact that the infinite regress case does not work simply proves the theorem.

So,

is not at all an "assumption" its the fact that proves the theorem....

People seldom see the halting and painful steps by which the most insignificant success is achieved,
Buffy

Aww isn't that cute... I didn't say anything about feeding it anything infinite. I said that any halting machine which was fed a finite encoding of itself would cause an infinite regress instead of going through it's normal function.

Thus the only thing proven is that it cannot operate on itself. It could still very well exist and handle all other machine/input combos.

[Buffy]

Originally Posted by Kriminal99

Aww isn't that cute... I didn't say anything about feeding it anything infinite. I said that any halting machine which was fed a finite encoding of itself would cause an infinite regress instead of going through it's normal function.

That's what I said too! And yes, its very cute!

The program itself is of finite length. It's input is itself, but the only way to get "infinite regress" is to apply the input to the input to the input, each discrete input is indeed finite, and that's what you appeared to be talking about. Without this, there's no possibility for "infinite regress."

There's nothing special about the nature of a Halting Problem Program: it's just an arbitrary algorithm. Saying that *by definition* feeding a Halting Problem Program to itself would cause infinite regress does not really make any sense without making lots of assumptions about what makes up such a program. You'll need to explain what you're talking about in more detail to get past this issue.

Originally Posted by Kriminal99

Thus the only thing proven is that it cannot operate on itself. It could still very well exist and handle all other machine/input combos.

What is clear is that:

1. If your assumption that no Halting Problem Program can resolve its own halting status for itself, then the theorem is by definition proven. Your assumption is that it never completes, then it's halting status is undecidable, showing that there's at least one instance of an algorithm that is not decidable.
2. You could even circumscribe the recursive case, and you can still prove that the halting problem is undecidable: Your assumption that "Every Halting problem undecidability proof asks us to assume that such functions could operate on themselves" is actually not the case, heck the proof in the Wikipedia page on the topic doesn't make this assumption, and there are other approaches as well. So its actually unnecessary to make this exception.

If you'd like to take a stab at the notion that all Halting Problem Programs result in infinite regress or otherwise do not halt given themselves as input, we might have an interesting discussion, but you need to prove it: its not true by definition.

But even then, it does not have any impact on whether or not the Halting Problem Theorem is false.

Not to see many things, not to hear them, not to let them approach one--first piece of ingenuity, first proof that one is no accident but a necessity,
Buffy

[Kriminal99]

Originally Posted by Buffy

That's what I said too! And yes, its very cute!

The program itself is of finite length. It's input is itself, but the only way to get "infinite regress" is to apply the input to the input to the input, each discrete input is indeed finite, and that's what you appeared to be talking about. Without this, there's no possibility for "infinite regress."

There's nothing special about the nature of a Halting Problem Program: it's just an arbitrary algorithm. Saying that *by definition* feeding a Halting Problem Program to itself would cause infinite regress does not really make any sense without making lots of assumptions about what makes up such a program. You'll need to explain what you're talking about in more detail to get past this issue.


What is clear is that:

1. If your assumption that no Halting Problem Program can resolve its own halting status for itself, then the theorem is by definition proven. Your assumption is that it never completes, then it's halting status is undecidable, showing that there's at least one instance of an algorithm that is not decidable.
2. You could even circumscribe the recursive case, and you can still prove that the halting problem is undecidable: Your assumption that "Every Halting problem undecidability proof asks us to assume that such functions could operate on themselves" is actually not the case, heck the proof in the Wikipedia page on the topic doesn't make this assumption, and there are other approaches as well. So its actually unnecessary to make this exception.

If you'd like to take a stab at the notion that all Halting Problem Programs result in infinite regress or otherwise do not halt given themselves as input, we might have an interesting discussion, but you need to prove it: its not true by definition.

But even then, it does not have any impact on whether or not the Halting Problem Theorem is false.

Not to see many things, not to hear them, not to let them approach one--first piece of ingenuity, first proof that one is no accident but a necessity,
Buffy

I do not have to prove that this would happen - that it is not true is an assumption that the undecidability proof makes. And therefore it is just as likely if not more likely to be the cause of the contradiction that results.

IE if there exists a halting machine H that always loops if run on itself but otherwise works, the halting problem is still possibly decidable except for halting machines. Which is very likely a trivial distinction from the idea that the halting problem is possibly solvable.

That being said there is pretty good reason to believe that such an infinite regress really would occur. Any halting machine run on itself would at some point try to trace at least a part of its own computations - at which point it would redo everything it had done up to that point when it would again restart and so forth. Each time it would be tracing an additional level of depth.

The wikipedia "proof" does assume that the g function could operate on itself. Note where it says that the function g corresponding to the halting problem is the eth possible input to the halting function. It's asking us to run:

g(g()), which tests h(g(),g())

So here g traces it's own computation creating the same infinite regress.

[Buffy]

Originally Posted by Kriminal99

I do not have to prove that this would happen - that it is not true is an assumption that the undecidability proof makes. And therefore it is just as likely if not more likely to be the cause of the contradiction that results.

Yes you do. The theorem makes no assumption of that the Halting Problem Program must use itself as input.

Originally Posted by Kriminal99

The wikipedia "proof" not only assumes that both involved functions could operate on themselves, they do not specify a finite input as you seemed to require. Note where it says that the function g corresponding to the halting problem is the eth possible input to the halting function. It's asking us to run:

g(g()), which tests h(g(),g(?))

But that's not a requirement for the proof! The core of the proof is simply that the f() algorithm is different from h() .

For your argument to disprove the theorem, you need to demonstrate why Halting Problem Programs are somehow different than any other algorithm in a fundamental way.

That the operation is "recursive" is of no consequence: an algorithm is an algorithm. There's no special effect on *any* algorithm simply because it takes itself as input. That's quite non-sensical.

In other words:

Originally Posted by Kriminal99

IE if there exists a halting machine H that always loops if run on itself but otherwise works, the halting problem is still possibly decidable except for halting machines. Which is very likely a trivial distinction from the idea that the halting problem is possibly solvable.

Yes, it's not only trivial because you've simply assumed that there is such an algorithm, it's more than insufficient in showing any sort of weakness in the proof.

Originally Posted by Kriminal99

That being said there is pretty good reason to believe that such an infinite regress really would occur. Any halting machine run on itself would at some point try to trace at least a part of its own computations - at which point it would redo everything it had done up to that point when it would again restart and so forth. Each time it would be tracing an additional level of depth.

Why are you making assumptions about what a halting machine would do? Isn't that the very charge that you are laying against the proof?

Why should your argument--for which you are providing no evidence or logic at all--be taken at face value when that is the very weakness you're--quite incorrectly--accusing the theorem of doing?

Human speech is like a cracked kettle on which we tap crude rhythms for bears to dance to, while we long to make music that will melt the stars,
Buffy

[Kriminal99]

Originally Posted by Buffy

Yes you do. The theorem makes no assumption of that the Halting Problem Program must use itself as input.
But that's not a requirement for the proof! The core of the proof is simply that the f() algorithm is different from h() .

For your argument to disprove the theorem, you need to demonstrate why Halting Problem Programs are somehow different than any other algorithm in a fundamental way.

That the operation is "recursive" is of no consequence: an algorithm is an algorithm. There's no special effect on *any* algorithm simply because it takes itself as input. That's quite non-sensical.

In other words:

Yes, it's not only trivial because you've simply assumed that there is such an algorithm, it's more than insufficient in showing any sort of weakness in the proof.

Why are you making assumptions about what a halting machine would do? Isn't that the very charge that you are laying against the proof?

Why should your argument--for which you are providing no evidence or logic at all--be taken at face value when that is the very weakness you're--quite incorrectly--accusing the theorem of doing?

Human speech is like a cracked kettle on which we tap crude rhythms for bears to dance to, while we long to make music that will melt the stars,
Buffy

In a proof by contradiction, you don't have to explicitly state that you are making an assumption. Any logical assumption you make, whether you recognize it or not, can be the cause of the contradiction.

The proof assumes that the halting machine can operate on itself, by operating the machine on itself during the course of the proof and assuming it behaves as it normally would.

It isn't an issue of disproving the "proof". "proofs" make assertions, and this assertion either fails due to a logical oversight, or if you simply define the halting machine in the proof to be able to operate on itself then it proves nothing more than that there can be no halting machine that operates normally on itself. There could still be one that doesn't work on itself.

The fact that my philosophical knowledge alerts me to the fact that it's definition most likely demands that it not be able to operate on itself is not required for the above reasoning.

[CraigD]

Originally Posted by Kriminal99

The proof assumes that the halting machine can operate on itself, by operating the machine on itself during the course of the proof and assuming it behaves as it normally would.

The halting problem explicitly asks if there exists a program H that can accept as input two data: the enumerated description a program, and that program’s data. The problem places no restriction on the size of value of these data, (other than that they are finite, since obviously we can show that H can’t output its required value of “halts” or “doesn’t halt” if it can never stop reading its input) so both inputs being the description of H is a direct consequence of the lack of a restriction prohibiting it.

Turing’s 1936 proof of the undecidability of the halting problem does not have the input to H be exactly H, but be H with a specific change to the so that H does not always halt (the following link’s illustration labels this program K). Since H by definition must halt with an output of “halts” or “doesn’t halt”, this change is essential to his proof. this textbook excerpt has a terse, illustrated summary of Turing’s proof.

If we change the question to explicitly prohibit inputs to H of description of modified versions of itself, we would have a new problem, as there are an arbitrarily large number of possible K’s. K’s need not be constructed as suggested by the illustrations – they could be entirely different programs, so long as they produced the same output. The problem would now require the answer of another problem, “is it possible for a program R to always halt with the output “like me” when inputted the description of a program that always halts with the same output it would halt with given the same data, and “not like me” when it does not.

If we change the question to explicitly program description and data inputs from being the same, we would again be faced with the “like me” problem, as for this to be effective, not only data inputs identical to program inputs would need to be prohibited, but “like” ones as well.

Originally Posted by Kriminal99

In a proof by contradiction, you don't have to explicitly state that you are making an assumption. Any logical assumption you make, whether you recognize it or not, can be the cause of the contradiction.

Turing’s halting problem proof is not, upon careful inspection, a proof by contradiction. It does not start with the assumption that a successful H exists, and show that this contradicts some proven or a-priori theorem. Rather, it is a disproof by counterexample. It shows that for any possible candidate H, a K can be built for which it fails. It provides a specific approach for generating K for any H.

Also, I’m unsure that Krim is using the term “proof by contradiction” in a conventional sense. Such a proof must state its assumed-true assertion, or it simply isn’t a this type of proof.

Originally Posted by Kriminal99

The proof assumes that the halting machine can operate on itself, by operating the machine on itself during the course of the proof and assuming it behaves as it normally would.

The halting problem explicitly requires that all programs can be enumerated, and described in the form of input data. Because it explicitly requires that the programs described in it are Turing-complete, it requires only one actual machine, which is either a universal Turing machine running the program of H, a special purpose Turing machine H, or any machine proven equivalent to one of these Turing machines. No machine actually works on another machine: it works on data describing other machines.

[Buffy]

Originally Posted by Kriminal99

The fact that my philosophical knowledge alerts me to the fact that it's definition most likely demands that it not be able to operate on itself is not required for the above reasoning.

I would hope that your "philosophical knowledge" would alert you to the fact that the phrase "most likely" has no truth-value, and that even if you dropped that qualifier to more explicitly state that "[a halting program's] definition demands that it not be able to operate on itself" requires at least some sort of outline of a proof to show the validity of the statement.

Craig's clarification that "operating on itself" refers to the program as a representation of an algorithm rather than the machine, is a different distinction which I had not considered might be tripping you up, but if this is what you mean by that inability to work on itself--something that's not clear because you still haven't gotten around to telling us anything about why you think this is problematic--then it's important to recognize that as Craig points out, the machine itself is not the subject of the Halting Problem, only the
algorithm is.

You cannot depend on your eyes when your imagination is out of focus,
Buffy

[Kriminal99]

Originally Posted by CraigD

The halting problem explicitly asks if there exists a program H that can accept as input two data: the enumerated description a program, and that program’s data. The problem places no restriction on the size of value of these data, (other than that they are finite, since obviously we can show that H can’t output its required value of “halts” or “doesn’t halt” if it can never stop reading its input) so both inputs being the description of H is a direct consequence of the lack of a restriction prohibiting it.

Turing’s 1936 proof of the undecidability of the halting problem does not have the input to H be exactly H, but be H with a specific change to the so that H does not always halt (the following link’s illustration labels this program K). Since H by definition must halt with an output of “halts” or “doesn’t halt”, this change is essential to his proof. this textbook excerpt has a terse, illustrated summary of Turing’s proof.

If we change the question to explicitly prohibit inputs to H of description of modified versions of itself, we would have a new problem, as there are an arbitrarily large number of possible K’s. K’s need not be constructed as suggested by the illustrations – they could be entirely different programs, so long as they produced the same output. The problem would now require the answer of another problem, “is it possible for a program R to always halt with the output “like me” when inputted the description of a program that always halts with the same output it would halt with given the same data, and “not like me” when it does not.

If we change the question to explicitly program description and data inputs from being the same, we would again be faced with the “like me” problem, as for this to be effective, not only data inputs identical to program inputs would need to be prohibited, but “like” ones as well. Turing’s halting problem proof is not, upon careful inspection, a proof by contradiction. It does not start with the assumption that a successful H exists, and show that this contradicts some proven or a-priori theorem. Rather, it is a disproof by counterexample. It shows that for any possible candidate H, a K can be built for which it fails. It provides a specific approach for generating K for any H.

Also, I’m unsure that Krim is using the term “proof by contradiction” in a conventional sense. Such a proof must state its assumed-true assertion, or it simply isn’t a this type of proof. The halting problem explicitly requires that all programs can be enumerated, and described in the form of input data. Because it explicitly requires that the programs described in it are Turing-complete, it requires only one actual machine, which is either a universal Turing machine running the program of H, a special purpose Turing machine H, or any machine proven equivalent to one of these Turing machines. No machine actually works on another machine: it works on data describing other machines.

The fact that the H in the proof is "Touring Complete" means the result is extremely weak. There could still be a halting machine that is "Touring - {H} Complete" where H is the halting machine itself.

Encompassing any Universal machine in a larger machine that also contains a machine capable of copying input causes an infinite regress if that Universal machine attempts to trace the computations of the machine encoding it recieves as input. Why? When it traced the computations it would just start the whole process over again, and make a new copy of the input for the next level of recursion. This is done in the proof. It doesn't matter how many K's there are, since it's the entire class that causes the problem.

I don't need to assume that H traces the computations of it's input, because I am not the one proposing a proof. Rather Touring's proof assumes that H can function on itself and still do what it is supposed to, when it is very likely that an H by it's very definition could not operate on itself. You can trivially dodge this by simply defining H to be able to operate on itself, but then you cannot sell the result as a proof that the Halting Problem cannot be decided. The removal of H from the set for which the problem is decidable is not very signifigant, much can still be accomplished by solving the problem for everything else.

The proofs absolutely are done by contradiction and not counterexample. You cannot counter example the possibility of existance of any halting machine. That doesn't make any sense. A counter example is just the opposite - when someone says "This always is the case" or "This cannnot be ever" (ie uses a universal quantifier) you only need one counter example to disprove their claim.

Touring starts by assuming there is a Halting decider H, assumes some other things, and then derives contradictions from the set of assumptions. When you say "possible candidate H", it means assume there is such an H. This is called a proof by contradiction.

And it only proves that a certain assumption is false if you are certain that all other assumptions, both recognized and unrecognized are not false. In this case there is no reason to trust the assumption that a Halting machine is in it's own domain.