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 ]
 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 -

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