[FOM] The Lucas-Penrose Fallacy

[Francis Davey]

laureano luna wrote:

> 
> 
> Any sound Turing machine is logically incapable to
> solve the halting problem when fed with its own code.
> But what how could we establish for a sound human the
> (corresponding) logical impossibility to solve the
> halting problem for some particular machine when faced
> to it, without assuming beforehand that he is a
> machine?
> 

I don't know much logic, so I'll focus on the computability aspect which 
is raised here -- but has been much less discussed on this thread.

Its not true to say that "any sound Turing machine is logically 
incapable to solve the halting problem when fed with its own code.". It 
is quite possible to code a machine, or class of machines, that, (1) 
halt; and (2) when fed with their own code output an indication that 
they halt.

More to the point, it is possible to produce a machine that (1) halts; 
(2) has as input a description of any machine and input; (3) output 
either 0, 1 or *; and only outputs 1 or 0 if the machines does or does 
not halt respectively; and (4) outputs 1 if fed itself plus any input.

What we know from computability theory is that such a machine will have 
to produce "*" some of the time -- it can't be a universal halting 
detecting machine.

I do not believe we know any way of algorithmically generating an input 
that will be guaranteed to produce a * for any input.

Certainly I doubt that we can, given such an almost universal machine, 
guarantee to generate a machine whose halting status we know and which 
it doesn't.

Now, this is a bit of a way from the Lucas-Penrose issue, which I 
confess I do not understand. I personally don't know how to see if 
mathematical statements are "true". I might believe that the godel 
sentence is true in the "intended model", but no-one has ever been able 
to explain exactly what they mean by the intended model, so I am far 
from sure about that. Maybe its a mystical ability I don't have or 
haven't appreciated (*).

However, I am much more sure that humans are unable, in general, to 
determine the halting statement of any machine and would be interested 
in any argument that they can.

Francis
(*) in other words - how do I know there aren't a non-standard number of 
hadrons in the universe?
Send instant messages to your online friends http://uk.messenger.yahoo.com