R3COGNITION OF THE HALTING SOLN
From: |-|erc (gotch_at_beauty.com)
Date: 09/13/04
- Next message: Rob Duncan: "Re: [|-|erc] Re: [PO] Halting Problem Final Conclusion"
- Previous message: Torkel Franzen: "Re: Raatikainen's critique of Chaitin"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Mon, 13 Sep 2004 03:45:38 GMT
"Acme Diagnostics" <LFinezapthis@partpostmark.net> wrote in >
> Thanks for the probability idea about a real-world solution to
> the Halting Problem recently when you were feeling well. Of all
> those who talked about that in real-world context, you had the
> best idea in my opinion. I think that was a major contribution,
> and I am sure I will be able to use that idea someday.
>
> Larry
Thank you Larry, Halt() is a big nut to crack. Here is the outline of
the solution for those who missed it among the heated discussion.
halt(f, a) -> pHalt2(n) -> P(UTM(n, f(a))='halt') = 0.5
!halt(f, a) -> pHalt2(n) -> UTM(n, f(a))='don't know'
pHalt2 is an (infinite) set of functions that satisfy pHalt below, with the added
contraint P(UTM(n, f(a))='halt') = 0.5. Therefore a randomly selected pHalt
function has 50% odds of answering the halt program for some given input.
(different set notation)
halt(f, a) -> En, n e pHalt, UTM(n, f(a))=true
!halt(f, a) -> An, n e pHalt, UTM(n, f(a))='don't know'
For example, pHalt could be an infinite set of Universal Turing Machines,
but they timeout after various amounts of time. If the parameter f(a) halted
in that time then it outputs TRUE, otherwise it timed out and outputs DONTKNOW.
Since the number of these partial Halt functions is infinite, we should come across
one with enough test cycles to determine if any function halts.
By itself pHalt is still useless as it only gives one output value, HALTS. But if
each pHalt function has 50% chance of being correct (something more powerful
than the UTM), then determining NOTHALT is a simple probabilistic procedure.
e.g.
pHalt2() = {2, 6, 33, 655, ..}
i.e.
pHalt(2) = true
pHalt2(6) = true
pHalt2(33) = true
..
pHalt2 is an infinite set of godel numbers whos functions can be parsed by a UTM.
each of these functions has independant probability of 50% of answering if the input function
halts, otherwise it will return DONTKNOW.
As an example.
the program with godel number 999 is
10 goto 10
UTM(2, 999) = DONTKNOW (ignoring the parameter of function 999)
UTM(6, 999) = DONTKNOW
UTM(33, 999) = DONTKNOW
UTM(655, 999) = DONTKNOW
...
Since :
!halt(f, a) -> pHalt2(n) -> UTM(n, f(a))='don't know'
the program with godel number 1000 is
10 print 10
UTM(2, 1000) = HALT
UTM(6, 1000) = DONTKNOW
UTM(33, 1000) = HALT
UTM(655, 1000) = DONTKNOW
Given :
halt(f, a) -> pHalt2(n) -> P(UTM(n, f(a))='halt') = 0.5
>From these outputs we can determine *without running the programs*
1/ program 999 does not halt with probability of error 1/16
2/ program 1000 halts
A *solution* to the halting problem is apparent, but it cannot be fully represented as
an *algorithm*, so the halting proof will fail here to surface a contradiction.
Herc
- Next message: Rob Duncan: "Re: [|-|erc] Re: [PO] Halting Problem Final Conclusion"
- Previous message: Torkel Franzen: "Re: Raatikainen's critique of Chaitin"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
|
