Because it's trivial.
Code:
GET S
IF S = "WHILE TRUE; DO {}" PRINT "DOESN'T HALT"
There is a program that tells if particular programs will halt. Note how its existence does not violate the Halting Problem, since the HP doesn't say what you think it says. Think a bit more carefully about what the HP actually states, and what it actually implies. The HP states that it's not possible to build a machine that can tell for
any input whether the machine halts or not.
See also
WP (Direct link to section, "Recognizing partial solutions"), if the above trivial example doesn't do it for you.
The point is: these are equivalent statements.
The point you objected to is that for the GC, there is a definite truth value. The point you're trying to raise is irrelevant.
What you're trying to say is not implied by GFIT, just like what you're trying to say about the halting problem is not implied by the HP. You're confused because they kind of look like the same thing, but GFIT is talking about the
existence of theories that cannot be proven within a system (true theories at that), and
not the
non-existence of theories that can. Just like HP is talking about being able to come up with a
general algorithm to tell that
any machine would halt, and
not that it's impossible to tell if a given machine would halt.
Your confusion leads you to think that Godel is saying that if you don't know whether or not a theorem is true, you can't show that it has a definite truth value. Godel's Incompleteness Theorem says nothing of the sort--not even close.
If you cannot compute it then - computationally speaking - there is no answer.
That's not the case. There's an entire field of mathematics where the existence of some kind of way to do something can be proven even though you can't find out the particular way to do it. There's absolutely no principle, or no theory, that says you can't do that. GFIT is not such a theory either--GFIT simply says that there are statements that cannot be proven (analogously, GFIT says there are rabbits, not that all animals are rabbits, nor that if you don't know what an animal is, it must be a rabbit).
I can confirm the halting problem up to any arbitrary number too.
No you can't. To do this, you would have to be able to play the other side of the same kind of game I'm playing with you. I pick a number, and you have to show what all Turing machines less than that number will do (halt or not halt), and do it in a finite amount of time. You can't do that.
Okay sure. You do that an infinite number of times and get back to me when you're done.
For the same reason I don't have to write down every infinite number, of Godel doesn't have to write down all possible mathematical systems, I don't have to do this an infinite number of times.
Think of it this way. If I can pick S given your arbitrarily large M, that means that
you cannot pick an M for which I can't pick that S. This is much more powerful than you are giving it credit for.
Of course, the one thing it doesn't prove is the one thing I'm not claiming--that you can prove the GC true if it is.
But you cannot compute that!
Doesn't matter. Look at what GC says. If I
can't prove it, and if, given that it's false, I necessarily
could prove it false, it follows that the only way I can't prove it is if it's true. If it's undecideable, even in 72 point font that blinks, is bolded, and is scrolling in marquee playing parade music, that still means GC is true.
The catch is that I wouldn't necessarily be able to
prove that I can't prove it in that case, so I wouldn't necessarily be able to know.
Actually I'm arguing that if you're going to try using a brute force search then you're pretty much screwed
Right, but what you objected to initially was whether or not it had a definite truth value. That's
still wrong--it can have a definite truth value even if you don't know what it is... GFIT doesn't say otherwise. And it's possible that for certain theories, you can
show it has a definite truth value, without knowing what it is--GFIT again doesn't say otherwise. All GFIT says is that there are things you
can't prove--in fact, GC can be something I can't prove,
and be true! I would just have to not be able to know I can't prove it due to what GC actually is.
Basically: you cannot be complete and consistent - in a sufficiently powerful formal language there will be some statement you can make whose truth value cannot be decided in that language.
Right. Anything in there about not knowing if it has a definite truth value?
The point is: these are equivalent statements.
The point you objected to is that for the GC, there is a definite truth value. The point you're trying to raise is irrelevant.
What you're trying to say is not implied by GFIT, just like what you're trying to say about the halting problem is not implied by the HP. You're confused because they kind of look like the same thing, but GFIT is talking about the existence of theories that cannot be proven within a system (true theories at that), and not the non-existence of theories that can. Just like HP is talking about being able to come up with a general algorithm to tell that any machine would halt, and not that it's impossible to tell if a given machine would halt.
Your confusion leads you to think that Godel is saying that if you don't know whether or not a theorem is true, you can't show that it has a definite truth value. Godel's Incompleteness Theorem says nothing of the sort--not even close.
If you cannot compute it then - computationally speaking - there is no answer.
That's not the case. There's an entire field of mathematics where the existence of some kind of way to do something can be proven even though you can't find out the particular way to do it. There's absolutely no principle, or no theory, that says you can't do that. GFIT is not such a theory either--GFIT simply says that there are statements that cannot be proven (analogously, GFIT says there are rabbits, not that all animals are rabbits, nor that if you don't know what an animal is, it must be a rabbit).
I can confirm the halting problem up to any arbitrary number too.
No you can't. To do this, you would have to be able to play the other side of the same kind of game I'm playing with you. I pick a number, and you have to show what all Turing machines less than that number will do (halt or not halt), and do it in a finite amount of time. You can't do that.
Okay sure. You do that an infinite number of times and get back to me when you're done.
For the same reason I don't have to write down every infinite number, of Godel doesn't have to write down all possible mathematical systems, I don't have to do this an infinite number of times.
Think of it this way. If I can pick S given your arbitrarily large M, that means that you cannot pick an M for which I can't pick that S. This is much more powerful than you are giving it credit for.
Of course, the one thing it doesn't prove is the one thing I'm not claiming--that you can prove the GC true if it is.
But you cannot compute that!
Doesn't matter. Look at what GC says. If I can't prove it, and if, given that it's false, I necessarily could prove it false, it follows that the only way I can't prove it is if it's true. If it's undecideable, even in 72 point font that blinks, is bolded, and is scrolling in marquee playing parade music, that still means GC is true.
The catch is that I wouldn't necessarily be able to prove that I can't prove it in that case, so I wouldn't necessarily be able to know.
Actually I'm arguing that if you're going to try using a brute force search then you're pretty much screwed
Right, but what you objected to initially was whether or not it had a definite truth value. That's still wrong--it can have a definite truth value even if you don't know what it is... GFIT doesn't say otherwise. And it's possible that for certain theories, you can show it has a definite truth value, without knowing what it is--GFIT again doesn't say otherwise. All GFIT says is that there are things you can't prove--in fact, GC can be something I can't prove, and be true! I would just have to not be able to know I can't prove it due to what GC actually is.
Basically: you cannot be complete and consistent - in a sufficiently powerful formal language there will be some statement you can make whose truth value cannot be decided in that language.
Right. Anything in there about not knowing if it has a definite truth value?" target="_blank">WP