>>>>> "Jeff" == Jeff Prideaux <JPRIDEAUX@GEMS.VCU.EDU> writes:
Jeff> I'd like to plug the new book by Roger Penrose, SHADOWS OF THE
Jeff> MIND. His thesis is that consciousness is of a
Jeff> non-computational nature... ie, it can't be done on a
Jeff> computer. He uses non- computable examples from the formal
Jeff> world (the halting problem, the tiling problem, the
Jeff> Diophantine equation solvability problem)
>If he's to be believed, then, the human mind is capable of solving the
>halting problem, when a computer cannot. I find no evidence to support
>that notion.
This is a reasonable conclusion for anyone who isn't familiar with the
work of Godel, Turing, and others...
The evidence (that the human mind is able to solve the halting problem whereas
a computer cannot) has been presented many times (for example in Penrose's books
THE EMPERORS NEW MIND, and in SHADOWS OF THE MIND. Turing and Godel origionally
showed this, Casti has written on it...and many others.
The argument goes (briefly) as follows. I am following the description
of the argument from Penrose's book SHADOWS OF THE MIND (pages 72-76)
Consider a particular turing machine that has n as its data input. The question
is "Does it ever halt?". Consider the case where that particular Turing machine
(Cq) operating on the data set n (Cq(n)) doesn't ever halt. We want to see if
an algorithmic proceedure (A) can tell us this (by itself halting).
In the above notation Cq stands for the qth Turing machine. Any particular
algorithm can be performed by a particular Turing machine. Cq can be viewed
as a universal Turing machine accepting q as its program...or you could view
it as your desktop computer running a particular program (q). The question is
can amother program (A), taking as input the program p and the data input n,
determine that the origional program q with input data n never stops.
That is.... If A(q,n) stops, then Cq(n) does not stop.
The main issue is whether we (as sentient beings) can determine that Cq(n)
does not halt, but A(q,n) can not. If we can, then it shows that we can do
something that an algorithm, or computation, cannot.
The proof involves an "reductio ad absurdum". Something is assumed, a
conradiction is shown, then the assumption is said to be false.
In this case the assumption is "If A(q,n) stops, then Cq(n) does not stop."
All we need to do is show a contradiction for one particular case for the
above assumption (in genreal) to be false.
Consider the case where q = n. Now we have
If A(n,n) stops, then Cn(n) does not stop.
Since A(n,n) just depends on one number n, we can find a particular Turing
Machine that perfoms this calculation. Call this Turing machine Ck.
A(n,n) = Ck(n)
Consider the case where n = k.
A(k,k) = Ck(k)
We now can say that
If Ck(k) stops, then Ck(k) does not stop.