Re: [PO] Halting Problem Final Conclusion
From: |-|erc (gotch_at_beauty.com)
Date: 09/09/04
- Next message: Kent Paul Dolan: "[Herc] Halting Problem Final Conclusion"
- Previous message: alpha_uma: "Re: theorems/problems with lots of quantifiers"
- In reply to: Simon G Best: "Re: [PO] Halting Problem Final Conclusion"
- Next in thread: Simon G Best: "[|-|erc] Re: [PO] Halting Problem Final Conclusion"
- Reply: Simon G Best: "[|-|erc] Re: [PO] Halting Problem Final Conclusion"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Thu, 09 Sep 2004 08:18:11 GMT
"Simon G Best" <s.g.best@btopenworld.com> wrote
> |-|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"?
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.
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.
>
> > <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
>
> >>[...]
> >>
> >>>>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.
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. There is no algorithm (atleast not
last century) to determine if a number is prime in polynomial time. BUT, an
algorithm exists that on every iteration determines if a number is prime within
50% chance of error.
Basically, over half of numbers from 1..p are witnesses to compositeness. A factor
is a basic witness to compositeness, but another defn of witness makes them
more numerous. So, to determine if the number is prime, take a random sample
of numbers from 1..p and do the test. If you test 100 numbers and none of
them are witnesses, then you have 1 - 0.5^100 probability that the number is prime.
A Halt function can work the same, its not a straight forward YES/NO output but
its still a practical soln.
>
> > 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.
>
> > 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!
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.
>
> >>[...]
> >>
> >>>>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.
Right.
A PHalt sequence and an NHalt sequence cannot both be possible. Since
a PHalt sequence can be constructed with UTMs, NHalt is impossible.
>
> >>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
Can you disprove a PHalt sequence is computable? Each is a partial halt function
that has 50% chance of stating any given f(a) will halt, otherwise it returns DONTKNOW.
Herc
- Next message: Kent Paul Dolan: "[Herc] Halting Problem Final Conclusion"
- Previous message: alpha_uma: "Re: theorems/problems with lots of quantifiers"
- In reply to: Simon G Best: "Re: [PO] Halting Problem Final Conclusion"
- Next in thread: Simon G Best: "[|-|erc] Re: [PO] Halting Problem Final Conclusion"
- Reply: Simon G Best: "[|-|erc] Re: [PO] Halting Problem Final Conclusion"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
