|-|erc
Posts:
1,782
Registered:
1/25/05
|
|
Re: Halting problem totally unsolvable?
Posted:
Jan 29, 2007 3:56 AM
|
|
"Chris Smith" <cdsmith@twu.net> wrote
> |-|erc <h@r.c> wrote:
> > It may be possible to program halt functions that return halt values
> > with arbitrary precision.
> >
> > e.g. the program halts with 99.9999999% certainty.
> >
> > The more iterations the halt functions are run the higher certainty they achieve.
> > The halting proof does not dispute this.
>
> I'm having trouble even assigning a meaning to that. For a given
> instance of the halting problem, the answer is either yes or no, with
> P=100%. Given your hypothetical program for the above claim, and any
> statement about a level of certainty you care to make, I can easily give
> you a set of inputs that cause your program to be wrong every time.
> Given that your program could be wrong 100% of the time, what exactly
> does it mean for it to be "99.9999999% certain"?
Suppose n is a composite number.
Then over half of numbers in 1..n are witnesses to compositeness.
Repeat
select random number 1..n
test if witness
until witness found or 99.9999% certain its prime
Finding a witness is like finding a factor, you know its not prime.
The more numbers you test and don't find a witness, the higher the certainty the
number is prime.
Iteration prime with x% certainty
1 50%
2 75%
3 87.5%
4 93.75%
5 96.875%
...
It's an algorithm for determining primes very quickly, but its not deterministic, there is
always that 0.0000000001% chance that the number is a composite and you need to
test further. Now imagine if witnesses to halting existed with a similar distribution, you
could effectively calculate when programs halted without that tiresome halting proof
getting in your way!
Herc
|
|
