Peter,
What is the correct return value that a halt decider
can provide for a program that does the opposite of
whatever value it returns?
Neither value.
And that is exactly the proof of the Halting Theorem.
An [incorrect question] is defined as any question such that a correct answer does not exist from the set of all possible answers.
Assume H is a correct total halt decider, and construct D so that:
-a-a if H(D) says HALTS:
-a-a-a-a-a-a D loops forever
-a-a if H(D) says DOES NOT HALT:
-a-a-a-a-a-a D halts
Now ask H(D).
If H(D) says HALTS, it is wrong.--
If H(D) says DOES NOT HALT, it is wrong.
Therefore there is no value H can return while remaining a correct halt decider.
But notice what follows logically.
It is NOT:
-a-a therefore D is an "incorrect question".
It is:
-a-a therefore the assumed correct total H does not exist.
That is the reductio.
We assumed:
-a-a H exists and correctly decides every program.
From that assumption we constructed D and derived:
-a-a H(D) cannot be correct.
Therefore the assumption is false.
In symbols:
-a-a Assume H exists.
-a-a Construct D using H.
-a-a H(D) = HALTS
-a-a-a-a-a-a => D does not halt
-a-a-a-a-a-a => H is wrong.
-a-a H(D) = DOES_NOT_HALT
-a-a-a-a-a-a => D halts
-a-a-a-a-a-a => H is wrong.
-a-a Therefore H cannot satisfy its assumed specification.
That is precisely the Halting Theorem.
Your question therefore does not expose a misconception in the proof.
It reproduces the contradiction used by the proof.
The only way to obtain a different conclusion is to explain why the contradiction should be attributed to the QUESTION rather than to the assumption that H exists.
And that requires an independent argument.
You cannot simply define:
-a-a a question for which no correct answer can be
-a-a returned by H is an "incorrect question"
because the entire purpose of the diagonal construction is to prove that
no such universally correct H exists.
Doing that would transform:
-a-a Assume H exists.
-a-a Derive contradiction.
-a-a Therefore H does not exist.
into:
-a-a Assume H exists.
-a-a Derive contradiction.
-a-a Therefore exclude the case producing the contradiction
-a-a from H's domain.
But that simply protects the original assumption by restricting its domain.
And then H is no longer a halt decider for all programs.
So to answer your simplified question as directly as possible:
-a-a What correct value can H return for D?
-a-a NONE.
And the standard conclusion is:
-a-a therefore a total correct H cannot exist.
If your conclusion is instead:
-a-a therefore D is outside H's domain,
then you have conceded the standard result:
-a-a H cannot decide halting for every program.
You have simply given the undecidable case a different name.
Peter,
I followed the x86utm link and read the README, and I think this finally gives us a very precise technical point to examine.
Your README says:
-a-a The key mistake of the halting problem proofs is that they
-a-a require a halt decider to report on the behavior of something
-a-a other than the behavior specified by its finite string input.
and Axiom 2 says:
-a-a The only correct finite string transformation rules that HHH
-a-a is allowed to apply to its finite string input DD is specified
-a-a by the operational semantics of the C programming language.
-a-a This requires DD to be simulated by HHH according to these rules.
I think the second statement is exactly where your argument departs from
the Halting Theorem.
A hypothetical halt decider is NOT required to determine termination by simulating its input.
Peter,
I think we have now achieved an important clarification, and I want to preserve it rather than continue arguing past it.
I wrote:
-a-a Then you have changed "correct computation"
-a-a into "justified computation".
-a-a That is an epistemic notion.
and you answered:
-a-a Yes. That is a correct clarification.
Good.
You have also now accepted that the ROM itself implements its stipulated mapping. So I think our hardware disagreement is essentially resolved.
The remaining issue is much narrower.
You write:
-a-a Deciders must apply finite string transformations that are
-a-a semantically relevant to the decision criteria.
I think your three recent replies now identify the exact point on which
we disagree.
You say:
-a-a A halt decider is required to derive its result through
-a-a the application of finite string transformations to its
-a-a finite string input. The halting theorem totally ignores
-a-a this.
and:
-a-a A halt decider is also implicitly required to limit these
-a-a finite string transformations to those relevant to determining
-a-a the halting property specified by this finite string input.
-a-a The halting theorem totally ignores this.
and:
-a-a The halting theorem is framed as the impossibility of
-a-a a halt decider returning a correct value to its caller
-a-a that is not even its input.
I don't think the Halting Theorem ignores any of these issues.
I think you are conflating three different things:
-a-a 1. the finite representation of a program P,
-a-a 2. the computation denoted by that representation,
-a-a 3. the context in which that computation is executed.
These are related, but they are not identical.
Consider an ordinary static analyzer A.
I can give A the finite source code:
-a-a int f() {
-a-a-a-a-a-a return 17;
-a-a }
The INPUT to A is a finite string representing f.
What A is asked to determine is a property of the computation denoted by that finite string.
There is no contradiction here between:
-a-a static finite string input
and:
-a-a executing process.
The finite string REPRESENTS the program whose possible execution we are reasoning about.
That distinction is fundamental to essentially all program analysis.
Likewise, there is no "mutual exclusivity" between a program being the caller of a function during one execution and a representation of that
same program being the input data of that function.
Assume H exists.
Then construct D:
-a-a D():
-a-a-a-a-a-a if H(<D>) == HALTS:
-a-a-a-a-a-a-a-a-a-a loop forever
-a-a-a-a-a-a else:
-a-a-a-a-a-a-a-a-a-a halt
Now ask H(<D>).
If H says HALTS, D does not halt.
If H says DOES_NOT_HALT, D halts.
You call this an "incorrect question".
function LoopIfYouSayItHalts (bool YouSayItHalts):
if YouSayItHalts () then
while true do {}
else
return false;
Does this program Halt?
(Your (YES or NO) answer is to be considered
translated to Boolean as the function's input
parameter)
Please ONLY PROVIDE CORRECT ANSWERS!
An [incorrect question] is defined as any question such that
a correct answer does not exist from the set of all possible
answers.
Peter,
I think your latest example makes the disagreement extremely precise:
-a-a int main()
-a-a {
-a-a-a-a-a DD(); // is neither the input to HHH nor a finite static string
-a-a }
I completely agree with the comment.
DD() executing in main is NOT the input to HHH.
But the Halting Theorem does not require it to be.
Peter,
When both of your own answers are wrong this proves
that I am correct.
No. It proves exactly the Halting Theorem.
Peter,
When both of your own answers are wrong this proves
that I am correct.
No. It proves exactly the Halting Theorem.
You are overlooking what your program depends on.
Your 2004 example says:
-a-a if YOU say HALTS:
-a-a-a-a-a-a loop
-a-a else:
-a-a-a-a-a-a halt
So there is no answer that can be both:
-a-a 1. supplied to the program, and
-a-a 2. a correct prediction of the resulting behavior.
Agreed.
But that does not prove that halting is an "incorrect question".
function LoopIfYouSayItHalts (bool YouSayItHalts):
if YouSayItHalts () then
while true do {}
else
return false;
Does this program Halt?
(Your (YES or NO) answer is to be considered
translated to Boolean as the function's input
parameter)
Please ONLY PROVIDE CORRECT ANSWERS!
| Sysop: | Amessyroom |
|---|---|
| Location: | Fayetteville, NC |
| Users: | 76 |
| Nodes: | 6 (0 / 6) |
| Uptime: | 55:54:13 |
| Calls: | 1,265 |
| Calls today: | 1 |
| Files: | 1,362 |
| D/L today: |
3 files (2,684K bytes) |
| Messages: | 285,712 |