Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: Halting problem totally unsolvable?
Replies: 32   Last Post: Apr 18, 2007 1:40 PM

 Messages: [ Previous | Next ]
 |-|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

Herc

Date Subject Author
1/21/07 mike3
1/21/07 Dirk Van de moortel
1/21/07 Rupert
1/22/07 Dirk Van de moortel
1/22/07 stephen@nomail.com
1/22/07 Denis Feldmann
1/22/07 Dirk Van de moortel
1/22/07 hagman
1/22/07 Dirk Van de moortel
1/22/07 Robert Israel
1/22/07 Dirk Van de moortel
1/25/07 mike3
1/26/07 Dirk Van de moortel
1/26/07 stephen@nomail.com
1/22/07 Rupert
1/23/07 Pubkeybreaker
1/23/07 Chris Menzel
1/24/07 Pubkeybreaker
1/26/07 Michael Press
1/21/07 Peter Smith
1/21/07 Klueless
1/21/07 Peter Smith
1/22/07 Proginoskes
1/25/07 mike3
4/18/07 ncapito
1/21/07 George Greene
1/22/07 Stephen Harris
1/22/07 |-|erc
1/29/07 Chris Smith
1/29/07 |-|erc
1/29/07 David Bernier
1/29/07 Chris Smith
1/23/07 LauLuna