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" 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 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 wrote: >"Marvin Minsky" 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 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