Awakenings & The Halting Problem Take II
Sunday, 9. December 2007, 14:06:52
The most dangerous man to any government is the man who is able to think things out for himself, without regard to the prevailing superstitions and taboos. - H. L. Mencken
I'd replace government with any governing body in whatever field. And by freedom, I'm not talking about being able to do what you want or any of that. I'm talking about the illusion that is being presented to you. The framework of what is accepted and what is the norm. This is the shield that grounds everyone and what keeps people from looking too hard.
I had written about one such problem where there was an illusion. It's only a single drop in the vast ocean as far as illusions go, but it's a good one as far as computing is concerned. It goes to the very root and core of computing. I removed that post because I was working out my ideas. And this is what happens when you look beyond what is being presented. You start to question things and start seeing things for what it is until the illusion is completely gone.
As the title says, the halting problem is one such illusion. It is presented in such a fashion where it doesn't actually mean anything. Yet we are led to believe that this is a profound conclusion as it relates to computing.
The halting problem asks if there is any program (H) that can determine if all programs (P) halt or not. The illusion here is that the halting oracle (H) must return true or false. Before going into that, let's just go through the proof that says no such oracle can exist.
There are two ways to show that something doesn't exist. Both use proof by contradiction.
1. State the properties of H and show a contradiction that makes the existence of H impossible.
2. Show a contradiction on ALL programs so that none of them could be the oracle.
The proof of the halting problem uses option number 2. That none of the possible programs in existence could be the halting oracle.
What the proof does is create a program Q that invokes the halting oracle, with the source (or binary) of Q as input, and does the opposite of what it says. Since H says one thing and Q does the opposite, then H could not have been the oracle. The proof says that you can write such a Q for any program in P that claims to be the oracle. So this means that there cannot be an oracle. I had a hard time typing this out because there are so many things wrong with this. But there you have it. We could go on with ignorant bliss and be on our merry way.
I'd like to look a little further. Why must the oracle return true or false? It sounds logical on the surface, but is it really a valid framing of the question? Before we get into that, there's another more important question that simply makes the halting problem proof look foolish.
If the halting oracle (H) can be invoked, then because it must be able to return to the invoker, it must have access to this information. If it has this information, then the proof falls apart. It can see how many levels from the root invoker it is. So it could return true if invoked by Q and return false if it was the main program. There is no contradiction since the invoker's information constitutes extra input information. Every time it's the main program, it returns the same answer. And every time Q invokes it, it returns the same answer. And it'd be correct every time.
This poses a second problem. It would mean that there is not ONE oracle, but TWO. The other oracle could return the exact opposite values. Regardless of all this, what does the framing of the halting problem do? Well, we must HIDE the invoker's information. To hide this information, it's a human decision to do so. It doesn't say anything about computing. It says that we're rejecting an answer "just because". More than that, recursive definitions are by default relations. If Q does the opposite, then main H will be the opposite of internal H called by Q. That's a relation. Heck, you don't even need the opposite for a relation. Q could do EXACTLY what H says and you'd still have a relation because both true and false are valid. When you can enter all values and these end up giving some kind of valid output, then it's a relation.
We'll call outside H as H1 and internal H (called by Q) as H0. In the proof, we had the following relation causing the contradiction.
H1 = !H0
For Q that does the exact same thing as H, you have this relation.
H1 = H0
In this last relation, we can come up with two valid programs for H that satisfy the halting problem (for this Q only!). So we are to assume that just because we flip the relation around, something profound has happened? This should be a warning. When you see this kind of thing happening, alarm bells should be ringing. In both relations above, we can enter either true or false and the results would be valid.
So we hide information. We say that the oracle (which is supposed to be all knowing) cannot know everything. Once we realise this, we see that things were framed exactly one specific way in order to produce the result wanted.
Now that we know the framing of the problem and of the proof is created by humans, then we are free to ask better questions. What if we don't consider programs that call H? These are the programs that are important in the real world anyways. And if programs do call H, let's give it access to information about the invoker. What then? It turns out these questions have much more value.
Let's ask a better question. Let's keep the initial wording of the halting problem with one exception. Let's let the halting oracle return anything it wishes. But we now ask if the halting oracle will only return true or false for all programs. If the halting oracle H only returns true or false for all programs P, then we should obtain the same result as before, right? There's no difference.
If we apply the halting problem proof to this scenario, it falls apart. This is because the halting oracle would need to return a relation (the only correct answer for recursive definitions) and Q doesn't know how to handle relations. This applies even if Q does EXACTLY what H says if it were to return true or false. Notice the consistency! We don't know what will happen to Q when it tries to process the results (relation) from H. They are incompatible parts. So we can say it's undecidable. And this is actually where the result of undecidability comes from. It comes from allowing invalid programs into the fray which is a rather insignificant conclusion. Again, note that we get the same conclusion for all relations. Not just for an inverse relation. What's more is that if you don't allow invalid programs, the proof falls apart because Q cannot be constructed in the first place. H will always return true or false for valid programs. No Q, no contradiction.
The more we look into it, the more we see REAL meaning. And the less we see value in the halting problem proof. Note that I'm not saying I believe it's possible to create a halting oracle. I'm saying that the halting problem proof leaves a lot to be desired when it comes to telling us something about computing. I'll also confess that I have no idea if a halting oracle is possible if we refrain from rejecting specific answers. What I do know is that the halting problem proof is very much lacking in substance.
When I read papers of any kind, I see this kind of thing all the time. It's usually the framework that is flawed. Proofs on flawed frameworks don't affect any of us. You could prove a million and one things and I still wouldn't care. I don't need to trust them because they simply do not apply to real life scenarios. So I hope this explains in more detail why I think much of what is written is incorrect. It's not necessarily on the basis of the question posed and the conclusions that stem from those questions, but that we often ask the wrong questions to begin with. I've often said that if a question is difficult to answer, it's usually because you're asking the wrong one. And that if you ask the right question, the answer comes with it. This is a double edged sword. Asking a wrong question will often come with its own answer too. We get led down the wrong path. This is another of my sayings. That knowing the right question to ask is often the hardest part.
This is an easy tactic to use and I see it all the time. Someone makes an argument with a certain premise and then goes on to apply this conclusion to another scenario where he or she has no right to do so. Superficially, it seems to make sense. This is why it's critically important to look a little beyond what is presented to us. What other details are hidden under the surface? And if you're still asking if I've shown the halting problem proof to be wrong, you've missed the point entirely. It's about knowledge that applies to YOU. That's why it's dangerous to simply take the word of "giants" at face value. Your application of certain concepts may not be the same and thus will not abide by the same rules and conclusions.
I hope the reader will understand that this is a difficult topic. Probably the most difficult one I've tackled on this blog so far. Freedom is about the ability to wield knowledge in a way that is beneficial to you and those around you. When people work together, it then becomes even more difficult to put up with an illusion. They naturally float to the surface. This is a very dangerous idea. If you do decide to look at what is put out there as news or whenever you read something that deals with public opinion (this applies to computing too), keep an eye out for what is being demonized. I can almost guarantee that it'll be public organised groups and those that don't follow accepted conventions. And for good reason.
The downside to all this is that once you see the illusion for what it is, the world becomes quite different. It's one that you would often like to never have seen in the first place. What I find most frightening is that once you take a breath of freedom, there's simply no other kind of air you want to breathe. The illusion of safety is gone. There's no going back. As I write this, I'm even more convinced that I'll get rather strange reactions. I'll end with this quote I found after having written this entire entry.
The fact is that the average man's love of liberty is nine-tenths imaginary, exactly like his love of sense, justice and truth. He is not actually happy when free; he is uncomfortable, a bit alarmed, and intolerably lonely. Liberty is not a thing for the great masses of men. It is the exclusive possession of a small and disreputable minority, like knowledge, courage and honor. It takes a special sort of man to understand and enjoy liberty — and he is usually an outlaw in democratic societies. - H. L. Mencken
I agree with your conclusion on the halting problem.
Now ... Hasn't anybody asked this before ?. Isn't THAT frightening ?
cheers
By anonymous user, # 9. December 2007, 15:06:08
I tried to show one example in this blog entry of how people don't look any further. The concurrency problem is another such example. So what I can say is that it's not an isolated incident. It's the norm rather than the exception. Individually, each example is not that worrisome. What gets scary is when you notice that this is going on all over the place. You start to lose your footing. There's nothing to ground you or to reassure you anymore. Think of vertigo. That's what freedom feels like. But unlocking yourself from predetermined conclusions opens up new possibilities. This means there are benefits. It's then up to you to define your own footings. I had a blog entry in the past (with a real life example) where I said most people aren't very good at defining their own needs and requirements. It still baffles me to this day. But I'm forced to very much agree with the quote that this kind of freedom isn't for everyone.
By Vorlath, # 9. December 2007, 21:00:14
"Big deal," you might say (and I think you've said it). The meaning of the Halting Problem is that in general, you can't have a computer reason about code. In specific cases, yes. But not in general, and this has implications in automatically proving program correctness (The Halting Problem does for computers what Gödel's Incompleteness Theorem does for Math) for more than just determining if a program will ever halt.
By spc476, # 10. December 2007, 08:51:04
(in this program, "number" represents a number of unspecified size; it could be 32 bits, it could be 4096 bits, it could be larger---the point is, not to get hung up on a restriction on the size of the number)
number A(number x,number y)
{
if (x == 0) return y + 1;
if (y == 0) return A(x - 1,y);
return A(x-1,A(x,y-1));
}
By spc476, # 10. December 2007, 09:24:18
About the contradiction, there is only one if you allow invalid programs. Why must the oracle return true or false? Why not allow it to return any answer that makes sense. It's like asking a function that normally returns A,B or C to only return B or C. If A is the correct answer yet you don't allow it, then of course it's undecidable. This is what's going on with the halting problem proof by not allowing A (or relations). This is why I say "big deal". I did not say "big deal" for the reasons you originally thought.
You can't say this with the current halting problem proof though. All it says is that you can't reason about invalid code. I'm not saying that it IS possible to reason about all code. I'm saying you can't show that you can't with the current proof.
About your program, it is indeed possible to write a program that can prove if it halts or not.
A is only called with decreasing values. And you have sentinel values on both x and y for zero. So right there, it's obvious it terminates for all inputs. I don't have time to write it, but it wouldn't be too difficult to analyse these kinds of programs.
Personally, by looking at it, I can tell you that x is irrelevant and that your function is the same as y+1 since it's the only exit value that doesn't call A() meaning it's the only way to go back up the call chain. The second line does not change y, so no need to look there. The last line possibly alters y. However, at each level back up, it would re-increment y (because this is the only way back up) cancelling out any change. That means A really is just y+1.
What does all this have to do with anything? Nothing so far changes anything about what I've said. And I assure you that I understand the halting problem perfectly.
By Vorlath, # 11. December 2007, 23:10:46
number A(number x,number y)
{
if (x == 0) return y + 1;
if (y == 0) return A(x - 1,1);
return A(x-1,A(x,y-1));
}
And yes, it may halt, it may not. I know that for A(5,5) it takes a really long time before it crashes. Go figure.
But I have a hard time understanding your argument against the Halting Problem. I don't follow your logic at all.
By spc476, # 12. December 2007, 22:47:30
My argument against the Halting Problem is simply that the definition of the halting oracle is incompatible with the specifications of a computing system. You end up contradicting the computing system in order to say that it's undecidable to know if all programs halt or not.
First assumption is that H (the oracle exists).
H
H must operate on all program P. This is essentially our computing system since it contains every possible program. We'll state this dependency for H as far as the definition is concerned.
H -> P
Q (the deceiver) is one of the programs P. So P's definition is dependant on the existance of Q.
H -> P -> Q
Q calls H. So Q's definition is dependent on H.
H -> P -> Q -> H
Note the circular dependency.
If any of these definitions fail to hold, they all fail. By showing a contradiction (meaning that Q does not exist), this means that H cannot exist for a P that was NOT all programs. The definition no longer holds and so H could never have been the oracle anyways. What you end up disproving is the set of all programs. NOT that an oracle cannot exist.
In any proof by contradiction, something must hold up. You can't disprove everything. For example, in the infinite prime proof, the numbers are prime all the way through. If the numbers ended up not being prime, then the proof falls apart. Same thing here. If P ends up NOT being the full set of possible programs, then you're dealing with a wrong definition of your computing system. Of course there's no oracle for an improperly defined computing system.
You want to prove that for ALL programs in P, that none of them could be H. So you only want to show a contradiction on that first H in the dependency chain above. P must still be the set of all programs (other than H). It must still have Q within that set. And Q must still call H. Of course, this is a circular argument (by making Q dependent on H) and can never succeed.
In this blog entry, I cut to the chase and say point blank that the only correct answer for an oracle to give upon a recursive definition (one that depends on the results of the oracle itself) must be a relation. That's the ONLY possible answer. But the wording of the halting problem rejects this. So the definition of the oracle is incompatible with any real computing system. You're basically saying that you can call it, but define the oracle in a way that makes it impossible to do so (by forcing the oracle to return an incorrect answer). Hence the contradiction. It's a contradiction on ALL definitions, not on anything about the fundamental nature of computing. You only want to contradict the EXISTENCE of the oracle, not the DEFINITION of everything (specifically the definition of a properly working oracle).
By Vorlath, # 14. December 2007, 02:41:39
Circular dependencies do not matter. What matters is that each step follows logically from the next, according to a fixed set of rules.
The boundaries the Halting Proof provides are largely theoretical, as one can do a lot even without being Turing complete. I read a paper some time ago about a language designed such that every program written in it always halts, and the paper demonstrated a number of problems that could be solved under such a system.
Nevertheless, Turing completeness is a valuable quality, though the problems involved in assuring whether something halts are more practical than theoretical. We know that it's impossible to determine whether every program can halt, but where the exact limit lies is unknown. It may be that a majority of Turing complete programs can be tested for infinite loops, but it's clear that this is a very difficult problem, even without the Halting Proof hanging over our heads.
In other words, we're thwarted by practical difficulties long before the particulars of the Halting Proof comes into play.
That all said, the Halting Proof is a pretty important piece of work, and places an upper limit on what we can achieve. But people do place too much emphasis upon it. Just because it's impossible to build a compiler that can detect every error, doesn't mean you shouldn't try to build a compiler that detects _almost_ every error
By anonymous user, # 17. December 2007, 23:23:15
See, it's easy to show there is no oracle if you include a program that cannot exist. Unfortunately, most people assume the contradiction is based on the oracle only. Not true. Since it's a circular dependency, everything fails at once. So you can't come to any conclusion about what failed first, the oracle or the set of all programs.
All this means that the current proof does not say that it's impossible to write an oracle. The Halting proof is irrelevant because it says absolutely nothing about real computing systems. The only way that the Halting Proof can hold is if you have a set of all programs that includes programs that cannot exist.
By Vorlath, # 18. December 2007, 00:24:23
It's not a circular argument. Consider the following javascript function:
var f = function(g) {
return function(x) {
var b = g(x, x);
while (b);
};
};
It's a syntactically valid function that will compile and run just fine in a javascript interpreter. For instance, f(function(a, b) { return a != b }) will execute without error.
So we know that f is a valid javascript function. But if h is a our halting oracle, then h(f(h), f(h)) is contradictory. Since we've already shown that f is a valid function (and our javascript interpreter agrees!), the only way this contradiction can be resolved is if h is not valid.
By anonymous user, # 20. December 2007, 18:33:09
By Vorlath, # 21. December 2007, 05:51:38
By Vorlath, # 21. December 2007, 06:33:37
Take a closer look at the function.
f = function(g) { return function(x) { var b = g(x, x); while (b); }; }
f(h) = function(x) { var b = h(x, x); while (b); }
f(h)(f(h)) = function() { var b = h(f(h), f(h)); while (b); }
So if h(f(h), f(h)) is true, then f(h)(f(h)) spins into an infinite loop. If h(f(h), f(h)) is false, then f(h)(f(h)) exits in finite time.
If I plug f into a javascript interpreter, it says that it's a perfectly valid function. So the existence of h is disproved using a function that both exists, compiles, and executes.
By anonymous user, # 21. December 2007, 17:38:41
By Vorlath, # 22. December 2007, 00:03:46
You don't seem to understand the code. I know nested functions are complex, but the local variable "b" will be a boolean for f(h)(f(h)), not an object or a function.
Like I say. Look over the function again a little more closely.
By anonymous user, # 22. December 2007, 00:36:13
Variable "b" won't be boolean if you expect a correct answer from the oracle. It'll be a relation as it must be for recursive definitions. But if you wish to reject correct answers, then you'd be right. But then you just admitted that the contradiction is caused by humans and this means you start off with the premise of undecidability, not a conclusion. You're knowingly setting things up to fail from the start. It's like saying I want a function that returns the answer to 2+2, but I don't accept 4 as an answer. Big deal. Of course it's undecidable. I'm not impressed by these kinds of arguments and this is all the Halting proof is.
edit: Note that these kinds of conclusions say nothing about the actual system. For example, writing a function that returns 2+2 is actually possible.
edit2: I have to mention that you're confused about a definition of a program and the existence of a program. Just because your program exists does not mean it does what you claim. I'm saying it does not do what you claim because it cannot handle correct answers (and hence cannot call the oracle in the first place). So the existence of a program that is not the deceiver isn't very noteworthy. Your program can exist all it wants and it won't change a thing. To convince me, your program must be the deceiver and work according to its definition. Both these things must happen at the same time and right now they don't.
By Vorlath, # 22. December 2007, 02:28:23
I'm pretty familiar with nested functions. Now if you were talking about dual Kleisli arrows or arboreal isomorphisms, I might get a little lost, but first class functions are pretty commonplace
And sure, the Halting Problem proof isn't that practical. But it does show that an oracle that is also a turing machine cannot accurately tell you, in a finite timespan, whether an arbitrary turing machine will halt or not. This is one of those things theoreticians like, but isn't really of practical use elsewhere, other than to suggest that telling whether or not a program will halt is generally not very easy, even when it is possible.
I'd guess you're more a practical kinda guy, but some people really like probing the theoretical limits, even if they'll never actually mean anything in the real world. It's all about discovery for discovery's sake, I guess.
By anonymous user, # 22. December 2007, 02:57:26
Unfortunately, it does no such thing. The proof fails miserably.
I don't think you understand. The setup in the Halting proof can never exist either in reality or in theoretical terms. It's a logical impossibility set up from the premise in exactly the same manner as when I ask you to define a function that returns the result of 2+2 just as long as you don't return 4. That is EXACTLY the Halting proof. Sorry, but that's an insult to my intelligence. I can write a function that returns the result of 2+2 and in the same way, maybe we can indeed write an oracle. Rejection of valid answers can NEVER get you proper conclusions no matter if the model is physical or theoretical.
By Vorlath, # 22. December 2007, 03:12:07
Uh, dude, this is a pretty well established proof. If there was anything wrong with it, someone would have probably pointed it out by now. Either you're the smartest guy in history, or you've misunderstood a pretty elementary proof.
I don't get what's you find so problematic about it. You're arguing that there's more than two correct answers for the oracle, right? But that just seems like you're redefining the problem.
I mean, if I asked the question "Given this input, will this turing machine halt in finite time", then I'd expect an answer of "Yes" or "No". If the oracle answered "Maybe", "Undefined", or "Yes, no, yes, no...", it wouldn't be a perfect oracle.
By anonymous user, # 22. December 2007, 13:03:37
Ah, this argument again. Thanks, I should just give up on Project V too. People told me it was impossible. BTW, in almost everything I do, I see this come up. If I listened to those people you speak of that came before me, I'd never get anything done. Those proofs are only valid as long as the basis of the argument holds up. I don't use the same basis, so the rules of computing that most people think are an absolute actually aren't.
I'm not arguing that there's more than two correct answers for the oracle. I'm saying if you want an oracle, then let it answer the CORRECT answer. If you do this, then you see that the Halting proof doens't work because you end up with an oracle that could possibly return true or false on ALL programs exactly as the Halting problem wants it.
This is what you don't get. If a program calls the oracle and acts on the result, then it's a relation. Anyone can tell you that just by looking at it. Forcing a "Yes or no" answer is a human decision because it's NOT the correct answer. It's the same as asking someone to write a function that returns the answer to 2+2 and not accepting 4. So yes, I'm saying the definition in the halting problem is ridiculous. But I'm also saying that the halting proof fails of its own accord (using the original definition of the oracle in the Halting problem)
So if the CORRECT answer from the oracle is a relation, this means the deceiver cannot exist because it cannot be composed with the oracle. The deceiver is only built to accept true or false answers and thus cannot call the oracle (even though it may exist). And since the deceiver cannot exist anyways, then the oracle never needed to give an answer to a program that is unable to call it. Programs like the deceiver, I call these invalid programs. Only if you allow invalid programs that do not act according to their specification (including the specification of the laws of computing), then sure, your proof can hold up. But I do not care about such trite arguments because the very definition of invalid programs is that they are undecidable.
So the proof says nothing about any computing system in existence theoretical or physical. In fact, I've shown how the proof contradicts its own definition of a computing system. No oracle needs to exist for an improperly defined computing system. So you end up with an oracle that cannot work with an improperly defined computing system. Big deal. Of course it doesn't exist. But it says nothing about a properly defined computing system.
There's a logical flaw in the proof itself. It's not just about changing the definition of the problem. I argue that if it were not for this error in definition, it'd be easier to see. But the flaw in the proof is there regardless.
And about your first argument, I haven't seen anything that contradicts what I've said. So far, the only argument I've seen are ones where they assume I don't understand the problem. I throw toss those aside right away. Or arguments that try and show how it's possible to compose a program out of something they end up saying doesn't exist. It's really a leap of faith how the set of all programs can contain something (the deceiver) that ends up not existing. Circular arguments simply do not work.
By Vorlath, # 23. December 2007, 22:39:57
The oracle is defined as a program that returns true or false in a finite length of time. Saying it should return "a relation", or anything other than a boolean value, is redefining the problem.
Also, this:
"Or arguments that try and show how it's possible to compose a program out of something they end up saying doesn't exist."
Is pretty much an exact description of proof by contradiction. That's how it works. If you can't see that, then either you've figured out something that no-one else has, which puts you ahead of pretty much every mathematician in history... or you simply don't understand logical proofs.
Good luck with your Project V, anyway.
By anonymous user, # 23. December 2007, 23:43:09
No, the problem is if there is an oracle that returns true or false for ALL programs. If your assumed deceiver program ends up not existing, there was no need for the oracle to return a "yes or no" answer in the first place.
But you don't understand. It's the definition of the oracle that is being contradicted, not its existence. Not only that, but the definition of the contradiction itself is being contradicted. This cannot happen in a proof by contradiction. If you contradict the contradiction, then there cannot be a contradiction. That's why the Halting Proof is using circular logic. Either everything is valid, or everything is contradicted (including the contradiction). Either way, the proof cannot succeed.
If the set of all programs ends up being contradicted, then the proof fails and I've shown that quite easily. An oracle needs not work on a set of all programs that ends up being contradicted (IOW, not properly defined).
Let me say again, in a proof by contradiction, you cannot contradict the contradiction. If you do so, then it fails. I don't know why this isn't mentioned anywhere that I could find. I also don't know what's so complicated about this.
edit: I should also point out that what you say I've described as being contradicted is the contradiction itself, not the assumption. So you can't just say there's a contradiction and end the discussion. You have to look at WHAT is being contradicted.
By Vorlath, # 24. December 2007, 00:01:48
I don't think I've seen a better description of the Halting Problem.
By Vorlath, # 24. December 2007, 00:37:49
Show how the oracle cannot work on programs that do not exist.
This means there is a contradiction and that the oracle cannot exist.
That's the Halting Problem PROOF!
By Vorlath, # 24. December 2007, 00:40:46
Fallacy of many questions
Absolutely brilliant!
In the Halting proof, it asks whether the oracle can exist. This is what you want to contradict. But the setup has a fallacy of many questions in it. It PRESUPPOSES that the set of all programs exists with the deceiver program as part of that set without convincing us that it does. Q alone is NOT the deceiver. The deceiver is the combination of Q and H. The only way to show that this combination exists would be to show a real, working oracle that works on this program as well as all others. If you can't show that both exists, then there cannot be a contradiction. In fact, in the end, it ends up telling us that the deceiver doesn't exist. They're setting up the contradiction within the premise!
By Vorlath, # 24. December 2007, 00:58:51
Aristotle could have shown the Halting problem to be false in 350BC! Where's Aristotle when you need him?
Look at that last sentence. "If, however, the relation of B to C is such that they are identical, or that they are clearly convertible, or that one applies to the other, then he is begging the point at issue."
There is a clear application of one to the other. H depends on the set of all programs P that depends on the inclusion of Q that depends on H. None of them can exist without the other. This means that if you use any of the dependencies to show a contradiction, then you are begging the point at issue and is a known fallacy.
Aristotle seemed to know his shit.
By Vorlath, # 24. December 2007, 02:06:23
You're still not understanding the problem. The existance of the deceiver program P is implied by the existence of H. That is, the argument is constructed such that if H exists, then P exists. To put it more precisely:
Assume H is a well formed turing machine.
Let P be defined:
P(I) = { b = H(I, I); while (b) }
If H is a well formed turing machine, then P is also a well formed turing machine, according to the rules laid out by Turing that define well formedness.
In other words, H implies P, P implies a contradiction with H, therefore H can't exist.
Or, to put it more simply: if H exists, P must exist.
Or, looking at it upside down: P doesn't exist, *because* H doesn't exist.
This is how proof by contradiction works. Given an assumption A, an intermediate result I, and a contradiction C, then:
A => I => C
In the case of the Halting Proof:
H(A, B) => P(I) = { b = H(I, I); while (b) } => C
But... since it's Christmas and all... What the heck. You're right, and everyone else is wrong
By anonymous user, # 24. December 2007, 17:51:18
Nope. P can only exist if you assume an invalid answer by H.
Well, P doesn't adhere to its definition. So it "well formed" doesn't even enter into the picture.
No. P actually cannot exist as defined. It's definition is incompatible with a correct answer from H.
Have you ever thought that maybe the reason P doesn't exist is because it is not composable with H?
Proof by contradiction must not contradict the contradiction. Sorry, but if you avoid that point, there is no further discussion. This is exactly what Aristotle meant if you have A and B that apply to each other.
Fight with Aristotle all you want. I think he was right on this one. So no, not everyone else is wrong. Aristotle was right.
By Vorlath, # 26. December 2007, 16:52:40
I just wanted to clarify this fallacy in a manner that only requires simple logic to show how this argument fails. Oh, and I understand the problem perfectly.
BTW, I'm gonna rename the deceiver to Q. The set of all programs is P.
Your words. So tell me, if H doesn't exist, and Q doesn't exist, then where's the contradiction? Without both Q and H, there cannot be a contradiction. Do you understand that? If you end up saying they do not exist, then you defeat your own argument.
Here's why.
H requires P.
P requires Q.
Q requires H.
Circular argument! Just as Aristotle said:
Clearly, each statement above applies to the other.
In syllogistic form, we'd like to state that:
Show how H implies Q (which contradicts H by definition).
Show how Q contradicts H.
Conclusion: H cannot exist.
These kinds of arguments are called circular logic and can never succeed.
Now, let's compare this to the official definition of "begging the question":
IOW, it's exactly what the halting proof does. Begging the question is identical to the halting proof.
Q implies contradiction. (p implies p)
Suppose Q. (suppose p)
therefore, contradiction. (therefore, p)
You don't even need a computing system or any of that to state the so-called "proof".
You could say this instead.
Proposition: (A,B) cannot exist in the same set as B
Suppose A,B.
Therefore B cannot exist.
It's beyond childish as an argument, much less a "proof".
With the Halting Proof, it gets worse. B implies A. So we could restate it as:
Proposition: A cannot exist in the same set as A
Suppose A
Therefore A cannot exist.
Aristotle was right. Alan Turing was wrong.
There has not been ONE valid argument as to why the Halting Proof should hold up. And if people want to side with "giants", then I side with Aristotle over Turing.
By Vorlath, # 29. December 2007, 01:06:27
It's not begging the question, because you're missing out a variable: the set of all well formed turing machines, W.
Assume H ∈ W.
H ∈ W logically implies Q ∈ W.
However, we can show that Q ∉ W.
Therefore, H ∉ W.
Proof by contradiction is the keystone of mathematics. It is the most common form of proof, and anyone using mathematics in any significant fashion, from Newton to Einstein, from Leibniz to Planck, is going to have used this technique.
If Turing is wrong, then so is every other mathematician and scientist of note. And it's rather more likely that you just don't understand formal logic that well.
By anonymous user, # 29. December 2007, 18:16:54
Let me add something to my previous post. You may find H, Q and W easier to reason about if they are assigned more natural values.
Let H be a Hippopotamus.
Let Q be the volume of water displaced by a Hippopotamus.
Let W be the set of objects with volumes less than 1 cubic metre.
Assume that a hippopotamus has a volume of less than 1 cubic metre. (Assume H ∈ W).
If a hippo has a volume of less than 1 cubic metre, then the water displaced by a hippo will also be less than 1 cubic metre. (H ∈ W => Q ∈ W)
However, we can put a hippo in a tank of water, measure the displacement, and discover it comes to a lot more than 1 cubic metre. (Q ∉ W)
Therefore, if the water displaced by a hippo is greater than 1 cubic metre, the hippo must have a volume of greater than 1 cubic metre. (Therefore H ∉ W).
By anonymous user, # 29. December 2007, 19:00:27
Just in case the "member of" and "not member of" symbols don't render for you, here's it using words:
Assume H member of W.
H member of W implies Q member of W.
But we can show Q not member of W.
Therefore H not member of W.
By anonymous user, # 30. December 2007, 01:58:55
This is false. In fact, it's easy to show that this is NOT the case.
If you want an oracle, then we know that passing it anything that is dependent on itself is a relation. So we know with 100% certainty that in these cases, true or false is an incorrect answer. It doesn't mean these cases exist. It means that if they do, then this is what you'd need as a valid answer. This is regardless of the definition of the oracle as specified in the question. This is because if the oracle only ends up giving a true or false answer for all programs that exist, then there is no difference.
So when you form your Q, something that we have not confirmed exists mind you, then Q must handle an answer that is neither true nor false in order for it to be a program. Otherwise, it's simply an invalid definition of one. And the definition says that it does not handle answers other than true or false. So H does NOT imply Q. And if Q cannot be defined correctly, then H does not need to give an answer to something that does not exist. Hence, no contradiction.
Again, this is a proof that begs the question just as you did with the quote above. Remember, just because you want an oracle to return true or false, you cannot assume it will return this if that would be an incorrect answer. This would only mean that Q is not composable. Not that H doesn't exist.
By Vorlath, # 31. December 2007, 00:35:40
You're redefining H. H returns either true or false. Any other definition of H is plainly a straw man argument and has no bearing on this discussion.
Yes, this results in an "incorrect" answer under certain conditions, but that's the *whole point* of the proof. The proof isn't trying to prove whether *your* particular definition of H exists or not. It's proving that H, as defined by Turing, does not exist.
Let me make it perfectly clear. H is:
1. A well formed turing machine.
2. Returns a value in finite time.
3. The return value is only ever true or false.
If your H differs from *any* of these rules, then you're talking about something entirely different.
So, the question is: does your idea of an oracle exactly match the above conditions?
By anonymous user, # 1. January 2008, 00:04:15
For example, if I end up showing that a function returns 5 when I assumed it was 2+2, I would end up contradicting the definition of a program that computes 2+2, not that this function does not exist. What I assumed was 2+2 ends up not being so, exactly like your H. But you don't see that for some reason. I proved that this function does NOT compute 2+2 exactly like the Halting Proof ends up proving that your definition of H is NOT the oracle. If it's not the oracle, then you've said nothing about the real oracle. Existence and definitions are two different things. Your definition must hold up. It's the existence that must fail.
You still didn't respond to Aristotle's argument that you are begging the question. You are assuming in words only that you have a valid computing system and then proceed to define an invalid one (Q) to prove your point. That is begging the question. You are providing the answer within the framework. Providing an invalid program does not mean that the oracle does not exist. It means that Q does not exist. H has no requirement to give answers to incorrectly defined programs that will never exist.
I'm sorry, but there is NO way for the Halting Proof to succeed.
edit: I predict the following argument, so I'll deal with it here. You want to show that no program could be the oracle. So if I show that no program can compute 2+2 (that they all compute 5 or whatever), then it's not only contradicting the definition, but also its existence. This is true if and only if the contradiction holds up and is properly defined. With Q, its definition puts it outside the realm of programs that do exist, therefore it says nothing about nothing.
Take the infinite prime proof for example. If you end up contradicting that the numbers within the list are prime, then your proof would fail. Same thing with Q. If you end up showing that Q is not well defined and cannot exist, then the proof fails. And Q can only be well defined if H exists as assumed. If the assumption fails, the proof fails. Your assumption is directly linked to the success of your proof. If the assumption ends up being true, then there is an oracle. If the assumption is false, then Q cannot exist and there is no contradiction. Either way, the proof fails.
By Vorlath, # 1. January 2008, 01:02:54
This is one point that NO ONE wants to take on directly. I wonder why.
By Vorlath, # 1. January 2008, 01:30:20
THEN I can come and say exactly WHY Q cannot exist (which the proof fails to explain). It's because a proper answer would be a relation and Q cannot handle that. So your proof is trying to tell you that there's something wrong with your definitions. You take the wrong conclusion though.
By Vorlath, # 1. January 2008, 01:42:07
The PROBLEM defines the oracle as a program that can predict the outcome of all programs.
The PROOF defines the oracle as a program that can predict the outcome of all progams, of which Q is included.
This is a critical difference. The proof defined H as working on Q. If it is shown that the pair (Q,H) doesn't exist, then it means that H was incorrectly defined because it was defined to work on programs (or pairs) that do not exist. You end up taking conclusions based on an incorrectly defined H (the one in the proof) and applying it to the REAL H (the one in the problem). You cannot do this.
If you start out assuming that Q is part of all programs and end up contradicting its existence, then you end up with two different sets of all programs. You've contradicted the ASSUMED set of all programs. This means that the assumed oracle worked on an improperly defined set of all programs. So you cannot use this proof to make any kind of conclusion about anything. FINAL!
By Vorlath, # 1. January 2008, 02:09:16
By Vorlath, # 1. January 2008, 10:34:01
THE INVALIDITY OF DIAGONALIZATION PROOF FOR HALTING PROBLEM
The last section.
The author is Palem GopalaKrishna though it doesn't say directly. The first section is found in another paper by the same author.
This paper says EXACTLY what I've been saying all along. In the paper, it says that g and h cannot co-exist (as I've said). I would have went further and said that since g and h cannot co-exist, then the definition of g is itself a contradiction since it requires h. So we know with 100% certainty that g does not exist as defined. But this says nothing about h.
My favourite part is this.
"Wishful thinking" = Begging the question, no?
By Vorlath, # 1. January 2008, 14:53:08
It doesn't surprise me that there's a paper on it. There's a paper on everything, regardless of its merits, and I can find few merits in the one you reference.
You seem to be hung up on Q being dependent on H. But it's very easy to separate the two. In javascript:
function Q(f) { return function(x) { var b = f(x, x); while(b); }; }
Note the lack of H. Are you going to tell me that the above function doesn't exist, even when I've written it down?
In the above case, the expression H(Q(H), Q(H)) provides the contradiction.
Or what about this:
function Q(f, x) { var b = f(x, [f, x]); while(b); }
With this definition of Q, then expression H(Q, [H, Q]) provides the contradiction.
So Q can be defined independent of H, and these independent definitions clearly exist, and clearly contradict the definition of H.
By anonymous user, # 1. January 2008, 17:54:00
No, of course not.
Are you saying Q doesn't invoke H? This is beyond ridiculously obvious. C'mon! The proof what's hung up on this. Not me. My argument is that if Q wasn't dependent on H, I'd accept the proof.
Yes! It's incomplete. The full definition of the deceiver is not only Q, but also H (either as a subroutine or as an input). But if you can show how to deceive the oracle without invoking it, I'm all ears.
Strange, there's H again being used by Q! How'd that happen?
Funny, I could swear you're using H with Q.
There's nothing in your comment that would indicate this. If you could, I'd accept it instantly. But I still don't see how you can deceive the oracle without invoking it.
Uh, certainly not. You only assumed the existence of H, not proved it. If you proved it, then your argument fails anyhow. But if you don't prove it, then there cannot be a contradiction because the definiton of Q is incomplete. Like I said, this proof cannot succeed and you've shown nothing credible that changes this fact.
No matter what, you're ignoring the above arguments that you cannot contracdict H without also contradicting (H,Q). This means there can NEVER be a contradiction. Answer that. So far, you're just repeating the same thing over and over without considering what I'm telling you. Your direct avoidance of issues I've pointed out with your arguments lead me to suspect that you are not serious.
I'm satisfied 100% that my arguments are valid. Nothing you've shown is of consequence and I've shown them incorrect many times over. So unless you have something new, there's nothing left to discuss. Perhaps you could read up on how proofs by contradiction work and then come back. Right now, you simply lack enough knowledge on the subject. This isn't an insult. It's simply a fact. For example, you believe that using a non-existent contradiction is valid. As another example, you are unable to respond to the numerous holes I've poked in your arguments like the different definitions of H, using multiple assumptions to come to a conclusion as well as not understanding the difference between a definition and existence. So I need to move ahead and have no desire to convince you specifically. I'll continue if you have something new to provide and if you answer the numerous holes in your argument.
I'll leave you with a few rules that go with proofs by contradiction.
1. If you contradict a contradiction, then there cannot be a contradiction. The proof fails!
2. If #1 happens, then you are begging the question.
3. If #1 happens, then an assumed definition was incorrectly defined.
These are all related, but should get you on your way to better understanding proofs by contradiction.
By Vorlath, # 1. January 2008, 18:58:05
You're confusing a falsehood with a contradiction.
But this is getting us nowhere. You have only the vaguest notion of how formal logical systems work, and are trying to fill in the gaps with intuition and guesswork. No matter how I present the proof, you lack the grounding to understand the components that compose it.
You're trying to apply dictionary definitions to words that, in this context, have very precise meanings. You can't contradict a contradiction. Saying that will help me understand proof by contradiction is akin to saying that to understand arithmetic you need to know how to "zer a zero". It's nonsense.
I haven't studied predicate logic or Turing machines as much as some, but I know my way around. You clearly haven't studied it at all.
My advice would be to enroll in a good CompSci course that at least covers predicate and propositional logic, formal automata, and naive set theory. You could also pick up some course books and try to work through the exercises on your own.
However, given that you seem almost proud of your ignorance, I suspect you won't take this advice.
By anonymous user, # 1. January 2008, 20:25:49
I've read and fully understand what the proof is getting at. I was simply pointing out the flaws. But what you did is reprehensible. Your only argument was that I didn't understand the proof. Basically, you have nothing to say at all. You're just repeating what you've seen and have no ability for critical thinking and don't even realise how insulting your attitude is. By doing this, you haven't shown that you possess the ability to tell if what you've read is right or wrong. Everything you've said is based on someone else. Do you have any substance? Everything you've said, I've already considered and have read elsewhere. You think I should learn about some theories? Well, you should take a few courses on being a human being. Man, where do you come off anyways that you'd pull a stunt like that? Do you get a kick wasting people's time like that? WTF?
All this time, I thought you actually had something to say. That maybe I was wrong. But no. You were only repeating what I've already seen. What a waste!
By Vorlath, # 1. January 2008, 23:48:35
If my attitude is insulting, I apologize. However, I don't think you realize that your attitude is equally insulting, and it's hard to maintain civility under such circumstances.
Your argument is that Turing is wrong, and that you are right. But you're arguing propositional logic without knowing the rules. You don't even know the meaning of "contradiction" in this context. (For reference, it's a logical incompatibility between two propositions, and since a logical incompatibility is not itself a proposition, a contradiction cannot be itself contradicted.)
You wrote: "You cannot contracdict H without also contradicting (H,Q)". There are so many things wrong with just that little sentence. Firstly, we're not contradicting H. H is a variable, not a proposition, and cannot be contradicted. (H, Q) is a tuple, and I'm not sure what the hell that's meant to represent, but it's not being contradicted either.
Now, maybe you're getting confused between contradictions and falsehoods. Maybe you're using "H" as a shorthand for "H ∈ W". Maybe you're using a tuple to represent an implication. Maybe you *meant* to say: "H ∈ W cannot be false without H ∈ W → Q ∈ W being false". But even this is wrong, since: F → x = T.
And this is just *one* sentence. Imagine when you start to pile on the paragraphs. Your reasoning has so many errors in it, it's really hard to pick out anything that makes even the slightest bit of sense. Are you starting to see why I've been a little short tempered? Because hardly anything you're writing makes the slightest bit of sense. You may as well have argued that "1 + 1 = 3 because banana". After the tenth time of you saying "because *banana*", it begins to become a bit wearing.
What makes matters worse, is that after you've written several nonsensical paragraphs, you then bring out patronizing comments like "If this is the level you're at, then there's a high risk we're gonna lose something in the translation." That's *really* annoying, and I'm ashamed to admit that after bearing this for a dozen posts or so, I've begun to sink to your level.
So this is why I'm a little irritated. If you want to argue formal logic, fine. But if you don't know how to do it, don't try and blag your way through. Instead, pick up a book, and learn about it.
By anonymous user, # 2. January 2008, 01:42:29
And again, you assume I don't understand basic things like contradiction. Why do you persist with this attitude? It's nonsensical. And really, you're telling me if the conclusion of a contradiction implies the non-existence of H, you don't accept the phrase "contradicted H"? Sorry, but there's no need for rocket science here. So I didn't want to type the entire thing out...
And you know perfectly well that H takes a program and an input. So what could a tuple possibly be for?
The part about A being member of B earlier on... was that really necessary?
I mean, I've already built a computing system that uses dataflow predicates as well as ZFC (or parts of it) in order to enable implicit concurrency over multi-core and distributed networks without the programmer dealing with it at all (other than specifying the machines). I had to use (and will use) a lot of algorithms based on graph theory to enable a lot of the interconnections. So yeah, A being a member of B. That's a tough one for me considering this is how types, categories and enumerations work.
These rules break down if the terms in question do not exist. You're taking for granted that they exist when you've only assumed their existence. I find this very strange. This isn't like regular math. When you deal with existence, rules that you normally take as absolute aren't so anymore.
1. H is assumed to be the oracle.
2. H ∈ W
3. Q ∈ W
4. #3 (Q ∈ W) implies contradiction on #2. So H ∉ W and Q ∉ W.
That ok with you? (even if loosely defined)
Unfortunately, there's one extra step.
5. #4 (Q ∉ W) implies that W (w/ Q) != W (w/o Q) which means that H cannot be the oracle, thus invalidating the definitions #1, #2 and #3.
By Vorlath, # 2. January 2008, 04:44:43
See, this is the problem. You say that "A contradiction can be contradicted", but I have no idea what you mean by this.
A contradiction is a logical incompatibility between two propositions. For instance, "H ∈ W = H ∉ W" is a contradiction, because "H ∈ W" and "H ∉ W" are propositions that are the logical inverse of each other. But the contradiction is not itself a proposition. It's not a statement that evaluates to true or false, so we can't contradict it.
Secondly, define "existence". In any formal logic, each term you use needs to stem from your set of base axioms. In the case of turing machines, the closest thing to "existence" is whether a variable is a well formed turing machine (H ∈ W). But this isn't anything special. The rules do not go out of the window, as if they did, you wouldn't be dealing with a formal system anymore! You can reason about a false proposition just as easily as you can a true proposition.
Thirdly, your step 5 does not invalidate the previous steps, because for those steps, H ∈ W is assumed to be true. Let's look at it another way. Proof by contradiction says that if you can show that A implies not A, then not A is a fact. In other words:
A → ￢A = ￢A
Is this statement true? Well, let's assume A is true:
T → ￢T = ￢T
T → F = F
F = F
T
Okay, now let's assume A is false:
F → ￢F = ￢F
F → T = T
T = T
T
Again, it all works out. So if we can show that H ∈ W → H ∉ W, then H ∉ W. In other words, if we can show that the _assumption_ of H ∈ W leads logically to H ∉ W, then H ∉ W is true. But just because H ∉ W is true doesn't invalidate our original argument, because H ∈ W → H ∉ W = H ∉ W is a tautology.
Do you see now? The assumption that H ∈ W isolates the proof from your point 5, since Q ∉ W implies H ∉ W, which is counter to the assumption. Or, to put it another way, if the assumption is false, the proof still holds, because F → x = T.
By anonymous user, # 2. January 2008, 10:05:22
Okay, now I'm the one making misleading and difficult to parse statements. I've just reread my paragraph on contradictions, and looking at it fresh, it's a pretty rubbish and misleading explanation.
Let me try and phrase it better:
A contradiction is a logical incompatibility between two propositions.
A contradiction always resolves to false.
You cannot contradict a boolean value.
Therefore you cannot contradict a contradiction.
The rest of my previous post seems okay, though. This is why I prefer to work with symbols and formula; mistakes are a lot easier to spot
By anonymous user, # 2. January 2008, 12:56:31
But this is exactly it. The Halting Proof only has ONE proposition. This is how you can contradict a contradiction by showing that what you thought was a second proposition wasn't. You need critical thinking and stop looking at what you read and accept it blindly. If you want a reference look at what Aristotle wrote in 350BC. It's not complicated. It's one of the oldest fallacies in logical thinking known to humankind. And you're trying to push this on me. I know intuitively that this is wrong. Yet you complain that I have critical thinking when I've shown how it's begging the question.
Right, but if W is not longer valid, you have ZERO propositions. There is no contradiction. You've invalidated the DEFINITIONS instead of showing a contradiction. Your propositions are gone. Poof! Without propositions, there are no contradictions. Didn't you learn this? Aristotle showed it over 2000 years ago.
edit: I should add that if the only "change" to W is H, then it's fine.
Exist means being part of a set. The Halting Problem is always about having an oracle that works on ALL programs. You use W. I use P.
No, this is where you are wrong (the last sentence).
Here's an easier example.
N = A/B
I can manipulate these variables all I want and can come to all sorts of conclusions AS LONG AS B is NOT 0. If B is 0, then all the rules go out the window. No matter what propostion you've made with N in it, if it's found that B is zero, then everything falls apart. You can't even claim that B was zero if this result came about an assumption. That's how bad it gets. You must throw everything out. If you've done limits you know what I mean. Just consider l'Hopital's rule.
With the Halting Proof, the same thing happens with P (or W as you use). If it's found that W wasn't as assumed, then all the rules go out the window. Every logical step you've taken is now unfounded. This is because the oracle has to work on CORRECT W, but you've shown your assumed W is incorrect. If you end up showing that W does not contain programs that you assumed it did, then the definition of W is invalid and all your propositions disapear. It's not falsehood. It's INVALID. Like division by ZERO. The proposition itself goes away. Hence, no contradiction. Or like I've said, you've contradicted the contradiction.
This is the definition of begging the question or of the fallacy of many questions. By asking a question, you make an unfounded statement within it. Here's an example.
Is your brother in the army?
First, it looks like the proposition is that someone is in the army. But in reality, it's ALSO presuming that there IS a brother in the first place or insinuating that he would be in the army.
With the Halting Proof, you're not only assuming H belongs in W (which is fine), you're also assuming Q belongs in W. Your definition of W is begging the question. We're being asked to believe that W holds Q without it being proven. It's an assumption. If W doesn't hold Q, then ALL your proposotions are invalid. Not false. INVALID. Because you used the fallacy of many questions. They disapear. Meaning that without even one proposition, you cannot have a contradiction.
So it's not about a FALSE proposition. It's about the foundation of the proposition (W). Just like the question about the brother. If there is no brother, then the proposition falls apart. It's not false. It's not true. The question just doesn't make sense. In the Halting Proof, there is NO W. So there is no H, no Q, and no other program for that matter. That's all the proof is showing.
Begging the question. Look it up. It's one of the oldest fallacies known. I knew it intuitively when I saw the proof. You can look up Aristotle's work if you want a reference and there are many Spanish authors that also brought the term "begging the question" to the mainstream. So don't believe me. Look it up.
By Vorlath, # 2. January 2008, 21:20:07
If Q ∉ W, then W != RW.
And if W != RW, then you cannot say H ∉ W or H ∈ W because W ∉ Universe of logic. And if you can't say H ∉ W or H ∈ W, then you certainly can't say H ∉ W != H ∈ W.
Get it? I don't know what to call the set that W is in, but it's no longer in it. Call it the Universe. Call it whatever.
edit: I'll add this.
If you conclude H ∉ W != H ∈ W, but that this also implies you can't say H ∉ W != H ∈ W, then that would mean those two statements are themselves in contradiction with each other, no? This is contradicting the contradiction. This is the natural conclusion of circular logic. The whole thing falls apart. What does it mean? Nothing. You can't base anything on this. The proof says nothing.
By Vorlath, # 2. January 2008, 21:50:04