Bruno Marchal wrote: > > On 09 Nov 2009, at 20:43, Brent Meeker wrote: > >> >> Bruno Marchal wrote: >>> >>> Hi, >>> >>> Let us come back on the "seven step" thread. >>> >>> Let me recall the initial motivation. The movie graph argument (cf the >>> MGA thread) shows that it is senseless to attach consciousness to the >>> physical activity of a brain or a computer. >>> >>> If we keep the computational thesis for the cognitive process, we have >>> to associate consciousness to the computation, and not to its physical >>> realization. Actually we have to explain what is a "physical >>> realization" from the existence of computations. >>> >>> But then we have to understand better what we mean by computation, in >>> the mathematical sense, given that we cannot use any physics, at this >>> stage. >>> >>> Luckily, the notion of computation has been discovered last century by >>> mathematicians. They were motivated by the foundation of mathematics >>> after the "crisis" of set theory. >>> >>> So what is a computation? Let us try some definitions. >>> >>> Attempt 1: A computation is a sequence of computational states. >>> >>> If we agree with this, it remains to define what is a computational >>> states. But the definition above misses something important. I suspect >>> everything can be "recoded" as a sequence of computational states, and >>> this could be the reason why some are willing to say that rock and >>> thinks like that are conscious. >>> >>> A physicist could say that what is lacking is a genuine causality >>> relation which links the states from the sequence of computational >>> states. But: >>> - in the context of the MGA argument, this should be seen as a red >>> herring >>> - the notion of causality is extremely vague, even for a materialist. >>> >>> So: >>> >>> Attempt 2: A computation is a sequence of computational states >>> obtained sequentially through the activity of some machine. >>> >>> This is actually a good definition, except that we have to define >>> (without using physics) what we mean by activity, and machine. This >>> may be problematic because we want to define activity by a sequence of >>> state of some machine ... So: >> >> I don't think it's very good since it depends on the notion of >> "computational states" to define computation. It is not clear that any >> sequence of states cannot be "computational states". It seems to me >> that we really take as primitive the concept of a function, something >> that is given some information and transforms it into some other >> information. That's what we think brains do - and they do a lot of it >> which is not conscious. When we have abstracted away what the >> information is about, we can regard it just as a string or number and >> apply the ideas of Turing, Church, et al to the transformation as a >> computation. But we have left behind the idea that the information was >> about something or represented something. In the context of a >> computation as a consciousness this representation is a relation between >> the information being transformed and the world of which one is >> conscious. So it seems you have ignored physics rather than explained >> it. However, I can accept it as an ansatz in hope that the explanation >> will emerge in the end. > > > The problem which appears taking only the function is that a function > can be computed in many different way. For example here is a way to > compute the factorial function: > > BEGIN > READ INPUT N > SIMULATE BRENT MEEKER DRINKING COFFEE > IF BRENT SAYS "GOOD" OUTPUT N*(N-1)* ... *1 > IF BRENT SAYS "BAD" OUTPUT N*(N-1)* ... *1 > IF BRENT SAYS NOTHING, AFTER AWHILE, OUTPUT N*(N-1)* ... *1 > END > > That program will go through the right computational state > corresponding to you drinking coffee, yet compute the same function > that any more reasonable way to compute the factorial. > It will be impossible to dismiss those "computational states" if we > want a comp supervenience thesis. > But this seems like creating a problem where none existed. The factorial is a certain function, the brain performs a certain function. Now you say we will formalize the concept of function in order to study what the brain does and perhaps understand what is consciousness. But there is nothing that requires that you start over with all possible computations. That is like explaining the factorial function by considering all possible computations that produce it (like the above). It's not wrong, but it doesn't follow from saying that the factorial is a function. That's why I say I take it as an ansatz - "Let's consider all possible computations and see if we can pick out physics and the brain and consciousness from them." > > > > > >>> >>> Attempt 3: a computation is a sequence of states such that it exists a >>> machine going through that sequence of states when computed by ... >>> >>> Well, we cannot refer to activity or to a physical implementation, so >>> what? >>> >>> Attempt 4 >>> >>> A computation is a sequence of states of some machine when executed by >>> some Universal Machine. >>> >>> That is a progress, in case we succeed in defining "executed by some >>> universal machine", without using physics. But now we have the problem >>> >>> Does a universal machine exist? And what is the mathematical meaning >>> of "execution". >>> >>> But now, Church Thesis (Post, Church, Turing, Markov Thesis) is a >>> strengthening of the following weaker thesis: It exists a universal >>> machine. >>> >>> And, all those machines, for Post, Turing, were mathematical >>> construction, right at the beginning. >>> >>> Church thesis is strictly speaking the statement that his formal >>> (mathematical) system, known as Lambda Calculus, is universal with >>> respect to computability. The basic entity there are the lambda >>> expressions (those little cousins of the combinators, for those who >>> remembers old threads). >>> >>> Turing thesis is that the language describing Turing machines is >>> universal with respect of that same class, and soon it will be proved >>> that they are equivalent indeed, making Church thesis equivalent to >>> Turing thesis, (and equivalent to "Post law"). >>> >>> Then Turing proved the existence of the "universal Turing Machine", >>> and indeed, since we know now that for each such universal system for >>> such system the "understanding of the language" can be encoded in the >>> language itself. So there is a universal lambda expression. There is a >>> universal Turing Machine. A universal Post production system, or a >>> Fortran interpreter (or compiled) in Fortran, or a Lisp intepreter in >>> Lisp. >>> >>> Some may ask "which universal machine?". But the whole point of >>> classical computationalism (and UDA) consists in showing that below >>> your (our common) substitution level, we have to take account of all >>> universal machines. Any universal dovetailer dovetails on all of them. >>> So even if only one computation "wins", it has to be justify by a >>> (relative) sum on all computations. >>> >>> I have suggested to take the combinators, without success, so I will >>> suggest later to take Robinson Arithmetic, which is Turing Universal, >>> as seen as a computer. It is really very elementary arithmetic. >>> Very simple cellular automata rules leads to universality, in this >>> Church Turing sense, like the "game of life" by Conway. Universality >>> is somehow cheap, and it happens that elementary arithmetic (with >>> zero, the successor rule, addition and multiplication) is already >>> Turing universal. >>> >>> "being a piece of computations" is equivalent with "being executed by >>> the universal dovetailer", and such a proposition can be translated >>> into elementary arithmetic. This is equivalent with Gödel's showing >>> how to translated statements about propositions, theories, machines, >>> into statement about numbers. >>> >>> But be careful to understand what happen here. It is not that the laws >>> of computations or universal machine dream are so easy that we can >>> represent them by number relation, the real discovery is that the >>> relation among numbers can be very complex. >>> >>> That is why I insist so much that an understanding already of just >>> Church thesis makes you modest, even just about what you can prove >>> about numbers. >>> >>> OK? Any question about the diagonalizations of Cantor and Kleene? >>> >>> I need this for the understanding of what the phi_i are. A universal >>> number will be a number u such that phi_u(x, y) = phi_x(y). (with >>> "(x,y)" represents a number through a computable bijection). >> Could you remind me what the phi_i are? The enumerated partial >> functions? > > > The enumerated so called "partial /computable/ functions". > > To get them, take your favorite universal system (fortran, lisp, c++, > java, whatever), write down the grammatically correct description of > function (of one argument, say, that is, from N to N). Put those codes > in lexicographical order, and you get the corresponding phi_i: phi_1, > phi_2, ..., and their domain W_1, W_2, W_3, ... > > With Church thesis, all the computable functions (having the domain N) > will belong to that list, but there will be no algorithm capable of > telling in advance for any phi_i if it compute partial computable > function or a computable functions. > > Given that this is a key point for everything which will follow, I > have to be sure that most people understand exactly why this has to be so.

Ok, I think I understand. It's probably not relevant here, but physicist usually think of functions which can be computed approximately by a uniformly convergent algorithm as computable (e.g. compute pi) but I think in the above you mean computable in the Turing sense that the computation stops with the answer (e.g. compute pi to 100 decimal places). Right? Brent > > So I will come back on this. > > Thanks for the feedback, > > Bruno > > > > > > > >> >> Brent >>> >>> The key point is that the notion of computation can be defined in >>> arithmetic. By Church thesis, limiting the computations to those >>> definable in arithmetic does not eliminate any computations. >>> >>> So the computational supervenience thesis is also equivalent with the >>> arithmetical supervenience thesis. >>> >>> Another important mathematical point is that Universality for >>> computations entails non universality for provability. That is >>> incompleteness. Universal machine have capabilities far beyond what >>> they can prove and known. The universal machine can lost itself in his >>> own creation. And, ASSUMING Church thesis, the existence of the >>> universal machine is a theorem of elementary arithmetic. >>> >>> It reminds me Aurobindo: >>> >>> >>> /What, you ask, was the beginning of it all?/ >>> >>> /And it is this .../ >>> /Existence that multiplied itself/ >>> /For sheer delight of being/ >>> /And plunged into numberless trillions of forms/ >>> /So that it might/ >>> /Find / >>> /Itself/ >>> /Innumerably/ >>> >>> >>> Any questions, remarks, comments? >>> >>> Bruno >>> >>> >>> >>> >>> >>> >>> On 11 Oct 2009, at 19:53, Bruno Marchal wrote: >>> >>>> Hi John, hi Marty, >>>> On 10 Oct 2009, at 21:47, John Mikes wrote: >>>> >>>>> Bruno, we had similar puzzles in middle school in the 30s. >>>>> The barber could not shave himself because he shaved only those who >>>>> did not shave themselves (and shaved all). So for (Q #1) in the 1st >>>>> vriant >>>>> *she(?)* was a female, unless *he(?)* was a beardless male >>>> >>>> >>>> You are right. The barber gender is female. I don't see why you add >>>> that he could be a beardless male. It is part of the problem that we >>>> are in a tyrannic country where no man can have a beard. >>>> >>>> >>>> >>>> >>>>> (and the 'all' refers to only the *bearded* males requiring a >>>>> shave). >>>>> * >>>>> Q#2 is beyond me, I do not resort to a QM-pattern like Schrodinger's >>>>> cat. >>>>> (Sh/H)e is either-or, not both. >>>> >>>> I am not sure I understand, except that Q#2 remains unanswered, OK. I >>>> will first comment Marty's posts. >>>> >>>> >>>> On 11 Oct 2009, at 01:30, m.a. wrote: >>>> >>>>> *Or the barber is a special exception to the group designated >>>>> as "men" and exists on a higher level of being. Therefore he can >>>>> shave himself without transgressing the rule as stated in the >>>>> premise. Isn't this one of Russell's paradoxes? marty a.* >>>> >>>> Well, if the barber is not human, there is indeed no problem. But >>>> here the fact that it can be a woman, and that usually a barber is a >>>> human being, and that the question refer to a gender strongly suggest >>>> that the solution "the barber is a woman" is more reasonable that >>>> "the barber is an extraterrestrial". I think. >>>> >>>>> And didn't Russell decide that this type of paradox should be >>>>> outlawed from allowable statements within the practice of >>>>> logic? m.a. >>>> >>>> Nice you see the relation with Russel's paradox. This is a very deep >>>> paradox which shows we have to handle the notion of sets with some >>>> care. Torgny Tholerus already mentionned this, and he defended the >>>> idea this is an argument for ultrafinitism, which in my opinion is >>>> like throwing the baby (the infinite sets) with the water of the bath. >>>> >>>> If we dare to consider that the collection of *all* sets is itself a >>>> set, we have a nice example of a set which contains itself as an >>>> element. >>>> This is not problematical in itself, and in some axiomatic set >>>> theories, some sets can belong to themselves. >>>> >>>> What becomes problematical is the idea of defining a set in intension >>>> by using *any* criteria. >>>> Indeed, let us call *universe*, U, the set of all sets. U belongs-to >>>> U. But {1, 2} does not belongs to {1, 2}, so some sets belong to >>>> themselves and some sets don't. So it looks like we could define a >>>> new set E of which contains all the sets which does not belongs to >>>> themselves. For example clearly the set {1, 2} is an element of E, >>>> and U is not an element of E. >>>> But then we are in trouble. Does E belongs to E? >>>> If E belongs to E, then he contradicts the definition of E, which >>>> contains only those set which does not belong to themselves. So E has >>>> to not belong to E. But then E does verify its own definition, so >>>> that he does belong to E. So E belongs to E and E does not belong to >>>> E. Damned. >>>> >>>> Well, this proves that the intuitive idea of set is inconsistent. We >>>> do have to make the notion more precise to avoid such kind of >>>> reasoning. All the many very different attempts to make the notion of >>>> set precise have lead toward interesting mathematics, philosophy and >>>> even religion (i think). But this would lead us far away of the >>>> topic. We will have opportunity to come back on this. With the most >>>> usual axiomatic set theories, the set of all sets is not a set, and >>>> the criteria to defined set in intension is usually weakened. So much >>>> that some axioms have to be added to get a reasonably rich theory. >>>> >>>> >>>> Question 2. >>>> >>>>> 2) What the hell has all this to do with diagonalization, ... and >>>>> universal machine? >>>>> >>>> >>>> Let us write (x y) to say that some relation between x and y exists. >>>> In the problem, for example, (x y) means that x shaves y, and x and y >>>> are supposed to be humans. >>>> In Russel's paradox (x y) means that x belongs to y, that is X >>>> contains y as an element, and x and y are supposed to be sets. >>>> >>>> Argument by diagonalization always proceeds by using the diagonal >>>> twice. Which diagonal? >>>> >>>> 1) the first diagonal: >>>> >>>> Well (x y) is a couple, and so belongs to the cartesian product of >>>> the set (of those x, y) with itself. Put in another way, if you look >>>> at all (x y) you get a matrix of pair of things (humans in the >>>> problem, sets in the paradox). >>>> >>>> OK? >>>> >>>> Well, the (x x) will constituted the diagonal of that matrix. x is >>>> supposed to vary in their respective domain (the humans in the >>>> village, the set, in the universe of all sets. >>>> >>>> In the village, this gives something like (Sophie Sophie) (Claude >>>> Claude) (Arthur Arthur) etc. As long as there are inhabitants in the >>>> village. With the sets, the diagonal is any couple (x x) with x an >>>> arbitrary set. >>>> >>>> The barber, let us call it B, and the paradoxical set E from above >>>> are defined in a very similar way, said "by diagonalization", because >>>> it involves the diagonal (x, x). >>>> >>>> The barber is defined by the condition that he shaves all and only >>>> the men who does not shave themselves. >>>> >>>> B shaves x >>>> if and only if >>>> x is a man and NOT (x x). "NOT (x,x)" means that x does not shave >>>> x. OK? >>>> >>>> E is defined by the condition that it contains all and only the sets >>>> which does not contain themselves as element. >>>> >>>> E contain x as element >>>> if and only if >>>> NOT(x x) >>>> >>>> 2) The second diagonal: >>>> >>>> Consist in looking what happen to the barber B, or the set E, when >>>> applied to itself. >>>> >>>> The second diagonalisation is the question (B B)?, or the question >>>> (E E)? >>>> >>>> (B B)? = Does B shaves B? >>>> >>>> And then, by definition of the barber B, if it is a man, we get a >>>> contradiction. Fortunately no contradiction occurs in case the barber >>>> is a woman. If he is a man, he has to shave himself if and only if he >>>> does not shave himself. If she is a woman, then she does not shave >>>> herself and has no obligation to do given that the barber shaves >>>> *only* men, by definition. So here, we have just proved that in that >>>> village the barber is a woman. Or, taking Marty's remark into >>>> account; we have proved that IF the barber is a human, THEN it is a >>>> woman. No contradiction occurs if the barber is a god, an >>>> extraterrestrial or a machine, with or without gender. It can be >>>> anything not shaving itself, and shaving by definition only the men >>>> of the village. >>>> >>>> (E E)? = Does the set E contains itself as an element? >>>> >>>> If yes: then it violates its own definition. >>>> If no: well, it violates again its definition. >>>> >>>> With (B B), we "prove a theorem", thanks to the saving condition >>>> excluding the possibility that (B B) is true in advance. >>>> With (E E) we get a genuine difficulty showing that the naïve idea of >>>> sets is inconsistent. >>>> >>>> And what if we delete the saving condition in the Barber problem, >>>> leading us to the "usual" Barber paradox. What if we say, with x >>>> varying on all humans (making barber shaving all womans, unless using >>>> John's proposal for the notion of "not shaving"). >>>> >>>> First diagonalisation: >>>> >>>> B shaves x >>>> if and only if >>>> NOT (x x). >>>> >>>> Well, second diagonalisation, we get: >>>> >>>> (B B) >>>> if and only if >>>> NOT(B B) >>>> >>>> A contradiction. Is it catastrophical? Not at all, it is a >>>> contradiction only assuming such a village exists. So it is only a >>>> proof that nowhere in any consistent reality or galaxies, >>>> multiverses, whatsoever you will ever find a barber, inhabiting a >>>> village and shaving all and only all the inhabitants who don't shave >>>> themselves. You will not find it for the same reason you will never >>>> find a square with only three sides, (unless dreaming or >>>> hallucinating or something?). >>>> >>>> Do you see the two diagonalisations in Cantor theorem's proof? And in >>>> Kleene's proof? >>>> >>>> We suppose there is a bijection between N and some set of functions. >>>> So we suppose there is an indexing of the functions, f_i available. >>>> The first diagonalisation is in the definition of g: >>>> >>>> g(n) = f_n(n) + 1 >>>> >>>> >>>> Then, for "good" or "bad" reasons, according of the context, we >>>> suppose g belongs to the set of f_n, so that we can apply g on its >>>> own index, that is the second diagonalization, and get wonderful >>>> variate results according again the context. >>>> >>>> Actually >>>> >>>> 1) when f_i are supposed to be a bijection between N and N^N, we get >>>> a contradiction. Showing that N^N are not enumerable. >>>> 2) when f_i are supposed to be a computable bijection between N and >>>> N^N-comp, we get a contradiction. Showing that, although enumerable, >>>> 2^N-comp and N^N-comp are not computably enumerable. >>>> 3) when f_i are supposed to belong to an universal sequence of >>>> N^N-comp, we ... crash the universal machine, and find ourself unable >>>> to prevent by any means such crashing without destroying the machine >>>> universality. Showing that if we want *all*l total computable >>>> functions in the universal sequence N^N-partial-comp, they will be >>>> hidden in a non solvable ways (Pi-2 complete) among the partial >>>> functions. Partial function are like ignorance tunnels, or abysses, >>>> in the reality with which universal machines can be confronted. >>>> >>>> I will come back on this, and develop, but this could make sense for >>>> those who have followed the last posts, in this thread. >>>> >>>> Precisely N^N-comp is the set of functions from N to N which are >>>> computable. >>>> N^N-partial-comp is the set of partial functions from N to N which >>>> are computable on their domains. Those partial functions are either >>>> defined on all N, and called total functions, or they are not defined >>>> for some number, and which, strictly speaking are functions from a >>>> subset of N to N. >>>> >>>> Take it easy. I intend to summarize and come back on some crucial >>>> points, soon or a bit later. >>>> >>>> Bruno >>>> >>>> >>>> >>>>> On Fri, Oct 9, 2009 at 12:00 PM, Bruno Marchal <marc...@ulb.ac.be >>>>> <mailto:marc...@ulb.ac.be> >>>>> <mailto:marc...@ulb.ac.be>> wrote: >>>>> >>>>> >>>>> Hi, >>>>> >>>>> I am so buzy that I have not the time to give long explanations, >>>>> so I >>>>> give here a short exercise and a subject of reflexion instead. >>>>> >>>>> Exercise: >>>>> >>>>> There is Tyrannic country where by law it was forbidden for any >>>>> man to >>>>> have a beard. >>>>> And there is village, in that country, and it is said that there >>>>> is a >>>>> barber in that village, who shaves all and only the men who don't >>>>> shave themselves. >>>>> >>>>> Two questions: >>>>> >>>>> 1) What is the gender of the barber? >>>>> 2) What the hell has all this to do with diagonalization, ... and >>>>> universal machine? >>>>> >>>>> Have a good day, >>>>> >>>>> Bruno >>>>> >>>>> http://iridia.ulb.ac.be/~marchal/ >>>>> <http://iridia.ulb.ac.be/%7Emarchal/> >>>>> <http://iridia.ulb.ac.be/%7Emarchal/> >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> >>>> >>>> http://iridia.ulb.ac.be/~marchal/ <http://iridia.ulb.ac.be/%7Emarchal/> >>>> >>>> >>>> >>>> >>>> >>>> >>> >>> http://iridia.ulb.ac.be/~marchal/ <http://iridia.ulb.ac.be/%7Emarchal/> >>> >>> >>> >>> t?hl=en >>> -~----------~----~----~----~------~----~------~--~--- >>> >> >> >> >> > > http://iridia.ulb.ac.be/~marchal/ <http://iridia.ulb.ac.be/%7Emarchal/> > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---