Re: [PO] Halting Problem Final Conclusion
From: Simon G Best (s.g.best_at_btopenworld.com)
Date: 09/09/04
- Next message: Ash: "Re: Closest Point Problem"
- Previous message: Bill F: "Re: theorems/problems with lots of quantifiers"
- In reply to: |-|erc: "Re: [PO] Halting Problem Final Conclusion"
- Next in thread: |-|erc: "Re: [PO] Halting Problem Final Conclusion"
- Reply: |-|erc: "Re: [PO] Halting Problem Final Conclusion"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Thu, 9 Sep 2004 05:42:25 +0000 (UTC)
|-|erc wrote:
> "Simon G Best" <s.g.best@btopenworld.com> wrote in
>
>>|-|erc wrote:
>>
>>>"Simon G Best" <s.g.best@btopenworld.com> wrote
>>>
>>>>|-|erc wrote:
>>>>
>>>>>"Simon G Best" <s.g.best@btopenworld.com> wrote in
>>>>>
>>>>>>|-|erc wrote:
>>>>>
>>>>[...]
>>>>
>>>>>>No, we are *not* "safe to assume" that. A lack of proof *does not* mean
>>>>>>that it's "safe to assume" the opposite.
>>>>>
>>>>>If we *label* HypotheticalFunction() as an assumption then we can assume it.
>>>>
>>>>Certainly an assumption is an assumption. That does not contradict what
>>>>I said.
>>>
>>>fraid so.
>>>
>>>if you have NOT proven x, i may assume !x T/F
>>
>>And that still doesn't mean it's a "safe" assumption.
>
> You mean I *can assume* halt exists, but it's NOT *safe to assume* halt exists
> in this domain of discourse??
Indeed - an assumption may turn out to be incorrect, and a lack of
disproof of such an assumption does not itself mean that it's unlikely
to be incorrect.
> You are splitting a fine hair between what is formally correct for me to write
> and one particular colloquial meaning of "safe".
So, what did you mean by "safe"?
> <unsnip>
> but how do you prove one program cannot recognise the other?
>
> it is your burden to show they can't. otherwise we are safe to assume
> a COMPLETE ALL KNOWING halt program can be written
> </unsnip>
Such an assumption would be wrong, as it's already been proven that no
such program (for a Universal Turing Machine) could be written. How
would such a wrong assumption be "safe"?
>>[...]
>>
>>>>Do you see the contradiction now?
>>>
>>>i think so, that was the 1st attempt at an infinite set of phalt. now i'm using
>>>only one result of the halt function, to determine the opposite (does not halt)
>>>you have to trial infinite n.
>>
>>That doesn't work. A Turing Machine using that method will never halt,
>>because it will never "trial infinite n" in any finite amount of time.
>>Surely this is just utterly obvious?
>
> The halt machine runs for 1 microsecond and outputs
> "program 922 halts with probability 0.999999999999999"
Which would be wrong. Either the probability of program 922 halting is
one, or it is zero. After all, Turing Machines are completely
deterministic.
> On a second trial, after 1 second it outputs
> "program 922 halts with probability 0.9999999999999999999999999999999999"
Which would again be wrong, for the same reason.
> After 10 minutes it outputs
> "program 999 halts with probability 0.999999999999999999999999999999999
> 99999999999999999999999999999999999999999999999999999999999999
> 99999999999999999999999999999999999999999999999999999999999999"
And, again, wrong.
> The halt machine runs for 100 microseconds on another input,
> "program 833 does not halt"
>
> and again
> "program 99484 does not halt"
Those two would be right.
> The halt machine does halt for one output value, and gives accurate information for the other.
Nope. The information it gives "for the other" is always wrong.
> The infinite run allows it to
> 1/ still give perfectly useful results
> 2/ evade ANY contradiction
Running it forever, and waiting an infinite amount of time for its final
results, is no better than just running the Turing Machine in question,
on the input in question, and waiting to see whether or not it halts
before an infinite amount of time has passed. We don't need your
'solution' for that!
>>[...]
>>
>>>>But, for all functions f, for all inputs a, where f does not halt on a,
>>>>your 'solution' never determines that f does not halt on a.
>>>>
>>>>It's no better than just running the UTM on (f, a) and waiting to see
>>>>whether or not it ever halts.
>>>>
>>>>Indeed, that is really all your 'solution' is!
>>>
>>>not at all, that was just a trivial *example* of the solution using clumsy UTMs.
>>>the idea works for an infinite set of smart phalt functions, or the opposite! an
>>>infinite set of nohalt functions.
>>
>>But it *doesn't work*.
>
> assumption
No. It is not an assumption, it's already been proved that no Turing
Machine can solve the Halting Problem for all Turing Machines, for all
inputs.
[...]
>>
>>Except that you haven't provided a way to actually list the elements of
>>NHalt2. Indeed, no Turing Machine can list the elements of NHalt2, the
>>proof being fairly similar to the proof I quickly sketched for the
>>nonexistence of a Turing Machine that could list the elements of AllHalt.
>
> assumption
No, again, it's not an assumption.
Here's a quick sketch of a proof that no Turing Machine can list the
elements of NHalt2:-
Let's assume that there exists a Turing Machine, N, which lists the
elements of NHalt2.
Given N, we can easily construct another Turing Machine, H, which takes
the pair (f, a) as input, and does the following.
First, it simulates f(a) for a finite number of steps. If, by the end
of that simulation, f(a) has halted, H outputs 'halts', and halts. If,
instead, f(a) hasn't halted, H simulates N for enough steps for N to
give one element of NHalt2, n_1. It then simulates n_1(f, a). If
n_1(f, a) outputs 'does not halt', H outputs 'does not halt', and halts.
Otherwise, it resumes its simulation of f(a) for a further finite
number of steps. If f(a) still hasn't halted, it resumes its simulation
of N to get the next element of NHalt2, n_2, and simulates n_2(f, a),
and so on.
H keeps repeating this process until either f(a) halts, or an n produced
by N is reached such that n(f, a) outputs 'does not halt'.
If f(a) halts, H will reach that point in a finite number of steps. If
f(a) never halts, it will reach an n produced by N such that n(f, a)
outputs 'does not halt' in a finite number of steps. So, either way, H
will reach a final result in a finite number of steps.
We already have the classic proof that H cannot exist. Therefore, N
cannot exist.
>>Without such a Turing Machine,
a Turing Machine listing the elements of NHalt2, that is,
>>you can't actually have a Turing Machine
>>applying your method.
>
> falicious argument. "The halt program is not written, that proves it doesn't exist."
I never said that, and it certainly wasn't my argument. My argument was
not based on "The halt program" having not been /written/, but on the
/unwritability/ of a program (for Universal Turing Machines) /to list
the elements of NHalt2/.
>>>the program with godel number 1000 is
>>>
>>>10 print 10
>>>
>>>UTM(2, 1000) = DONTKNOW
>>>UTM(6, 1000) = DONTKNOW
>>>UTM(33, 1000) = DONTKNOW
>>>UTM(655, 1000) = DONTKNOW
>>>
>>>>From these outputs we can determine *without running the programs*
>>>1/ program 999 does not halt
>>>2/ program 1000 halts with probability of error 1/16.
>>
>>That would be an heuristic, *not* a general solution to the Halting Problem.
>
> look up heuristic, then look up solution.
"*General* solution to the *Halting Problem*" is what I said.
"Solution" in the mathematical sense. "General solution" in the
mathematical sense.
An heuristic is *not* a general solution to the Halting Problem, as
there are cases in which it either fails to yield a solution, or gives
the wrong result.
> anyone else want to actually disprove NHalt2 can exist?
You seem to be confusing sets with Turing Machines that list the
elements of those sets. There certainly are sets that match your
definition of NHalt2 that exist - an infinite number of such sets, in fact!
> Atleast now we know why everyone here is so stubborn. YOU'VE GOT 2 FACTS!!
We've got rather more than just two facts.
> 1/ theres a proof that halt has a contradiction
There are indeed proofs (including the classic 'loop if halts' proof)
that the existence of a Turing Machine that solves the Halting Problem
in the general case (for all Turing Machines, for all inputs) implies a
contradiction, and that therefore no such Turing Machine can exist.
> AND
> 2/ NO ONE'S WRITTEN A HALT FUNCTION
>
> must be true, when 1 fails see 2
Uh?
Simon
- Next message: Ash: "Re: Closest Point Problem"
- Previous message: Bill F: "Re: theorems/problems with lots of quantifiers"
- In reply to: |-|erc: "Re: [PO] Halting Problem Final Conclusion"
- Next in thread: |-|erc: "Re: [PO] Halting Problem Final Conclusion"
- Reply: |-|erc: "Re: [PO] Halting Problem Final Conclusion"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
