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:
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).
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>
>> 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/~marchal/
>
>
>
>
> >
http://iridia.ulb.ac.be/~marchal/
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
