mike3
Posts:
2,395
Registered:
12/8/04
|
|
Re: Halting problem totally unsolvable?
Posted:
Jan 25, 2007 11:17 PM
|
|
On Jan 21, 11:25 pm, "Proginoskes" <CCHeck...@gmail.com> wrote:
> Peter_Smith wrote:
> > Klueless wrote:
> > > "mike3" <mike4...@yahoo.com> wrote in messagenews:1169415261.556559.215860@l53g2000cwa.googlegroups.com...
> > > > Is the "halting problem" _totally_ unsolvable, ie. is there no
> > > > physically-possible machine that can decide it?
>
> > > The current answer is No. SEE:
> > > <http://en.wikipedia.org/wiki/Church-Turing_thesis>
> > > <http://en.wikipedia.org/wiki/Hypercomputation>
>
> > > I disagree with the other posters that say CPU's have become so fast,
> > > that the problem is now "moot". They are totally wrong about that.
>
> > Well, as you say, the issues about CPUs becoming faster is absolutely
> > irrelevant.
>
> > And as the hypercomputation entry says "At this stage, none of these
> > devices seem physically plausible. Thus, hypercomputers are likely to
> > remain as mathematical models." But "seem"/"likely" seem right. The
> > about Turing-beating physical possibilities isn't entirely foreclosed.
> > Which is all I, at any rate, meant by "moot".
> If you can solve the Halting Problem, then you can solve many
> mathematical problems, such as Goldbach's Conjecture, Fermat's Last
> Theorem, the Odd Perfect Number Theorem, etc etc etc.
>
> The problems above are known to be true for all "small N", but that
> doesn't rule out the possibility
>
> For instance, you could take the following procedure:
>
> n := 6
> Repeat
> For every i between 3 and n-3,
> if i and n-i are both prime, return YES.
> "Forever"
>
> This procedure, if it halts, shows that Goldbach's Conjecture is false.
> If it doesn't halt (if it runs forever), then Goldbach's Conjecture is
> true.
>
Holy cow!
n = 6. Then n-3 = 3. So i, "between" 3 and n-3 is " "between" 3 and 3,
or 3.
3 (i) and 3 (n-i = 6-3) are both prime, so HALT and thus GBC is FALSE!
Damn, that was easy.
I must have made a mistake somewhere, I doubt this stuff is so easy.
I high doubt it. I know I'm wrong. But where?
> Another example.
>
> Conjecture: For every integer n >= 2, 2^n - 3 is not divisible by n.
>
> This conjecture is actually false, but the smallest counterexample is
> 4,700,063,497.
>
> --- Christopher Heckman- Hide quoted text -- Show quoted text -
|
|
