Velocity Reviews > Java > The halting problem revisited

# The halting problem revisited

Screamin Lord Byron
Guest
Posts: n/a

 03-27-2011
On 26.03.2011 21:56, Dirk Bruere at NeoPax wrote:
> The Human brain is also subject to the Turing
> limitation (as far as is known)

If what you're saying is true, then how can the human brain prove things
like, say, Fermat's last theorem?

Screamin Lord Byron
Guest
Posts: n/a

 03-27-2011
On 27.03.2011 21:18, Patricia Shanahan wrote:
> On 3/27/2011 9:10 AM, Screamin Lord Byron wrote:
>> On 26.03.2011 21:56, Dirk Bruere at NeoPax wrote:
>>> The Human brain is also subject to the Turing
>>> limitation (as far as is known)

>>
>> If what you're saying is true, then how can the human brain prove things
>> like, say, Fermat's last theorem?

>
> How would you deduce inability to prove Fermat's last theorem from the
> Turing limitation?

There can not be an algorithmic proof of Fermat's last theorem because
of the halting problem. And yet, humans can produce the proof.
Therefore, human brain is not subject to Turing limitation.

Screamin Lord Byron
Guest
Posts: n/a

 03-27-2011
On 27.03.2011 22:30, Patricia Shanahan wrote:
> On 3/27/2011 1:19 PM, Screamin Lord Byron wrote:
>> On 27.03.2011 21:18, Patricia Shanahan wrote:
>>> On 3/27/2011 9:10 AM, Screamin Lord Byron wrote:
>>>> On 26.03.2011 21:56, Dirk Bruere at NeoPax wrote:
>>>>> The Human brain is also subject to the Turing
>>>>> limitation (as far as is known)
>>>>
>>>> If what you're saying is true, then how can the human brain prove
>>>> things
>>>> like, say, Fermat's last theorem?
>>>
>>> How would you deduce inability to prove Fermat's last theorem from the
>>> Turing limitation?

>>
>> There can not be an algorithmic proof of Fermat's last theorem because
>> of the halting problem....

>
> Why does the halting problem imply anything at all about the existence
> or otherwise of a proof for Fermat's last theorem?
> Can you give a proof, or point to one I can read?

Yes. Sir Roger Penrose's book "Emperor's New Mind". I have a copy which
is translated to my language, so I can't give you exact page numbers
where he talks about that specifically (should be within first 100
pages), but the book is absolutely worth a read in its entirety.

Screamin Lord Byron
Guest
Posts: n/a

 03-27-2011
On 27.03.2011 23:03, Screamin Lord Byron wrote:
> On 27.03.2011 22:30, Patricia Shanahan wrote:
>> On 3/27/2011 1:19 PM, Screamin Lord Byron wrote:
>>> On 27.03.2011 21:18, Patricia Shanahan wrote:
>>>> On 3/27/2011 9:10 AM, Screamin Lord Byron wrote:
>>>>> On 26.03.2011 21:56, Dirk Bruere at NeoPax wrote:
>>>>>> The Human brain is also subject to the Turing
>>>>>> limitation (as far as is known)
>>>>>
>>>>> If what you're saying is true, then how can the human brain prove
>>>>> things
>>>>> like, say, Fermat's last theorem?
>>>>
>>>> How would you deduce inability to prove Fermat's last theorem from the
>>>> Turing limitation?
>>>
>>> There can not be an algorithmic proof of Fermat's last theorem because
>>> of the halting problem....

>>
>> Why does the halting problem imply anything at all about the existence
>> or otherwise of a proof for Fermat's last theorem?
>> Can you give a proof, or point to one I can read?

>
> Yes. Sir Roger Penrose's book "Emperor's New Mind". I have a copy which
> is translated to my language, so I can't give you exact page numbers
> where he talks about that specifically (should be within first 100
> pages), but the book is absolutely worth a read in its entirety.

Just to be clear, in the time of writing of that book Fermat's last
theorem wasn't yet proven nor Penrose provides the proof. That was done
later of course.
http://en.wikipedia.org/wiki/Wiles&#39;_...s_Last_Theorem

In his book, Penrose argues that such problems cannot be solved
algorithmically.

Screamin Lord Byron
Guest
Posts: n/a

 03-27-2011
On 27.03.2011 23:18, Patricia Shanahan wrote:
> On 3/27/2011 2:03 PM, Screamin Lord Byron wrote:
>> On 27.03.2011 22:30, Patricia Shanahan wrote:
>>> On 3/27/2011 1:19 PM, Screamin Lord Byron wrote:
>>>> On 27.03.2011 21:18, Patricia Shanahan wrote:
>>>>> On 3/27/2011 9:10 AM, Screamin Lord Byron wrote:
>>>>>> On 26.03.2011 21:56, Dirk Bruere at NeoPax wrote:
>>>>>>> The Human brain is also subject to the Turing
>>>>>>> limitation (as far as is known)
>>>>>>
>>>>>> If what you're saying is true, then how can the human brain prove
>>>>>> things
>>>>>> like, say, Fermat's last theorem?
>>>>>
>>>>> How would you deduce inability to prove Fermat's last theorem from the
>>>>> Turing limitation?
>>>>
>>>> There can not be an algorithmic proof of Fermat's last theorem because
>>>> of the halting problem....
>>>
>>> Why does the halting problem imply anything at all about the existence
>>> or otherwise of a proof for Fermat's last theorem?
>>> Can you give a proof, or point to one I can read?

>>
>> Yes. Sir Roger Penrose's book "Emperor's New Mind". I have a copy which
>> is translated to my language, so I can't give you exact page numbers
>> where he talks about that specifically (should be within first 100
>> pages), but the book is absolutely worth a read in its entirety.
>>

>
> I don't have a copy, so that is not currently one I can read. Perhaps
> you can restate the proof in your own words, or give an on-line reference?

In fact I have. I didn't have much hope to find it online, but I got
lucky I guess.

http://bit.ly/gCPoot

<http://books.google.hr/books?id=oI0grArWHUMC&pg=PA75&lpg=PA75&dq=emperor' s+new+mind+hilbert+problem&source=bl&ots=04Ljj-YNVy&sig=GNJwD-YkfZ1R5u2oFHD2vjrEqns&hl=hr&ei=T6yPTYnyHIrysgbi7Y2 NCg&sa=X&oi=book_result&ct=result&resnum=1&ved=0CB gQ6AEwAA#v=onepage&q&f=false>

Lew
Guest
Posts: n/a

 03-28-2011
Dirk Bruere at NeoPax wrote:
> It is trivial to detect whether most small programs will do in a finite time.
> Otherwise nobody could ever read somebody else's code and spot halting/loop
> bugs. The Human brain is also subject to the Turing limitation (as far as is
> known)

Fortunately the human mind is not limited to the limitations of the human brain.

--
Lew
Honi soit qui mal y pense.

John B. Matthews
Guest
Posts: n/a

 03-28-2011
In article <(E-Mail Removed)> ,
Patricia Shanahan <(E-Mail Removed)> wrote:

> On 3/27/2011 2:03 PM, Screamin Lord Byron wrote:
> > On 27.03.2011 22:30, Patricia Shanahan wrote:
> >> On 3/27/2011 1:19 PM, Screamin Lord Byron wrote:
> >>> On 27.03.2011 21:18, Patricia Shanahan wrote:
> >>>> On 3/27/2011 9:10 AM, Screamin Lord Byron wrote:
> >>>>> On 26.03.2011 21:56, Dirk Bruere at NeoPax wrote:
> >>>>>> The Human brain is also subject to the Turing
> >>>>>> limitation (as far as is known)
> >>>>>
> >>>>> If what you're saying is true, then how can the human brain
> >>>>> prove things like, say, Fermat's last theorem?
> >>>>
> >>>> How would you deduce inability to prove Fermat's last theorem
> >>>> from the Turing limitation?
> >>>
> >>> There can not be an algorithmic proof of Fermat's last theorem
> >>> because of the halting problem....
> >>
> >> Why does the halting problem imply anything at all about the
> >> existence or otherwise of a proof for Fermat's last theorem? Can
> >> you give a proof, or point to one I can read?

> >
> > Yes. Sir Roger Penrose's book "Emperor's New Mind". I have a copy
> > which is translated to my language, so I can't give you exact page
> > numbers where he talks about that specifically (should be within
> > first 100 pages), but the book is absolutely worth a read in its
> > entirety.
> >

>
> I don't have a copy, so that is not currently one I can read. Perhaps
> you can restate the proof in your own words, or give an on-line
> reference?

Several related arguments, including Penrose's, are summarized here:

<http://en.wikipedia.org/wiki/Mechanism_(philosophy)#G.C3.B6delian_arguments>

--
John B. Matthews
trashgod at gmail dot com

javax.swing.JSnarker
Guest
Posts: n/a

 03-28-2011
On 27/03/2011 10:20 PM, Lew wrote:
> Dirk Bruere at NeoPax wrote:
>> It is trivial to detect whether most small programs will do in a
>> finite time.
>> Otherwise nobody could ever read somebody else's code and spot
>> halting/loop
>> bugs. The Human brain is also subject to the Turing limitation (as far
>> as is
>> known)

>
> Fortunately the human mind is not limited to the limitations of the
> human brain.

Non sequitur. In fact, self-contradicting. The human mind is implemented
on the human brain*. Your statement is analogous to saying that some
computer program you ran on your dual-core x86-64 machine was not
limited to the limitations of your dual-core x86-64 machine, or that if
you put a fancy enough GPS unit in your Chevy Tahoe you could drive it
from New York to Sydney, Australia in under two hours, regardless of the
Tahoe's engine speed, and without having to drive it onto a plane or a ship.

Obvious nonsense.

* And to forestall the inevitable objections from dualists, every single
faculty of the human mind has been found to be able to be specifically
impaired by particular brain injuries, including memory, face
recognition, conscious awareness, language (and particular subskills of
language), and more. If the brain was just the antenna by which some
external mind-stuff connected to pilot the body, it seems unlikely that
this would be the case. Indeed, other than specific low-level sensory or
motor impairments, and perhaps epilepsy, any sensible dualist theory
would predict a near-total absence of mental disorders resulting from
identifiable physical trauma or chemical states of the brain, or
correctable by same. But instead it's possible to get whacked upside the
head and become unable to *think certain thoughts* anymore.

Read "The Man Who Mistook His Wife For A Hat" and try to reconcile *any*
of it with *any* flavor of dualism. On the other hand, the broad
spectrum of often very quirky bug reports in there are pretty much
exactly what you'd expect if the mind was complex software that ran as
specialized daemons distributed over a complex computer-network inside
the skull, and then various parts of that network became "host unreachable".

I'll add that they've mostly already reverse engineered auditory
perception, have made big strides in reverse engineering visual
perception, and will probably have decompiled and begun to analyze the
very algorithms underpinning conscious awareness itself in another
decade or three. MP3 encoding is a lossy compression whose lossiness was
optimized partly based on understanding the algorithms used in the human
brain to process incoming sound data. With every passing year, that much
less of what goes on in there remains unexplained in terms of simple
mechanics, electrochemistry, and various algorithms, and there's no
reason to believe that process will stop short of explaining *all* of it
in such terms.

--
public final class JSnarker
extends JComponent
A JSnarker is an NNTP-aware component that asynchronously provides
snarky output when the Ego.needsPuncturing() event is fired in cljp.

Mike Schilling
Guest
Posts: n/a

 03-28-2011

"Patricia Shanahan" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) m...
> On 3/27/2011 8:26 PM, John B. Matthews wrote:
>> In article<7pGdnXRQeKUINBLQnZ2dnUVZ_omdnZ2d@earthlink .com>,
>> Patricia Shanahan<(E-Mail Removed)> wrote:
>>
>>> On 3/27/2011 2:03 PM, Screamin Lord Byron wrote:

> ...
>>>> Yes. Sir Roger Penrose's book "Emperor's New Mind". I have a copy
>>>> which is translated to my language, so I can't give you exact page
>>>> numbers where he talks about that specifically (should be within
>>>> first 100 pages), but the book is absolutely worth a read in its
>>>> entirety.
>>>>
>>>
>>> I don't have a copy, so that is not currently one I can read. Perhaps
>>> you can restate the proof in your own words, or give an on-line
>>> reference?

>>
>> Several related arguments, including Penrose's, are summarized here:
>>
>> <http://en.wikipedia.org/wiki/Mechanism_(philosophy)#G.C3.B6delian_arguments>
>>

>
> Thanks. I happen to agree with the view that human reasoning is not
> always consistent. It has evolved to produce decisions as needed, even
> if there is limited data, which puts completeness ahead of consistency.

In particular, I think, the human mind sees patterns everywhere, and is
ready to reason from them without knowing for sure whether they're real or
spurious. Ramanujan was well-known for deriving amazing results from this
kind of reasoning by analogy which other, sometimes lesser, mathematicians
would later prove rigorously.

Lawrence D'Oliveiro
Guest
Posts: n/a

 03-28-2011
In message <imp859\$n5i\$(E-Mail Removed)>, Mike Schilling wrote:

> In particular, I think, the human mind sees patterns everywhere, and is
> ready to reason from them without knowing for sure whether they're real or
> spurious.

And the part of the mind that believes in these patterns is different from
the part that finds out whether they’re spurious.

And so you have the odd situation of scientists who continue to believe in
religion, for example. Or Johnny Carson’s famed debunking of Uri Geller, the
effect of which on his popularity was ... zero.