Toward a Science of Consciousness 1998

Stephen Harris mulcyber at
Fri Apr 24 17:56:48 EST 1998

modlin at wrote:

> It's not an "AI" idea.  It's one of those things that is basic to the
> notion of computing.  A guy called Church formalized it quite a while
> ago, but it is pretty obvious for discrete digital computing (once
> you've realized that no discrete architecture can transcend a Turing
> Machine), and more subtly obvious for all machines of any type.

Dennett maintains that 'Turing has proven- and this is probably
his greatest contribution- that his Universal Turing machine can
compute any function that any computer, with any architecture,
can compute'.

This is a common error in rendering the Church-Turing thesis.
A UTM can compute what is computable for any Turing machine.

Thesis M:"Whatever can be calculated by a machine (working on
finite data in accordance with a finite program of instructions)
is Turing-machine-computable.

Thesis M itself admits of two interpretations, according to 
whether the phrase 'can be calculated by a machine' is taken
in the narrow sense of 'can be calculated by a machine that
conforms to the physical laws(if not to the resource constants)
of the actual world', or in a wide sense that abstracts from the
issue of whether or not the notional machine in question could
exist in the real world. The narrow version of thesis M is an
empirical proposition whose truth-value is unknown. The wide
version of thesis M is known to be false. Various notional
machines have been described which can calculate functions
that are not Turing-machine-computable(for example, Abramson,
da Costa and Doria, Doyle, Hogarth, Pour-El and Richards,
Scarpellini, Siegelman and Sontag, Stannett, Stewart, Copeland
and Sylvan is a survey)."

So "no discrete architecture can transcend a Turing Machine".
I assume that this alludes to the 'narrow sense' above.
This is a stronger assertion not contained in the CT thesis.
You probably consider it an implication; but this implication
is not proven and does not refute architectural considerations.
I am not sure what "and more subtly obvious for all machines
of any type" means. If this is meant to apply to the 'wider
sense' above, there are counter-examples.


More information about the Neur-sci mailing list