[|-|erc] Re: [PO] Halting Problem Final Conclusion
From: Simon G Best (s.g.best_at_btopenworld.com)
Date: 09/09/04
- Next message: Mikito Harakiri: "Re: Data structure for indexing on multiple keys."
- Previous message: Bill F: "Re: An article about factorization"
- In reply to: |-|erc: "Re: [PO] Halting Problem Final Conclusion"
- Next in thread: |-|erc: "Re: [|-|erc] Re: [PO] Halting Problem Final Conclusion"
- Reply: |-|erc: "Re: [|-|erc] Re: [PO] Halting Problem Final Conclusion"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Thu, 9 Sep 2004 21:12:23 +0000 (UTC)
You haven't said why you cross-posted to sci.math, so I'm setting the
follow-ups back to just comp.theory and sci.logic.
|-|erc wrote:
> "Simon G Best" <s.g.best@btopenworld.com> wrote
>
>>|-|erc wrote:
>>
>>>"Simon G Best" <s.g.best@btopenworld.com> wrote in
>>>
[...]
>>
>>So, what did you mean by "safe"?
>
> I just meant this :
>
>>>it is your burden to show they can't. otherwise we CAN assume
>>>a COMPLETE ALL KNOWING halt program can be written
>
> I don't know why you think safe implies absolute truth / guaranteed assumption here.
I don't. I think "safe to assume" means that we could make whatever
assumption it is, and that assumption is unlikely to be wrong, or, if it
is wrong, it isn't really going to matter that it's wrong. I thought it
was "safe to assume" that that was the sort of thing you meant by "safe".
> safe <=> guaranteed ??
>
> I don't see 'safe to assume' being a stronger statement than "we can assume".
> "a safe assumption" could be interpreted as something more than an assumption.
This is getting silly. Perhaps Kent Paul Dolan's right? Would it be
"safe to assume" that he's right about you? After all, it's certainly
the case that I /can/ assume that he's right about you.
>>><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"?
>
> because you haven't proven a 3 valued system wont work, everyone here
> is assuming it will be wrong most of the time. it may just output 'don't know' on
> the vary rare occasions it faces a loop-if-halt type program.
>
> software-can-recognise loop-if-halt construct -> halt function may be
> entirely possible
You said, "a COMPLETE ALL KNOWING halt program", but now you're saying
"it may just output 'don't know' on the vary rare occasions it faces a
loop-if-halt type program." So, you concede that it could not be "a
COMPLETE ALL KNOWING halt program" after all.
The Halting Problem /itself/ is 'two-valued', in the sense that each
Turing Machine (TM) on each input either halts or does not halt. Those
are the only two possibilities.
A general solution to the Halting Problem, therefore, is one which is
also 'two-valued'. If TM M halts on input x, the solution to the
problem of whether or not M halts on x is that it does halt on x. If TM
M does not halt on x, the solution to that same problem is that it
doesn't halt.
A "3 valued system", which ever outputs "'don't know'", is therefore
clearly not a general solution to the Halting Problem.
[...]
>>>
>>>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.
>
> Back to the probability soln..
>
> you misinterpret. each phalt function declares the halt value with 50% chance
> of being correct. if 100 phalt functions all declare 'don't know' then we have
> 0.5^100 probability of error in the result.
>
> I got the idea from the prime witness algorithm. [...]
>
> A Halt function can work the same, its not a straight forward YES/NO output but
> its still a practical soln.
Whether or not it would be a practical 'solution', the Halting Problem
is a /mathematical/ problem.
>>>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.
>
> Why would such a hypothetical output be wrong? Its just a program spec.
It might be /your/ "program spec", but it does *not* match the Halting
Problem. The Halting Problem is itself the specification of relevance
to the Halting Problem.
[...]
>>
>>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!
>
> You DONT run it for infinite time. The probability of error reduces inverse exponentially,
> if NHalt2 existed it would give answers very quickly. The halting proof however
> requires an absolute commital, 0.9999999999999999999999999 chance that the
> program will always halt is not good enough to get a contradiction.
It's the Halting /Problem/ that "requires an absolute commital".
[...]
>>
>>Here's a quick sketch of a proof that no Turing Machine can list the
>>elements of NHalt2:-
>>
[...]
>
> Right.
>
> A PHalt sequence and an NHalt sequence cannot both be possible.
You haven't said what "NHalt" is.
And "A PHalt sequence" certainly does exist, if, by "PHalt sequence",
you mean a list of the elements of AllHalt. But no Turing Machine can
compute that list.
> Since
> a PHalt sequence can be constructed with UTMs, NHalt is impossible.
What do you mean by "a PHalt sequence can be constructed with UTMs"?
Did you mean that a UTM can be used to compute a list of the elements of
AllHalt?
[...]
>
> Can you disprove a PHalt sequence is computable?
I sketched such a disproof in an earlier post.
> Each is a partial halt function
> that has 50% chance of stating any given f(a) will halt, otherwise it returns DONTKNOW.
Not according to your second post in this thread
(news:zc9%c.21947$D7.11256@news-server.bigpond.net.au), in which you said:-
> An algorithm produces a set of godel numbers for pHalt programs.
> AllHalt() = {1, 5, 20, 55, 999, 23838... }
>
> Each of these programs is a partial halt function that behaves correctly
> with the outputs :
>
> 1/ halts
>
> 2/ does not halt
>
> 3/ don't know
You really do need to /clearly/ define things, and *stick* to those
definitions.
Simon
- Next message: Mikito Harakiri: "Re: Data structure for indexing on multiple keys."
- Previous message: Bill F: "Re: An article about factorization"
- In reply to: |-|erc: "Re: [PO] Halting Problem Final Conclusion"
- Next in thread: |-|erc: "Re: [|-|erc] Re: [PO] Halting Problem Final Conclusion"
- Reply: |-|erc: "Re: [|-|erc] Re: [PO] Halting Problem Final Conclusion"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
