# noncomputability

From: Mitchell J Porter (mjporter@U.Arizona.EDU)
Date: Wed Jul 25 2001 - 18:46:35 MDT

John Stick said

> Once you
> find a "new physics" phenomenon that is uncomputable, if you ever do,
> I will bet the uncomputability will be able to be manifested in a
> substrate employing only the old physics as well. Uncomputability is
> ultimately a mathematical phenomenon, not a phvsical one, and it will
> be independent of the details of brain chemstry or physics.

This doesn't make any sense. An example of a noncomputable function
would be HALT[TM,IN], defined as follows: it returns "1" if the
Turing machine TM presented with the input IN will eventually halt,
and "0" otherwise. There's no end of specific cases where it's easy
to figure out the answer, but there is no Turing machine which can
compute the function's value for all possible pairs of inputs.

The computational primitives of a Turing machine are a few
operations: read, write, move right, move left. One can imagine
adding the function HALT (in some form) as a new computational
primitive. This defines a new class of abstract computers,
capable of computing a much larger universe of functions (namely,
anything that can be expressed as a composite of Turing-computable
functions and "halting functions" for Turing machines). The
members of this new class are "oracles" of the first degree.
But if OR1 is a member of this class, then it turns out that
HALT[OR1,IN] is not computable for a first-degree oracle.
So you can define a second-order oracle which has HALT[OR1,IN]
as a new computational primitive. And so on.

If there is such a thing as "noncomputable physics", it means
that, say, the equations of motion involve noncomputable
functions. There would be processes which, over time,
transformed one set of quantitative physical properties into
another set, according to some noncomputable transformation.
Example: you have two groups of binary physical systems ('bits').
They spontaneously produce another binary entity, whose state
is HALT[TM,IN], where the first group of bits encodes a
Turing machine, and the second group of bits encodes an input
to that machine.

If there was such an interaction, you could use it to make
an oracle - to compute the values of functions that are
noncomputable for Turing machines - since it implements the
necessary new computational primitive. But if the rest of
physics involves Turing-computable processes, there's not
going to be any way to combine them to duplicate the
computational powers of this hypothetical new noncomputable
process.

This thread started with Emil Gilliam saying:

> [what if] noncomputability lies at the heart of qualia

and quoting Eliezer (http://sysopmind.com/archive-sl4/0103/0006.html):

> I do think there's a good possibility that qualia
> are noncomputable ... But I definitely deny that the noncomputability
> has anything whatsoever to do with either Godelization or reflection.

Emil seems to mean Turing-noncomputability, but Eliezer seems
to mean something else, because if it means anything, Godelization
means jumping out of the system to add a new computational
primitive (HALT[]) or a new axiom (an unprovable-but-true Godel
proposition). What I think Eliezer means is that qualia might
not be computations, or might not be spontaneously generated
by computations independent of substrate. Personally I think
that's a reasonable opinion, but it is a *separate question*
from the computability-or-otherwise of physics.

If I read him correctly, Eliezer's issue is a question of
ontological categories: what sort of thing *is* a quale
(singular of qualia)? Is it an "informational property" as
Chalmers would have it, possessed by any implementation of
a particular finite-state machine? Or is it a substrate-dependent
*dynamics*: what are the "equations of motion" of qualia?
Are they Turing-computable or not?

It is quite consistent to maintain that qualia are
substrate-dependent but "Turing-computable", meaning
that their dynamics could be simulated and predicted
by a Turing machine. If this is true then consciousness
can be simulated without actually being created. I think
this is the simplest position, on account of

(i) the very sparse evidence that human thought has a
Turing-noncomputable dynamics, and

(ii) the difficulties in maintaining that computational
states are defined by objective (user-independent) properties
of physical systems.

This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:37 MDT