# [FOM] The Lucas-Penrose Fallacy

Francis Davey fjmd1 at yahoo.co.uk
Thu Oct 12 15:45:26 EDT 2006

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