Original Posted 7 Mar 1998. Typo corrected 8 Mar 1998
Sequel 10 Mar 1998

Fascinating replies by Ilias Kastanas

CONTENTS:

 From: Nospam.Sloman@cs.bham.ac.uk (Aaron Sloman See text for reply address)
 From: A.Nospam@cs.bham.ac.uk (Aaron Sloman See text for reply address) (Reply to Draper)
 From: ikastan@alumni.caltech.edu (Ilias Kastanas) 11 March
 From: A.Nospam@cs.bham.ac.uk (Aaron Sloman See text for reply address) 16 March
 From: ikastan@alumni.caltech.edu (Ilias Kastanas) 19 March

Newsgroups: sci.logic,comp.ai.philosophy
References: <6cl2d5$j54$1@belzebul.imaginet.fr> <6dpu78$dti$1@hpns1.media.mit.edu>
From: Nospam.Sloman@cs.bham.ac.uk (Aaron Sloman See text for reply address)
Subject: Re: Non-computability

"Marvin Minsky" <minsky@media.mit.edu> writes:

> Date: Fri, 06 Mar 1998 17:41:33 +0000
> Organization: mit
>
>
> ----------
> In article <6dout0$bbl@gap.cco.caltech.edu>, ikastan@alumni.caltech.edu
> (Ilias Kastanas) wrote:
>
> Someone said---
>
> >>Then you are completely wrong.  There is clearly a difference in
> >>principle between a parallel and a serial computer.  A parallel computer
> >>is time-dependent.  Its behaviour will depend on the speeds at which its
> >>underlying processors operate, because that will determine when
> >>communciation occurs, and so what is communicated.  This is not the case
> >>for a serial computer.
>
> Ilias said:  So there are additional inputs, the "speeds".
>
> I completely agree with Ilias. It has nothing to do with the computers at
> all, but with an 'oracle' that has been overlooked.   As with GIGO we have
> NINO, by replacing 'Garbage" with 'Non-computability'.  And presumably
> garbage is precisely what you get, because over any finite interval--even if
> it is the seven billion years during which the inner Solar Syatem is
> expected to be stable--there's no way to distinguish the behaviors of a
> 'truly random" TM from a pseudorandom one.

It's perhaps worth noting that if we consider infinite sequences of
zeros and ones there are uncountably many of them whereas there are
only countably many possible turing machines (because the
specification of any turing machine can be expressed in a finite
program for a universal turing machine, and the (infinite) set of
such finite descriptions must be countable.

Thus if you have a couple of unsynchronised Turing machines one
generating an infinite sequence of 1s and the other an infinite sequence
of 0s, and their speeds vary in an appropriate way, they could, if left
to run forever (requiring an unbounded supply of tape extensions), and
if the physical properties of the universe don't rule this out (see
below), produce a non computable sequence of 0s and 1s.

I.e. it could be the case that for the kth Turing machine Tk in a
standard enumeration the sequence will eventually diverge from the
sequence computed by Tk. So in some sense a pair of unsynchronised
turing machines can produce (infinite) non-computable output.

If the physical universe is computable (as Minsky claims), then that's
impossible.

However, suppose such a non-turing equivalent machine (NTEM) is
possible:

(a) Then, as Minsky notes above, over any finite time interval the
observed behaviour produced by the NTEM will be *indistinguishable*
from the outputs of infinitely many different Turing machines. (i.e.
whatever sequence of N 0s and 1s the NTEM produces in time interval
T, if T is finite, then N will be finite, and there are infinitely
many ways of programming a turing machine to produce a specified
finite sequence followed by something different, e.g. different
numbers of 1s followed by infinitely many 0s.)

(b) Can there possibly be something interesting about a
non-computable infinite sequence of 1s and 0s produced by NTEM?

Obviously, infinite non-computable sequences may have interestingly
different initial (finite) subsequences, but all of those interesting
initial segments will also be found in computable sequences (as
indicated in (a) and in Minsky's comment).

Can a non-computable infinite sequence have any interesting
feature NOT found in any computable sequence?

Could there be mathematically interesting transfinite differences
between different non-computable sequences? Or do they all
correspond to something computable plus a lot of pure garbage, as
suggested by Minsky's comment:

> garbage is precisely what you get

I have no reason to think he's wrong, but I am wondering how one
could be sure there's nothing of any interest.

This would require some clear notion of what "interesting" could
cover. I am not sure I have a sufficiently well defined concept to
rule out the possibility of some relevant mathematical theory about
interestingly different (and therefore interesting) classes of
non-computable sequences.

I ask only out of curiosity, not because I think anything relevant
follows for debates about strong AI. It could simply point to an
interesting branch of mathematics (some subset of transfinite set
theory perhaps?)

Here's a first draft attempt to characterise some possible answers to
question (b):

Could different non-computable sequences be shown to provide models
for interestingly different sets of axioms?

Could non-computable infinite sequences have anything to do with
interestingly different non-standard models for axioms for
arithmetic, for instance?

E.g. if you take a standard undecidable axiomatic theory for arithmetic
AT which has various different consistent possible extensions, could
there be interestingly different extensions AT', AT'', AT''',
corresponding to (modelled by) different non-computable sequences?

I don't think positive answers to my question (b) could support Penrose
and others who wish to claim that brains have non-computable
capabilities, since I can't see how being a normal human being, or even
being a human mathematician, could require the ability to generate a
non-computable infinite sequence of symbols, since none of us lives
forever, and certainly our brains don't.

Moreover, just because there are interesting differences between
different non-computable sequences it doesn't follow that those
differences cannot be expressed in some finite set of symbols. E.g. they
may satisfy (or provide models for) different finite sets of axioms.

Why?

It's easy to write down a finite set of axioms for which only infinite
models are possible (e.g. Peano's axioms). Using diagonalisation and a
sufficiently expressive logic it should not be hard to write down a set
of axioms characterising a non-computable sequence, e.g. by specifying a
specific enumeration of the computable sequences, and defining a
non-computable one which is got from that enumeration by flipping the
kth bit in the kth sequence. (Just translate all that into (second
order?) predicate calculus....)

Moreover it's pretty obvious that using different such axioms we can
specify different non-computable sequences. So one interpretation of my
question (b) is whether there are "interestingly" different sets of such
axioms?

E.g. suppose that instead of always flipping only the kth bit of the kth
sequence you flip bit k+f(k) of the kth sequence, where f(k) is a
monotonically nondecreasing function of k? That will also generate a
non-computable sequence, but a new one.

If there are interesting differences between different non-computable
sequences then perhaps in some sense it isn't all garbage?

Or have I missed something?

Is this a question anyone has addressed? Perhaps I need to read
Chaitin's work on this?

When Minsky writes

> garbage is precisely what you get

he apparently justifies this on the basis of point (a). But I don't
find it obvious that it follows from (a) that every such sequence is
pure garbage. Maybe there are interesting differences between
different subsets of non-computable sequences?

Incidentally, this message is a demonstration that a finite brain can
have thoughts about non-computable infinite sequences. I don't know how
I do it: maybe I am implicitly manipulating something like the axioms
which characterise these sequences.

Of course it doesn't follow that any brain can actually produce any
non-computable sequence. And it doesn't follow that such thoughts could
not occur in a system implemented in a Turing machine.

If I can reason about things I can't generate, so perhaps can a robot
implemented in a Turing machine.

Minsky commented:
> Generally, I don't understand why theorists keep 'rediscovering' this
> difference between a parallem computer in a non-computable environment and a
> serial TM.

Perhaps they misconstrue the significance of the discovery, either
because they have not grasped point (a) or because they THINK they
have an answer to my question in (b).

> My view is that this universe is completely computable in the
> first place,

Is this just a hunch, or a consequence of some feature of current
physical theory?

I think Chris Fields once tried to produce a proof that all physically
producible sequences must be computable, in a paper in Journal of
Experimental and Theoretical AI, circa 1989, but I didn't know enough
theoretical physics and mathematics to be able to assess the proof. (I
think his proof implicitly presupposed that there was a Hamiltonian
defining state transitions for the whole universe, or at least for any
bounded subset.)

Aaron

=======================================================================
Posted 10 Mar 1998
Newsgroups: sci.logic,comp.ai.philosophy
References: <6cl2d5$j54$1@belzebul.imaginet.fr> <6dpu78$dti$1@hpns1.media.mit.edu> <6ds3vg$vul$1@soapbox.cs.bham.ac.uk> <3504DA74.5CFB1B4C@concentric.net>
From: A.Nospam@cs.bham.ac.uk (Aaron Sloman See text for reply address) (Reply to Draper)
Subject: Re: Non-computability

Patrick Draper <pdrap@concentric.net> writes:

> Date: Tue, 10 Mar 1998 01:15:16 -0500
> Organization: I speak for nobody but myself.
>
[Aaron Sloman]
> > I.e. it could be the case that for the kth Turing machine Tk in a
> > standard enumeration the sequence will eventually diverge from the
> > sequence computed by Tk. So in some sense a pair of unsynchronised
> > turing machines can produce (infinite) non-computable output.
> >
> > If the physical universe is computable (as Minsky claims), then that's
> > impossible.
>
[Patrick Draper]
> The flaw that I can see with your argument is that it does not match
> observation of the physical universe.
>
> The actual universe in bounded, and a turing machine will indeed stop
> because it reaches the end of the tape.

Whether the physical universe is bounded or not (on which I have no
information) the particular scenario I put forward can easily be
modified to consider two machines one repeatedly writing a 1 on the
end of its tape and the other repeatedly writing a 0, with a robot
assistant which, from time to time, cuts out a chunk of previously
used tape, erases the marks on it, and sticks it on the end beyond
the writing head.

In fact, you don't need two turing machines with tapes, etc. just
two unsyncrhonised machines each flashing a light to make the point
about non-computable sequences being *logically* possible if the
machines are not synchronised.

Of course, any physical machine if left alone will eventually rust,
wear out, be demolished by an exploding sun, run out of energy, or
whatever. So more work is needed to set up a scenario to cope with
these things.

It's not obvious to me that it is IMPOSSIBLE for any physical
scenario to produce an unending sequence of discrete signals of some
kind. If it IS impossible then every discrete physical sequence is
finite, and therefore computable in an uninteresting way.

There might still be non-computable examples of continuous
variation, but I wasn't concerned with that in the discussion of
unsynchronised parallel discrete (Turing) machines.

And of course questions of physical realisability are separate from
the questions I went on to raise about whether there can be any
interesting classes of non-computable infinite sequences. In
particular it is not obvious to me that they all have to be pure
garbage apart from some finite (or computable) subset.

E.g. what happens if you merge (interleave) a computable sequence
with a non-computable one?

Aaron
===
=======================================================================

From article: 50703 in comp.ai.philosophy
Newsgroups: sci.logic,comp.ai.philosophy
Message-ID: <6e5nin$s1d@gap.cco.caltech.edu>
References: <6cl2d5$j54$1@belzebul.imaginet.fr> <6dpu78$dti$1@hpns1.media.mit.edu> <6ds3vg$vul$1@soapbox.cs.bham.ac.uk>
Xref: bhamcs sci.logic:23649 comp.ai.philosophy:50703
Date: 11 Mar 1998 10:04:07 GMT
Organization: Caltech Alumni Association
Subject: Re: Non-computability
From: ikastan@alumni.caltech.edu (Ilias Kastanas) 11 March

In article <6ds3vg$vul$1@soapbox.cs.bham.ac.uk>,
Aaron Sloman See text for reply address <Nospam.Sloman@cs.bham.ac.uk> wrote:
>"Marvin Minsky" <minsky@media.mit.edu> writes:
>
>> Date: Fri, 06 Mar 1998 17:41:33 +0000
>> Organization: mit
>>
>>
>> ----------
>> In article <6dout0$bbl@gap.cco.caltech.edu>, ikastan@alumni.caltech.edu
>> (Ilias Kastanas) wrote:
>>
>> Someone said---
>>
>> >>Then you are completely wrong.  There is clearly a difference in
>> >>principle between a parallel and a serial computer.  A parallel computer
>> >>is time-dependent.  Its behaviour will depend on the speeds at which its
>> >>underlying processors operate, because that will determine when
>> >>communciation occurs, and so what is communicated.  This is not the case
>> >>for a serial computer.
>>
>> Ilias said:  So there are additional inputs, the "speeds".
>>
>> I completely agree with Ilias. It has nothing to do with the computers at
>> all, but with an 'oracle' that has been overlooked.   As with GIGO we have
>> NINO, by replacing 'Garbage" with 'Non-computability'.  And presumably
>> garbage is precisely what you get, because over any finite interval--even if
>> it is the seven billion years during which the inner Solar Syatem is
>> expected to be stable--there's no way to distinguish the behaviors of a
>> 'truly random" TM from a pseudorandom one.

>It's perhaps worth noting that if we consider infinite sequences of
>zeros and ones there are uncountably many of them whereas there are
>only countably many possible turing machines (because the
>specification of any turing machine can be expressed in a finite
>program for a university turning machine, and the (infinite) set of
>such finite descriptions must be countable.
>
>Thus if you have a couple of unsynchronised Turing machines one
>generating an infinite sequence of 1s and the other an infinite sequence
>of 0s, and their speeds vary in an appropriate way, they could, if left
>to run forever (requiring an unbounded supply of tape extensions), and
>if the physical properties of the universe don't rule this out (see
>below), produce a non computable sequence of 0s and 1s.



    Yes... reflecting the time lengths assigned to steps of the TMs
(the latter being, after all, just finite tables of quintuples).  That is,
an oracle.

    The physical universe does not enter.   No one has ever "observed"
a real.


    (Below, I'll say "real" for members of  R, or w^w, or 2^w).



>I.e. it could be the case that for the kth Turing machine Tk in a
>standard enumeration the sequence will eventually diverge from the
>sequence computed by Tk. So in some sense a pair of unsynchronised
>turing machines can produce (infinite) non-computable output.
>
>If the physical universe is computable (as Minsky claims), then that's
>impossible.
>
>However, suppose such a non-turing equivalent machine (NTEM) is
>possible:
>
>(a) Then, as Minsky notes above, over any finite time interval the
>observed behaviour produced by the NTEM will be *indistinguishable*
>from the outputs of infinitely many different Turing machines. (i.e.
>whatever sequence of N 0s and 1s the NTEM produces in time interval
>T, if T is finite, then N will be finite, and there are infinitely
>many ways of programming a turing machine to produce a specified
>finite sequence followed by something different, e.g. different
>numbers of 1s followed by infinitely many 0s.)
>
>(b) Can there possibly be something interesting about a
>non-computable infinite sequence of 1s and 0s produced by NTEM?
>
>Obviously, infinite non-computable sequences may have interestingly
>different initial (finite) subsequences, but all of those interesting
>initial segments will also be found in computable sequences (as
>indicated in (a) and in Minsky's comment).



    And conversely.   So one studies e.g. (infinite) recursive "appro-
ximations"...  No initial segment has any bearing on computability.



>Can a non-computable infinite sequence have any interesting
>feature NOT found in any computable sequence?
>
>Could there be mathematically interesting transfinite differences
>between different non-computable sequences?



    The reals have an intricate structure under Turing reducibility  x <= y
(x computable with oracle y), its equivalence classes being "degrees of unsol-
vability".   E.g.  0 = computable reals (recursive, Delta-0-1),  0' = Halting
problem (universal r.e. (Sigma-0-1) real)...  and continuum many others.

    More coarsely, there are Sigma-0-n reals (arithmetical), n in  w;
then, n on to w_1-CK, the hyperarithmetical ones (Delta-1-1);  then Sigma-1-n
(analytical);...  Sigma-m-n ...      [Pi = ~Sigma,  Delta = both Sigma & Pi]



>I ask only out of curiosity, not because I think anything relevant
>follows for debates about strong AI. It could simply point to an
>interesting branch of mathematics (some subset of transfinite set
>theory perhaps?)



    Descriptive Set Theory, lightface.  (Boldface: Sigma-0-1 = open sets
of reals,  Delta-1-1 = Borel sets,  Pi-1-1 = Co-analytic sets ...)



>Here's a first draft attempt to characterise some possible answers to
>question (b):
>
>Could different non-computable sequences be shown to provide models
>for interestingly different sets of axioms?



    Yes... for all of them!   Any set of axioms (in any countable language)
that has a model at all has a countable model -- hence encodable by a real.


>Could non-computable infinite sequences have anything to do with
>interestingly different non-standard models for axioms for
>arithmetic, for instance?



    They do; in fact, they are unavoidable.   A (countable) non-standard
model of PA, M' say, has universe  w + Q copies of Z.   Implement it by the
integers ("W"), ordered in that order type.   Then the +  operation of M' is
a ternary relation on W; same for *.

    By a theorem of Tennenbaum, neither + nor * can be recursive.  So we
do need a non-computable real to describe an M'.   And if  M' is moreover a
non-standard model of _true_ arithmetic, neither + or * can be arithmetical
at all.



>E.g. if you take a standard undecidable axiomatic theory for arithmetic
>AT which has various different consistent possible extensions, could
>there be interestingly different extensions AT', AT'', AT''',
>corresponding to (modelled by) different non-computable sequences?



    Well, PA has continuum many (non-isomorphic complete consistent)
extensions, all uncomputable (as, uh, somebody proved).   Such extent of
variety is interesting!...



>I don't think positive answers to my question (b) could support Penrose
>and others who wish to claim that brains have non-computable
>capabilities, since I can't see how being a normal human being, or even
>being a human mathematician, could require the ability to generate a
>non-computable infinite sequence of symbols, since none of us lives
>forever, and certainly our brains don't.



    So we cannot actually generate _any_ infinite sequence, computable
or not.   But we can describe them and reason about them.


>Moreover, just because there are interesting differences between
>different non-computable sequences it doesn't follow that those
>differences cannot be expressed in some finite set of symbols. E.g. they
>may satisfy (or provide models for) different finite sets of axioms.

>Why?
>
>It's easy to write down a finite set of axioms for which only infinite
>models are possible (e.g. Peano's axioms). Using diagonalisation and a


    True.  (Even though PA itself is infinite -- an induction axiom
for every formula).


>sufficiently expressive logic it should not be hard to write down a set
>of axioms characterising a non-computable sequence, e.g. by specifying a
>specific enumeration of the computable sequences, and defining a
>non-computable one which is got from that enumeration by flipping the
>kth bit in the kth sequence. (Just translate all that into (second
>order?) predicate calculus....)



    That's how one proves each Sigma-0-n level has "new" elements...
And 1st-order is enough.


>Incidentally, this message is a demonstration that a finite brain can
>have thoughts about non-computable infinite sequences. I don't know how
>I do it: maybe I am implicitly manipulating something like the axioms
>which characterise these sequences.


    Hmm, "characterise" isn't the word, as 1st-order axioms seldom do
(c.f. all those non-standard models!).   But we have a grasp of  w  (or  R,
or  V...) -- and that is where the axioms we use come from in the first
place.


>Of course it doesn't follow that any brain can actually produce any
>non-computable sequence. And it doesn't follow that such thoughts could
>not occur in a system implemented in a Turing machine.
>
>If I can reason about things I can't generate, so perhaps can a robot
>implemented in a Turing machine.



    Certainly so;  a TM can enumerate all formal deductions  S |- phi.
The question is, which S "carry weight" regarding  w, R, V...?   We focus
on S that are finite subsets of -- what?   PA?  KP?  ZFC?  ZFC + X ?



                        Ilias

From A.Sloman March 16 1998
Newsgroups: sci.logic,comp.ai.philosophy
References: <6cl2d5$j54$1@belzebul.imaginet.fr> <6dpu78$dti$1@hpns1.media.mit.edu> <6ds3vg$vul$1@soapbox.cs.bham.ac.uk> <6e5nin$s1d@gap.cco.caltech.edu>
From: A.Nospam@cs.bham.ac.uk (Aaron Sloman See text for reply address) 16 March
Subject: Re: Non-computability

ikastan@alumni.caltech.edu (Ilias Kastanas) gave a detailed and very
patient tutorial reply to my questions for which many thanks.

Apologies for a delayed resonse. Five days seems to be a long time in
netland.

Ilias wrote
> Date: 11 Mar 1998 10:04:07 GMT
> Organization: Caltech Alumni Association

[AS]
> >Obviously, infinite non-computable sequences may have interestingly
> >different initial (finite) subsequences, but all of those interesting
> >initial segments will also be found in computable sequences (as
> >indicated in (a) and in Minsky's comment).
>
[IK]
>   And conversely.   So one studies e.g. (infinite) recursive "appro-
> ximations"...  No initial segment has any bearing on computability.

Yes. I was merely trying to be precise. The statement that any
non-computable sequence is "garbage" is not a precise statement. I
am not suggesting that Minsky intended his comment (to which I was
reacting) as a precise statement, but some readers might.

In fact, in the light of your comments I suspect he is wrong: in any
reasonable sense of "garbage" there are going to be many sets of
non-computable sequences which are not garbage, but quite interesting,
from a mathematical point of view: e.g. if I understand you correctly,
this will be true of various sets of non-computable reals.

This in itself does not support any attack on AI, however.

[AS]
> >Can a non-computable infinite sequence have any interesting
> >feature NOT found in any computable sequence?
> >
> >Could there be mathematically interesting transfinite differences
> >between different non-computable sequences?

[IK]
>   The reals have an intricate structure under Turing reducibility  x <= y
> (x computable with oracle y), its equivalence classes being "degrees of unsol-
> vability".   E.g.  0 = computable reals (recursive, Delta-0-1),  0' = Halting
> problem (universal r.e. (Sigma-0-1) real)...  and continuum many others.
>
>   More coarsely, there are Sigma-0-n reals (arithmetical), n in  w;
> then, n on to w_1-CK, the hyperarithmetical ones (Delta-1-1);  then Sigma-1-n
> (analytical);...  Sigma-m-n ...      [Pi = ~Sigma,  Delta = both Sigma & Pi]
> ....

Unfortunately my technical/mathematical knowledge is not up to the
details of the answers Ilias gives. Maybe it's time for me to go
back to being a maths student.

However, I think I get the gist: the class of non-computable sequences
(which corresponds to the class of non-computable reals) does include
some interestingly different sub-classes, and these are well known to
(some) mathematicians.

So my intuitive untutored hunch was correct.

A question for AI theorists of the future would be to explain how
someone with limited mathematical knowledge could have a hunch like
that. This is part of a general problem which interests me: what kind of
architecture in an information processing system provides a basis for a
grasp of various mathematical concepts which (as Immanuel Kant pointed
out a long time ago) could not possibly be abstracted from experience of
examples, since no examples are ever experienced. E.g. euclidean points
and lines, the totality of natural numbers, the continuum.

(Maybe some people would say that we do experience a continuum both in
spatial perception and in our sense of time. But that's a topic for
another occasion. NB if we do it, then presumably suitably designed
robots could too: I am not attacking AI.)

I return to the question about architecture below.

[AS]
> >Could different non-computable sequences be shown to provide models
> >for interestingly different sets of axioms?

[IK]
>   Yes... for all of them!   Any set of axioms (in any countable language)
> that has a model at all has a countable model -- hence encodable by a real.

Surely it doesn't follow from this alone that some of those sets of
axioms are interestingly different? I guess it depends what
"interesting" means, and this may be as hard to define in a
non-question-begging way as "computable"!

Anyhow, what you are saying is that finite sets of axioms can be used to
"specify" various non-computable sequences. Finite sets of axioms can be
expressed in Turing machines. Therefore in some sense Turing machines
can be used to "specify" non-computable sequences. They merely can't
generate them. (I.e. they can do the job intensionally not
extensionally).

That raises the question: what could a TM do with such a set of axioms?

Well maybe it could deduce some additional interesting facts about the
non-computable sequence (i.e. the real) which they specify (or the set
of reals if they have more than one model).

E.g., to take a trivial example, suppose we specify a sequence S1 as
being the first one generated by diagonalisation given an enumeration of
all the computable sequences. Now suppose we find a computable sequence,
e.g. the digits in the binary representation of PI, and interleave those
with the digits of S1 to provde S2. S2 is not computable (I suspect,
since if it were, the generating algorithm could be combined with that
for PI to produce an algorithm to generate S1).

S2 is just a trivial example of a non-computable sequence which can be
shown by simple reasoning to have an interesting property.

I presume the mathematical theories Ilias refers to would include far
more interesting cases of ways of specifying and reasoning about
non-computable reals. And there's no reason why a turing machine should
not be able to replicate that reasoning if it merely involves finite
manipulations of finite sets of axioms.

... Skipping bits some of which I didn't grasp fully ...

[AS]
> >I don't think positive answers to my question (b) could support Penrose
> >and others ....

[IK]
>   So we cannot actually generate _any_ infinite sequence, computable
> or not.   But we can describe them and reason about them.

And so, presumably could a suitably programmed turing machine.

Of course, Penrose might claim that it would not ``understand'' what it
was doing. But in some deep sense it's not clear to what extent we
understand either .....

This is the basis of some disputes in mathematics, e.g. between
intuitionists and others.

It is often the case that when we think we attach a clear semantics to
some concept it turns out later that it was very unclear. Historical
examples are "continuity", "simultaneity", "atom", "energy", and recent
examples are "consciousness", "emotion", "intelligence",
"representation", "semantics" etc.


[AS]
> >It's easy to write down a finite set of axioms for which only infinite
> >models are possible (e.g. Peano's axioms). Using diagonalisation and a
>
[IK]
>   True.  (Even though PA itself is infinite -- an induction axiom
> for every formula).

But presumably this infinite set of axioms is not needed in a higher
order logic. Don't most students first encounter PA with a single
high order induction axiom? Isn't that how Peano thought about it?

[AS]
> >Incidentally, this message is a demonstration that a finite brain can
> >have thoughts about non-computable infinite sequences. I don't know how
> >I do it: maybe I am implicitly manipulating something like the axioms
> >which characterise these sequences.
>
[IK]
>   Hmm, "characterise" isn't the word, as 1st-order axioms seldom do
> (c.f. all those non-standard models!).

OK. I was not using the word in any precise mathematical sense. In
fact it's an interesting research question in what sense the
(presumably finite) structures in brains are capable of
characterising whatever it is that we are thinking about when we
think about transfinite sets.

I've never met a brain scientist interested in this! They'd rather study
perception, emotions, or even the truly muddy, multiply ambiguous,
notion of consciousness ....

> But we have a grasp of  w  (or  R,
> or  V...) -- and that is where the axioms we use come from in the first
> place.

I don't know what V is.

However the question I am approaching in a backwards way is *how* we
have a grasp of w. If you just start from that as a given then
that's a problem for a psychology of mathematics, or a theory of
requirements for a mathematical brain.

How does a child turn into a mathematician? What sort of architecture
can support that kind of development?

I suspect that possibility is a consequence of having deliberative
capabilities (e.g. planning mechanisms) together with self-monitoring
mechanisms, both of which evolved to meet quite different requirements
(planning enables you to avoid disastrous action sequences,
self-monitoring enables you to improve your planning capabilities, etc.
etc.)

Contrast that sort of explanation with the explanation offered in
another thread, that mathematical ability may have been selected for by
the need to impress mates seeking "interesting" partners. This already
presupposes the mechanisms: it doesn't say anything about what they are
or how they could be derived from pre-existing mechanisms mechanisms.
However mate selection could be part of an explanation of how
mathematical abilities were enhanced or become more wide-spread than
their practical relevance would explain.

Think of all those long nights without lamps, books, television etc. and
only lots of stars to watch. Oliver Selfridge suggested this had a
powerful effect on human development, in a talk I heard him give about
20 years ago.)


[AS]
> >Of course it doesn't follow that any brain can actually produce any
> >non-computable sequence. And it doesn't follow that such thoughts could
> >not occur in a system implemented in a Turing machine.
> >
> >If I can reason about things I can't generate, so perhaps can a robot
> >implemented in a Turing machine.

[IK]
>   Certainly so;  a TM can enumerate all formal deductions  S |- phi.
> The question is, which S "carry weight" regarding  w, R, V...?   We focus
> on S that are finite subsets of -- what?   PA?  KP?  ZFC?  ZFC + X ?

Maybe one day you can write a nice tutorial on all that and post it?

Aaron


From article: 51007 in comp.ai.philosophy
Newsgroups: sci.logic,comp.ai.philosophy
Message-ID: <6eqoev$dco@gap.cco.caltech.edu>
References: <6cl2d5$j54$1@belzebul.imaginet.fr> <6ds3vg$vul$1@soapbox.cs.bham.ac.uk> <6e5nin$s1d@gap.cco.caltech.edu> <6ei5mf$5j2$1@soapbox.cs.bham.ac.uk>
Date: 19 Mar 1998 09:27:59 GMT
Organization: Caltech Alumni Association
Subject: Re: Non-computability
From: ikastan@alumni.caltech.edu (Ilias Kastanas) 19 March

In article <6ei5mf$5j2$1@soapbox.cs.bham.ac.uk>,
Aaron Sloman See text for reply address <A.Nospam@cs.bham.ac.uk> wrote:
>ikastan@alumni.caltech.edu (Ilias Kastanas) gave a detailed and very
>patient tutorial reply to my questions for which many thanks.


    You are welcome!

>Apologies for a delayed resonse. Five days seems to be a long time in
>netland.
>
>Ilias wrote
>> Date: 11 Mar 1998 10:04:07 GMT
>> Organization: Caltech Alumni Association
>
>[AS]
>> >Obviously, infinite non-computable sequences may have interestingly
>> >different initial (finite) subsequences, but all of those interesting
>> >initial segments will also be found in computable sequences (as
>> >indicated in (a) and in Minsky's comment).
>>
>[IK]
>>   And conversely.   So one studies e.g. (infinite) recursive "appro-
>> ximations"...  No initial segment has any bearing on computability.
>
>Yes. I was merely trying to be precise. The statement that any
>non-computable sequence is "garbage" is not a precise statement. I
>am not suggesting that Minsky intended his comment (to which I was
>reacting) as a precise statement, but some readers might.
>
>In fact, in the light of your comments I suspect he is wrong: in any
>reasonable sense of "garbage" there are going to be many sets of
>non-computable sequences which are not garbage, but quite interesting,
>from a mathematical point of view:



    I don't think he is wrong; I think he is addressing a different
context (e.g. (non)-verifiability of something "physical" being recursive,
etc.).   To be sure, he does know the mathematical results!   After all, what
I myself have learned comes from many sources, one of them _his_ book!
("Computation: Finite and Infinite Machines")



>from a mathematical point of view: e.g. if I understand you correctly,
>this will be true of various sets of non-computable reals.



    Yes.   I wrote mostly about reals, but the theory applies to sets
of reals too.   E.g. sets that are Delta-1-1 -in-an-oracle  are exactly the
(classical) Borel sets.



>This in itself does not support any attack on AI, however.



    And in fact, neither attacking nor defending it was ever on my mind.


>[AS]
>> >Can a non-computable infinite sequence have any interesting
>> >feature NOT found in any computable sequence?
>> >
>> >Could there be mathematically interesting transfinite differences
>> >between different non-computable sequences?
>
>[IK]
>>   The reals have an intricate structure under Turing reducibility  x <= y
> (x computable with oracle y), its equivalence classes being "degrees of unsol-
>> vability".   E.g.  0 = computable reals (recursive, Delta-0-1),  0' = Halting
>> problem (universal r.e. (Sigma-0-1) real)...  and continuum many others.
>>
>>   More coarsely, there are Sigma-0-n reals (arithmetical), n in  w;
>> then, n on to w_1-CK, the hyperarithmetical ones (Delta-1-1);  then Sigma-1-n
>> (analytical);...  Sigma-m-n ...      [Pi = ~Sigma,  Delta = both Sigma & Pi]
>> ....
>
>Unfortunately my technical/mathematical knowledge is not up to the
>details of the answers Ilias gives. Maybe it's time for me to go
>back to being a maths student.



    Quick signposts: the arithmetical levels roughly correspond to  0,
0', 0'' (= Halting problem of halting problems), 0''', ...   The hyp reals
(Delta-1-1) arise by "recursively coded" sequences of (countable) unions,
intersections and complement operations.

    Going higher, a "complete" (hardest) Pi-1-1 set is Kleene's O.

       [ A linear ordering of  w  is a set of pairs, and hence a set
of integers (via some fixed, simple enumeration of  w x w).   So "recursive"
makes sense for l.o.'s.  Now a recursive set has code j if the j-th TM computes
the set; we can consider the codes of said l.o.'s.   O  =  codes of the l.o.'s
that are _wellorderings_ of  w  (no infinite descending R-chains) ].

    More below.



>However, I think I get the gist: the class of non-computable sequences
>(which corresponds to the class of non-computable reals) does include
>some interestingly different sub-classes, and these are well known to
>(some) mathematicians.
>
>So my intuitive untutored hunch was correct.
>
>A question for AI theorists of the future would be to explain how
>someone with limited mathematical knowledge could have a hunch like
>that. This is part of a general problem which interests me: what kind of
>architecture in an information processing system provides a basis for a
>grasp of various mathematical concepts which (as Immanuel Kant pointed
>out a long time ago) could not possibly be abstracted from experience of
>examples, since no examples are ever experienced. E.g. euclidean points
>and lines, the totality of natural numbers, the continuum.


    A slow process, cumulative over generations.


>(Maybe some people would say that we do experience a continuum both in
>spatial perception and in our sense of time. But that's a topic for
>another occasion. NB if we do it, then presumably suitably designed
>robots could too: I am not attacking AI.)


    We also hear a heartbeat, very early on;  then come distinctions,
I/others, presence/absence...


>[AS]
>> >Could different non-computable sequences be shown to provide models
>> >for interestingly different sets of axioms?
>
>[IK]
>>   Yes... for all of them!   Any set of axioms (in any countable language)
>> that has a model at all has a countable model -- hence encodable by a real.
>
>Surely it doesn't follow from this alone that some of those sets of
>axioms are interestingly different? I guess it depends what
>"interesting" means, and this may be as hard to define in a
>non-question-begging way as "computable"!



    Agreed.  I meant it the other way round;  all differences, inte-
resting or not, reflect to models/reals.

    
>Anyhow, what you are saying is that finite sets of axioms can be used to
>"specify" various non-computable sequences. Finite sets of axioms can be
>expressed in Turing machines. Therefore in some sense Turing machines
>can be used to "specify" non-computable sequences. They merely can't
>generate them. (I.e. they can do the job intensionally not
>extensionally).



    Well, axiom sets are usually infinite, but recursive, so ultimately
yes, they are expressed by a TM.

    And yes, for a real  x  if  "x(n) = m" is Pi-0-1, then  x  is recur-
sive (Delta-0-1); that's "generated".  But if x is the unique solution of
a Pi-0-1 predicate  ( {x} is Pi-0-1, "Pi-0-1 -singleton"), then  x  can be
much more complicated;  lots of Delta-1-1 (hyp) reals arise this way, although
not all.   This  x  would be "specified".


>That raises the question: what could a TM do with such a set of axioms?
>
>Well maybe it could deduce some additional interesting facts about the
>non-computable sequence (i.e. the real) which they specify (or the set
>of reals if they have more than one model).
>
>E.g., to take a trivial example, suppose we specify a sequence S1 as
>being the first one generated by diagonalisation given an enumeration of
>all the computable sequences. Now suppose we find a computable sequence,
>e.g. the digits in the binary representation of PI, and interleave those
>with the digits of S1 to provde S2. S2 is not computable (I suspect,
>since if it were, the generating algorithm could be combined with that
>for PI to produce an algorithm to generate S1).
>
>S2 is just a trivial example of a non-computable sequence which can be
>shown by simple reasoning to have an interesting property.



    S1 too was interesting already... being non-computable!


    Now look at Kleene's O, defined within this finite posting.  It
packs a lot of wallop, in spite of appearances.  It solves the halting
problem, 0';  as well as all of  0'', 0''' ... !   It embodies full
"arithmetical truth", TrA, the FO statements that hold in  w  (itself no
slouch).   And more: it enumerates the hyp (Delta-1-1) reals, solving the
membership problem for each.   We (or a TM) define it, specify it, and
prove such properties.   No, of course we have no algorithm to list it.



>I presume the mathematical theories Ilias refers to would include far
>more interesting cases of ways of specifying and reasoning about
>non-computable reals. And there's no reason why a turing machine should
>not be able to replicate that reasoning if it merely involves finite
>manipulations of finite sets of axioms.




    No problem replicating _reasoning_ ...   but the catch is, from
what hypotheses?   PA proves a lot about  w, but fails to handle, say,
Strong Ramsey or Goodstein sequences.   ZF proves those, and many more,
but again fails on some phi about  w.  Same story, of course, for any
other, stronger recursive axiom set  X.   And we face the task of _finding_
appropriate, or plausible  X.



>[AS]
>> >I don't think positive answers to my question (b) could support Penrose
>> >and others ....
>
>[IK]
>>   So we cannot actually generate _any_ infinite sequence, computable
>> or not.   But we can describe them and reason about them.
>
>And so, presumably could a suitably programmed turing machine.
>
>Of course, Penrose might claim that it would not ``understand'' what it
>was doing. But in some deep sense it's not clear to what extent we
>understand either .....
>
>This is the basis of some disputes in mathematics, e.g. between
>intuitionists and others.



    We do feel that PA _holds_ in  w,  the intuitive  w  that axioms
do not capture fully.   And no, this is not formalizable!


>It is often the case that when we think we attach a clear semantics to
>some concept it turns out later that it was very unclear. Historical
>examples are "continuity", "simultaneity", "atom", "energy", and recent
>examples are "consciousness", "emotion", "intelligence",
>"representation", "semantics" etc.


    Yes...  and every gain we make, we do formalize; but there is no
end to this.   (Which is not necessarily a bad thing at all).


>[AS]
>> >It's easy to write down a finite set of axioms for which only infinite
>> >models are possible (e.g. Peano's axioms). Using diagonalisation and a
>>
>[IK]
>>   True.  (Even though PA itself is infinite -- an induction axiom
>> for every formula).
>
>But presumably this infinite set of axioms is not needed in a higher
>order logic. Don't most students first encounter PA with a single
>high order induction axiom? Isn't that how Peano thought about it?



    Yes.  Induction in 2nd-order, "for every subset, ..."  is a single
axiom and PA's only model is  w.   But this is of little help, as we do not
_have_ a 2nd-order logic, really!  I.e. no Completeness theorem, no sufficient
formal deduction mechanism...   What do we _do_ with such a thing?   It's
hardly any different from the intuitive view of  w!



>[AS]
>> >Incidentally, this message is a demonstration that a finite brain can
>> >have thoughts about non-computable infinite sequences. I don't know how
>> >I do it: maybe I am implicitly manipulating something like the axioms
>> >which characterise these sequences.
>>
>[IK]
>>   Hmm, "characterise" isn't the word, as 1st-order axioms seldom do
>> (c.f. all those non-standard models!).
>
>OK. I was not using the word in any precise mathematical sense. In
>fact it's an interesting research question in what sense the
>(presumably finite) structures in brains are capable of
>characterising whatever it is that we are thinking about when we
>think about transfinite sets.



    Or even  w;  what is the basis for our intuition of it as a unique
object?   A strong one too!



>I've never met a brain scientist interested in this! They'd rather study
>perception, emotions, or even the truly muddy, multiply ambiguous,
>notion of consciousness ....
>
>> But we have a grasp of  w  (or  R,
>> or  V...) -- and that is where the axioms we use come from in the first
>> place.
>
>I don't know what V is.



    The cumulative hierarchy of sets.  Starting from 0 (empty) and
applying Powerset, stage after stage... the stages being the ordinals.



>However the question I am approaching in a backwards way is *how* we
>have a grasp of w. If you just start from that as a given then
>that's a problem for a psychology of mathematics, or a theory of
>requirements for a mathematical brain.
>
>How does a child turn into a mathematician? What sort of architecture
>can support that kind of development?
>
>I suspect that possibility is a consequence of having deliberative
>capabilities (e.g. planning mechanisms) together with self-monitoring
>mechanisms, both of which evolved to meet quite different requirements
>(planning enables you to avoid disastrous action sequences,
>self-monitoring enables you to improve your planning capabilities, etc.
>etc.)



    Sounds plausible.   Its being _fun_, for some reason, helps too.


>Contrast that sort of explanation with the explanation offered in
>another thread, that mathematical ability may have been selected for by
>the need to impress mates seeking "interesting" partners. This already



    Take my proof of the Riemann hypothesis.  I haven't had a _moment_
free ever since, to sit down and write it up...


>presupposes the mechanisms: it doesn't say anything about what they are
>or how they could be derived from pre-existing mechanisms mechanisms.
>However mate selection could be part of an explanation of how
>mathematical abilities were enhanced or become more wide-spread than
>their practical relevance would explain.



    I'm all for it as a trend to encourage!   But as an account of what
happened, it probably originated in a "Hermann" cartoon, professor-with-
"little'-formula-on-blackboard scowling at professor-with-BIIIG-formula, who
is being mobbed by adoring females.   Hmm, both had beards... that looked
markedly Freudian.


>Think of all those long nights without lamps, books, television etc. and
>only lots of stars to watch. Oliver Selfridge suggested this had a
>powerful effect on human development, in a talk I heard him give about
>20 years ago.)



    It led to the _invention_ of television, though;  while urban glare
and smog took care of the stars.   (I was driving up the West Coast; stopped
near Redding, in northern California, turned off the car lights -- not with
this in mind;  the stars were _stunning_, no figure of speech... and never
mind Kant either).   So I have to be out of Los Angeles...  or else drive
on Hollywood Boulevard!


>[AS]
>> >Of course it doesn't follow that any brain can actually produce any
>> >non-computable sequence. And it doesn't follow that such thoughts could
>> >not occur in a system implemented in a Turing machine.
>> >
>> >If I can reason about things I can't generate, so perhaps can a robot
>> >implemented in a Turing machine.
>
>[IK]
>>   Certainly so;  a TM can enumerate all formal deductions  S |- phi.
>> The question is, which S "carry weight" regarding  w, R, V...?   We focus
>> on S that are finite subsets of -- what?   PA?  KP?  ZFC?  ZFC + X ?
>
>Maybe one day you can write a nice tutorial on all that and post it?



    Maybe...  especially if I should find a good X!   (Quite a few
nice ones have been identified and studied already).



                        Ilias
