The seven step series

[John Mikes]

Yes, Bruno, it helps - however: I did not want to put you into any apology!

The list is a free communication among free spirits and controversy is part of it.

What I 'read' in your reply still "sticks" within 'math' and my principal point is: the image represented is STILL what a human mind MAY think, irrespective of 'machines' above it - as well humanly thought out.

Of course smart mathematicians came up with ideas similar to what I thought and produced 'remedies' to cover the uncovered. Math extends as we go.

 

"...But, once we assume comp, N is "ontologically" enough, all other sort
of numbers do necessarily appear as unavoidable epistemological
constructions,..."

I am not for the 'ontological' because that is based on whatever we KNOW and I prefer the 'epistemological' ("in spe" acquirable) totality. Extending yesterday's ontology into tomorrow's by epistemic enrichment .

 

We cannot override the capabilities of our 'mind', restricted by the brain- tissue - function and bordered by our 'existence'. And - I condone it happily: the best we can do is math-ways (not mathematics) with all freedom within.

WITHIN is the word.

I represent in my thinking the humbleness of being restricted. I call it my scientific agnosticism - allowing "things" beyond our limitations.

This is why I don't use "truth" or even "everything". And I use common sense.

(Mine - that is <G>)

 

So far you always pronounced the (infinite?) series of NATURAL numbers and I jumped on a number-wise defined item that was outside of them.

Sorry, when it comes to speculation, I am jumpy.

I did not know about those non-natural naturals.

 

Have a good day

 John

On Fri, Sep 18, 2009 at 3:23 AM, Bruno Marchal <marchal@...> wrote:

On 17 Sep 2009, at 18:17, John Mikes wrote:

> Dear Bruno,
>
> it is not very convincing when you dissect my sentences and
> interject assuring remarks on statements to come later in the
> sentence, negating such remarks  in advance, on a different basis.
>
> I argued that - upon what you (and the rest of the multimillion
> mathematicians past and present) live with  - the applied
> nomenclature is incomplete. It is not a counter-argument that "it is
> used by many" or "for so many purposes". Of course it is in use,
> that was my point.
> I am not basing my position on opinions from "within" the argued
> position.
> (May the "-2 level" point to a 'total senselessness' of my opinion?
> I did not understand it, nor did I the (N + *) structure, which
> therefore I find irrelevant in the question what "I" raised. (I, not
> Rieman, Cantor, etc.).
>
> There is the idea of including 'quantities' in our worldview (excuse
> my naive reference, but you illustrated earlier "2" as "II" and "3"
> as "III" etc. and THIS in my mind means sort of a quantity) and such
> 'system' would be qualitatively
> infinite if we try to include quantities from all directions (math
> is the level of handling such quantities that 'came up' in the past
> - gradually - and we may expect more to come, new discoveries,
> extending the qualitative inventory)
> although in your words 'everything' can be expressed by (many many?)
> of your natural numbers (except  square root 2?) - what is exactly
> my point.
>
> I did not want to open a scientific argument - I am no match for
> you, or any other 'mathematically educated' person. I scribbled a
> 'qualitative' idea of thinking in 'wider' terms than the defined
> 'natural numbers' in a worldview of a (qualitative) "totality" -
> what I pursue, but do not understand in my sci.fic agnosticism.
>
> I am sorry if I bored you with my remark.

I apologize if I gave that impression, but I try sometimes to be not
too much long in the mails, and being short can have given that
impression. Sorry. My point was just that there is a sense where
natural numbers are not enough in math, and that is why mathematicians
have extended the set N. N, then Z, then Q, then R, then the complex
numbers, then the quaternions, octonions, etc.
But, once we assume comp, N is "ontologically" enough, all other sort
of numbers do necessarily appear as unavoidable epistemological
constructions, if only to understand the (additive-multiplicative)
behavior of the natural numbers, a bit like Riemann use complex
numbers to provide information on the prime (natural) numbers.

Without digging a bit more on the technical issue, I can hardly say
more than my usual: there is only natural number, together with the
additive and multiplicative law. This, assuming comp, already defines
a "matrix" of number's dreams, and those cannot avoid the internal
phenomenological appearance of richer structures, like the "other"
numbers, and indeed like the whole physical appearances.

Does this help you a little bit?

Best,

Bruno
>

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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

I give the answer.

On 17 Sep 2009, at 16:27, Bruno Marchal wrote:

On 16 Sep 2009, at 18:12, Bruno Marchal wrote:

If it is OK, in the next post we begin to address the computability issue. I give you an anticipative exercise or subject reflection. This is a deep exercise. Its solution leads to the notion of universal function and universal number/machine. More exactly it leads to an evaluation of the price we have to pay if we want to believe in that notion.

We have seen that the set N^N is non enumerable. This means it is a *huge* infinite set, compared to N.

We could argue that there are too much functions in that set. Most usual functions that we encounter in real life, both in math and physics, seem to share the property that they are computable. This means that we can write some rules or recipe for computing them, or that, may be, we can build some mechanical device capable of computing them. The natural functions we met were the exponential f(n) = 2^n, or the factorial(n), or similars. It seems that we can explain to each other how to compute them, and you already known that we can build machines computing them indeed. So, we could decide, if only to avoid those big infinities, to restrict ourself on the computable functions. Let us define N^N-comp to be the set of computable functions from N to N.

The question is: is there a bijection from N to N^N-comp ?

This is a tricky question. 

I give you an argument that there is a bijection between N and N^N-comp. Followed by an argument that there is no bijection between N and N^N-comp.

Which one is wrong?

1) A "proof" that N^N-comp is enumerable.

I said that a function from N to N, is computable (and thus in N^N-comp), if there is a recipe explaining how to compute it.

But this means that there has to be a language in which we can describe or encode that explanation. A language is a set of finite expressions build from some finite alphabet. But we have seen that the set of finite expressions build on an alphabet (which is always a finite set) is enumerable. Those expressions, corresponding to the explanation describing the recipe for a computable function, will constitute a subset of the set of all expressions, and is thus enumerable. So N^N-comp is enumerable.

That is correct. N^N-comp is enumerable. 

2) A "proof" that N^N-comp is NOT enumerable.

Suppose N^N-comp is enumerable, and let f_n be such an enumeration, with n in {0, 1, 2, ...}. Consider the diagonal function g defined by g(n) = f_n(n) + 1. All f_n are computable, and surely "+ 1" is computable, so g is a computable function.

That is wrong. It is true that all the f_n are computable, and that "+ 1" is computable. But to compute g on n I have to find f_n, and although all f_n are computable, the bijection itself which send n to f_n cannot be computable.

Why? Well if it is, given that by the reasoning above shows correctly that N^N-comp is enumerable, what follows would lead to 0 = 1.

But then g has to belong to f_n, which enumerates the computable functions. So there is a k such that g = f_k. But then g(k) = f_k(k) = f_k(k) + 1. But f_k is a computable function from N to N, so f_k(k) is a number, which I can subtract on both side, so 0 = 1. So N^N^comp is not enumerable.

Well, there is a problem, isn't it? N^N-comp cannot be both enumerable and non enumerable. So one of those proofs has to be wrong. Which one?

So it was the second "proof" which was wrong. We have implicitly assumed that the enumeration f_n was a computable enumeration. The reasoning above in "1)" has show that there is a bijection between N and N^N-comp, and not that such an enumeration could be done by a *computable* bijection between N and N^N.

We say that the f_n are, although enumerable, not computably enumerable. 

On the set N^N of all functions from N to N, Cantor diagonal shows that N^N is non enumerable.

On the set N-N-comp, the diagonal shows that N^N-comp, although enumerable is non computably enumerable.

OK?  take the time to swallow this, and ask question if this seems not clear. We are at the crux of the subject.

----------------

Next anticipative exercise.

If N^N-comp is not  or non *computably* enumerable, so that we cannot enumerate mechanically, using some recipe, the f_n, is there still some hope to develop a *universal* machine, or a *universal* language, or a *universal* dovetailer? all capable of computing ALL computable function?  How to escape the diagonal contradiction?

We would appreciate that a universal could be able, given the nth "program" (identified by the number n), and the datum m, to compute f_n(n). Indeed that is how we will *define* universal machine. But if the machine cannot find "mechanically" the f_n, what can we do or hope for? What is the price of universality? 

Gödel's theorem has forced us to abandon the notion of universal provability (in the realm of the relations and functions on numbers), and this results mainly from the use of a diagonal argument 5Godel 1931). So when Church told him that he decided to define computable by the formal language of Lambda-calculus, Kleene thought this was impossible, and that he could by diagonalization refute that universality pretension. But 'overnight', after failing to diagonalize against lambda-calculus, he realize that Church *may* be correct, and he invented the vocable of "Church thesis".

CHURCH's (original) thesis: a function from N to N is computable if we can explain in lamdda-calculus how to compute it.

What could be so special about Church language that it could define ALL computable functions from N to N, and yet be immune to the diagonal argument?

Bruno

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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

On 18 Sep 2009, at 17:00, I wrote:

> On the set N^N of all functions from N to N, Cantor diagonal shows  
> that N^N is non enumerable.
> On the set N-N-comp, the diagonal shows that N^N-comp, although  
> enumerable is non computably enumerable.
>
> OK?  take the time to swallow this, and ask question if this seems  
> not clear. We are at the crux of the subject.
>
> ----------------
>
> Next anticipative exercise.
>
> If N^N-comp is not  or non *computably* enumerable, so that we  
> cannot enumerate mechanically, using some recipe, the f_n, is there  
> still some hope to develop a *universal* machine, or a *universal*  
> language, or a *universal* dovetailer? all capable of computing ALL  
> computable function?  How to escape the diagonal contradiction?
>
> We would appreciate that a universal could be able, given the nth  
> "program" (identified by the number n), and the datum m, to compute  
> f_n(n). Indeed that is how we will *define* universal machine. But  
> if the machine cannot find "mechanically" the f_n, what can we do or  
> hope for? What is the price of universality?
>
> Gödel's theorem has forced us to abandon the notion of universal  
> provability (in the realm of the relations and functions on  
> numbers), and this results mainly from the use of a diagonal  
> argument 5Godel 1931). So when Church told him that he decided to  
> define computable by the formal language of Lambda-calculus, Kleene  
> thought this was impossible, and that he could by diagonalization  
> refute that universality pretension. But 'overnight', after failing  
> to diagonalize against lambda-calculus, he realize that Church *may*  
> be correct, and he invented the vocable of "Church thesis".
>
> CHURCH's (original) thesis: a function from N to N is computable if  
> we can explain in lamdda-calculus how to compute it.
>
> What could be so special about Church language that it could define  
> ALL computable functions from N to N, and yet be immune to the  
> diagonal argument?

OK. I have defined a computable function (from N to N) as being a  
function which can computed from a finite description in some  
language, and this makes them intuitively enumerable. The admittedly  
vague idea here, is that any set of finite things is either finite or  
enumerable.

But of course, this is not entirely convincing, we could use a non  
enumerable set to multiply non enumerably finite beings, and a case  
could be made that if we allow a non enumerable set of languages, or a  
non enumerable set of beings understanding those languages, we could  
find for *any* functions, a language defining that function or a being  
computing that function, making all function computable, by some  
being, and this would make the notion of computability relative if not  
trivial.

Let me do something which illustrates this in a non trivial way,  
though, but which relies on what I have already said about the  
ordinals some times ago. I will repeat the definition.

I will write as if I was criticizing myself.

The notion of computable function does not make sense, by the argument  
above. To define a notion of computability, you have to define first a  
fixed language L, in which the correct grammatical expressions will be  
definition of functions, that is will correspond to the description of  
how to compute those functions, on each of their arguments. In that  
case, the f_n are clearly *computably* enumerable. The bijection n ->  
f_n has to be computable, then. But in that case,  the g function,  
the one defined by g(n) = f_n(n) + 1,  is clearly computable, and the  
Cantor-like diagonal argument just showed that that g is NOT  
*definable* in the language L. L cannot be universal.

And given that the argument seems not to depend on which language L,  
it looks like we have proved that there is no universal language.

After all I could build a new language now, by adding a primitive  
computing g to the L language. Diagonalizing again would provide a new  
function g2, which we can add as new primitive again, and so one,  
getting

L, g, g2, g3, g4, ...

I could even build a more powerful language by adding a primitive  
which computes all gi automatically, giving a new primitive, that I  
can add to L, so that this process can be extended into the  
constructive tranfinite (if you remember the post on the growing  
functions, and the ordinals).

Could such a process converge toward a language computing all  
computable functions? That is, is there a universal language in which  
we can define all computable function?

It will not converge for any effective, or constructive of computable  
ordinal, because if it does, we would get a computable bijection from  
N to N^N-comp. This we already know cannot exist, the diagonal leads  
to 0 = 1.

Could it converge on non effective ordinals. Yes, and this can be used  
to make precise the idea that by liberalizing enough the notion of  
language we can define universal language. But using a non effective  
ordinal to define the notion of computable would illustrate only how  
non universal that notion could be.

All this to make more amazing the seemingly naive proposal by Church,  
to Kleene, for a definition of computability:

A function is computable only if I can described in my language (which  
was lambda calculus, the famous cousin of the combinators).

Kleene will try to diagonalize on Church functions, but will not  
succeed. The reason is that Church language defines a vaster class of  
functions that N^N-comp. Those will be noted phi_n, to distinguish  
them from the computable functions. That class is computably  
enumerable, the bijection n ==> phi_n is computable, but not all are  
computable functions from N to N, so may be undefined. This saves the  
language from the diagonal: now g can belong to the class, and so g  
will be some f_k, and f_k(k) will be equal f_k(k)+1. But f_k(k) will  
be undefined, the computation of f_k(k) will run forever, the computer  
is crashing, if you want.

  If the language L is universal, it defines all computable functions  
from N to N. This means that in the computable enumeration of the  
partial computable functions from N to N., phi_n, that is

phi_1, phi_2, phi_3, ....

All the f_n will appear, here and there. The f_n constitute a  
enumerable subset of the phi_i. But certainly not a computably  
enumerable subset. If L is universal, then there is absolutely no  
algorithm for telling, in general, if phi_j is a total function or a  
strictly partial function. If that would exist, we would be able to  
effectively filtrated the f_n from the phi_n, to provide an effective  
enumeration of all N^N-comp, which gives 0 = 1.

Note this. Here we have used arithmetical realism. If you remember, it  
was the use of the excluded middle which provides me the tool to prove  
that there are irrational numbers x and y such that x^y  is rational,  
showing you only that the solution was in the set {sqrt(2)^sqrt(2),  
(sqrt(2)^sqrt(2))^sqrt(2)}. Here, by assuming a language L is  
universal (for N^N-comp) we have to accept that the functions f_n are  
non constructively dispersed in a vaster set: the phi_i. The  
universality of the language makes that dispersion absolutely non  
computable. We see that the price of universality is the unability to  
compute definable feature of nameable of objects, and unpredictible  
behavior.

Is Church thesis true?

There are four deep reasons to find CT rather plausible.

1) The closure of the class of partial computable functions for the  
diagonalization.
2) All attempts, some very independent, some very different, to define  
a general notion of computability has always given the same class N^N-
comp.
3) Anything proved comp-insoluble remains unsolved
4) the common impression we do share the elementary intuition of  
finite things and of applying finite things on themselves repetitively  
up to a possible but not guarantied satisfaction.

The rational x^y disperse itself non constructively in  
{sqrt(2)^sqrt(2), (sqrt(2)^sqrt(2))^sqrt(2)}, but I told you that  
complex mathematics can show that the precise solution is  
sqrt(2)^sqrt(2). But the non constructive dispersion of the f_n in the  
phi_n cannot be dispensed with. The diagonal above shows exactly that,  
and that is what makes arithmetical realism indispensable if we want a  
notion of universality. Here realism really means an acceptance of a  
universal modesty about our ways to separate the f_n from the phi_n,  
and many propositions relating those objects and the machines which  
compute them.

Let <x,y> represents a the image of a computable bijection from NXN to  
N, so that we can code a couple of numbers by one number. Let phi_n be  
a "universal enumeration" (that is an enumeration of all partial  
computable functions)
I will say that a number u is universal, if phi_u(<x,y>) = phi_x(y).

I have to go. Ask question, and don't worry if it seems difficult. It  
is difficult.  Conceptually, just not for the notations and the typo  
errors .... I will sum up soon all what the same diagonalization proved.

Diagonalization and non constructive reasonings are the key tools for  
the study of machine's theology and machine's machine's theology ....  
You can see this as the self-study of an abyssal intrinsic ignorance,  
with the discovery that it is related to life forms and many other  
unknowns and mysteries ....

Questions, remarks?

Bruno



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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

Hi,

I sum up the definition and results seen so far.

N = {0, 1, 2, ...}, the set of natural numbers (also called positive  
integers).

N^N = {f such that f is a function from N to N} = the set of functions  
from N to N.

Universal language: a language in which we can describe formally how  
to compute any intuitively computable functions.

Weak Church thesis: there exists a universal language.

Church thesis: lambda-calculus is universal.
Turing thesis: the Turing machine specification language is universal
Markov thesis: the Markov formalism is universal
Post laws: production system is universal
Beniov-Deutsch: quantum turing machine is universal
etc.

All such thesis have been proved equivalent. Instead of lambda  
calculus, turing machines, Markov systems or Post production  
rules, ... you can use your favorite programming language (ADA,  
FORTRAN, LISP, Prolog, C++, etc.). Thanks to Church thesis, I will not  
need to actually use any of those formal systems, and what we prove  
will be true for any of them. Actually I am using only the weak Church  
thesis.

Computable = programmable in my favorite universal language (this  
definition use the (weak) Church thesis)

N^N-comp = {f such that f is a computable function from N to N}

N^N-comp+ = {f such that f is a computable function from a subset of N  
to N} = {f such that f is a partial computable function}


Note that N is a particular subset of N; so a computable function  
(defined on the whole N) is a particular case of a partial function,  
so N^N-comp is included in N^N-comp+

Training exercise: try to reprove for your own benefit that:

N^N is non enumerable

N^N-comp is enumerable

N^N-comp is non computably enumerable (the bijection exists but is not  
computable)

N^N-comp+ is enumerable

N^N-comp+ is computably enumerable (allowing repetition: different  
numbers can correspond to the same function).

Bruno




On 21 Sep 2009, at 19:47, Bruno Marchal wrote:

>
>
> On 18 Sep 2009, at 17:00, I wrote:
>
>
>> On the set N^N of all functions from N to N, Cantor diagonal shows
>> that N^N is non enumerable.
>> On the set N-N-comp, the diagonal shows that N^N-comp, although
>> enumerable is non computably enumerable.
>>
>> OK?  take the time to swallow this, and ask question if this seems
>> not clear. We are at the crux of the subject.
>>
>> ----------------
>>
>> Next anticipative exercise.
>>
>> If N^N-comp is not  or non *computably* enumerable, so that we
>> cannot enumerate mechanically, using some recipe, the f_n, is there
>> still some hope to develop a *universal* machine, or a *universal*
>> language, or a *universal* dovetailer? all capable of computing ALL
>> computable function?  How to escape the diagonal contradiction?
>>
>> We would appreciate that a universal could be able, given the nth
>> "program" (identified by the number n), and the datum m, to compute
>> f_n(n). Indeed that is how we will *define* universal machine. But
>> if the machine cannot find "mechanically" the f_n, what can we do or
>> hope for? What is the price of universality?
>>
>> Gödel's theorem has forced us to abandon the notion of universal
>> provability (in the realm of the relations and functions on
>> numbers), and this results mainly from the use of a diagonal
>> argument 5Godel 1931). So when Church told him that he decided to
>> define computable by the formal language of Lambda-calculus, Kleene
>> thought this was impossible, and that he could by diagonalization
>> refute that universality pretension. But 'overnight', after failing
>> to diagonalize against lambda-calculus, he realize that Church *may*
>> be correct, and he invented the vocable of "Church thesis".
>>
>> CHURCH's (original) thesis: a function from N to N is computable if
>> we can explain in lamdda-calculus how to compute it.
>>
>> What could be so special about Church language that it could define
>> ALL computable functions from N to N, and yet be immune to the
>> diagonal argument?
>
>
> OK. I have defined a computable function (from N to N) as being a
> function which can computed from a finite description in some
> language, and this makes them intuitively enumerable. The admittedly
> vague idea here, is that any set of finite things is either finite or
> enumerable.
>
> But of course, this is not entirely convincing, we could use a non
> enumerable set to multiply non enumerably finite beings, and a case
> could be made that if we allow a non enumerable set of languages, or a
> non enumerable set of beings understanding those languages, we could
> find for *any* functions, a language defining that function or a being
> computing that function, making all function computable, by some
> being, and this would make the notion of computability relative if not
> trivial.
>
> Let me do something which illustrates this in a non trivial way,
> though, but which relies on what I have already said about the
> ordinals some times ago. I will repeat the definition.
>
> I will write as if I was criticizing myself.
>
> The notion of computable function does not make sense, by the argument
> above. To define a notion of computability, you have to define first a
> fixed language L, in which the correct grammatical expressions will be
> definition of functions, that is will correspond to the description of
> how to compute those functions, on each of their arguments. In that
> case, the f_n are clearly *computably* enumerable. The bijection n ->
> f_n has to be computable, then. But in that case,  the g function,
> the one defined by g(n) = f_n(n) + 1,  is clearly computable, and the
> Cantor-like diagonal argument just showed that that g is NOT
> *definable* in the language L. L cannot be universal.
>
> And given that the argument seems not to depend on which language L,
> it looks like we have proved that there is no universal language.
>
> After all I could build a new language now, by adding a primitive
> computing g to the L language. Diagonalizing again would provide a new
> function g2, which we can add as new primitive again, and so one,
> getting
>
> L, g, g2, g3, g4, ...
>
> I could even build a more powerful language by adding a primitive
> which computes all gi automatically, giving a new primitive, that I
> can add to L, so that this process can be extended into the
> constructive tranfinite (if you remember the post on the growing
> functions, and the ordinals).
>
> Could such a process converge toward a language computing all
> computable functions? That is, is there a universal language in which
> we can define all computable function?
>
> It will not converge for any effective, or constructive of computable
> ordinal, because if it does, we would get a computable bijection from
> N to N^N-comp. This we already know cannot exist, the diagonal leads
> to 0 = 1.
>
> Could it converge on non effective ordinals. Yes, and this can be used
> to make precise the idea that by liberalizing enough the notion of
> language we can define universal language. But using a non effective
> ordinal to define the notion of computable would illustrate only how
> non universal that notion could be.
>
> All this to make more amazing the seemingly naive proposal by Church,
> to Kleene, for a definition of computability:
>
> A function is computable only if I can described in my language (which
> was lambda calculus, the famous cousin of the combinators).
>
> Kleene will try to diagonalize on Church functions, but will not
> succeed. The reason is that Church language defines a vaster class of
> functions that N^N-comp. Those will be noted phi_n, to distinguish
> them from the computable functions. That class is computably
> enumerable, the bijection n ==> phi_n is computable, but not all are
> computable functions from N to N, so may be undefined. This saves the
> language from the diagonal: now g can belong to the class, and so g
> will be some f_k, and f_k(k) will be equal f_k(k)+1. But f_k(k) will
> be undefined, the computation of f_k(k) will run forever, the computer
> is crashing, if you want.
>
>  If the language L is universal, it defines all computable functions
> from N to N. This means that in the computable enumeration of the
> partial computable functions from N to N., phi_n, that is
>
> phi_1, phi_2, phi_3, ....
>
> All the f_n will appear, here and there. The f_n constitute a
> enumerable subset of the phi_i. But certainly not a computably
> enumerable subset. If L is universal, then there is absolutely no
> algorithm for telling, in general, if phi_j is a total function or a
> strictly partial function. If that would exist, we would be able to
> effectively filtrated the f_n from the phi_n, to provide an effective
> enumeration of all N^N-comp, which gives 0 = 1.
>
> Note this. Here we have used arithmetical realism. If you remember, it
> was the use of the excluded middle which provides me the tool to prove
> that there are irrational numbers x and y such that x^y  is rational,
> showing you only that the solution was in the set {sqrt(2)^sqrt(2),
> (sqrt(2)^sqrt(2))^sqrt(2)}. Here, by assuming a language L is
> universal (for N^N-comp) we have to accept that the functions f_n are
> non constructively dispersed in a vaster set: the phi_i. The
> universality of the language makes that dispersion absolutely non
> computable. We see that the price of universality is the unability to
> compute definable feature of nameable of objects, and unpredictible
> behavior.
>
> Is Church thesis true?
>
> There are four deep reasons to find CT rather plausible.
>
> 1) The closure of the class of partial computable functions for the
> diagonalization.
> 2) All attempts, some very independent, some very different, to define
> a general notion of computability has always given the same class N^N-
> comp.
> 3) Anything proved comp-insoluble remains unsolved
> 4) the common impression we do share the elementary intuition of
> finite things and of applying finite things on themselves repetitively
> up to a possible but not guarantied satisfaction.
>
> The rational x^y disperse itself non constructively in
> {sqrt(2)^sqrt(2), (sqrt(2)^sqrt(2))^sqrt(2)}, but I told you that
> complex mathematics can show that the precise solution is
> sqrt(2)^sqrt(2). But the non constructive dispersion of the f_n in the
> phi_n cannot be dispensed with. The diagonal above shows exactly that,
> and that is what makes arithmetical realism indispensable if we want a
> notion of universality. Here realism really means an acceptance of a
> universal modesty about our ways to separate the f_n from the phi_n,
> and many propositions relating those objects and the machines which
> compute them.
>
> Let <x,y> represents a the image of a computable bijection from NXN to
> N, so that we can code a couple of numbers by one number. Let phi_n be
> a "universal enumeration" (that is an enumeration of all partial
> computable functions)
> I will say that a number u is universal, if phi_u(<x,y>) = phi_x(y).
>
> I have to go. Ask question, and don't worry if it seems difficult. It
> is difficult.  Conceptually, just not for the notations and the typo
> errors .... I will sum up soon all what the same diagonalization  
> proved.
>
> Diagonalization and non constructive reasonings are the key tools for
> the study of machine's theology and machine's machine's theology ....
> You can see this as the self-study of an abyssal intrinsic ignorance,
> with the discovery that it is related to life forms and many other
> unknowns and mysteries ....
>
> Questions, remarks?
>
> Bruno
>
>
>
> 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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

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/




--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[John Mikes]

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

(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.

 

John M

On Fri, Oct 9, 2009 at 12:00 PM, Bruno Marchal <marchal@...> 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/



--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[m.a.-2]

Some parts of this message have been removed. Learn more about Nabble's security policy.

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.

 

 

 

----- Original Message -----

From: jamikes@...

To: everything-list@...

Sent: Saturday, October 10, 2009 3:47 PM

Subject: Re: The seven step series

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

(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.

 

John M

On Fri, Oct 9, 2009 at 12:00 PM, Bruno Marchal <marchal@...> 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/



--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[m.a.-2]

Some parts of this message have been removed. Learn more about Nabble's security policy.

And didn't Russell decide that this type of paradox should be outlawed from allowable statements within the practice of logic?      m.a.

 

----- Original Message -----

From: marty684@...

To: everything-list@...

Sent: Saturday, October 10, 2009 7:30 PM

Subject: Re: The seven step series

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.

 

 

 

----- Original Message -----

From: jamikes@...

To: everything-list@...

Sent: Saturday, October 10, 2009 3:47 PM

Subject: Re: The seven step series

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

(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.

 

John M

On Fri, Oct 9, 2009 at 12:00 PM, Bruno Marchal <marchal@...> 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/



--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

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 <marchal@...> 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/

--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

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 <marchal@...> 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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Brent Meeker-2]

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.

>
> 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?

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 <marchal@...
>>> <mailto:marchal@...>> 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/~marchal/ <http://iridia.ulb.ac.be/%7Emarchal/>
>>
>>
>>
>>
>>
>>
>
> http://iridia.ulb.ac.be/~marchal/ <http://iridia.ulb.ac.be/%7Emarchal/>
>
>
>
> t?hl=en
> -~----------~----~----~----~------~----~------~--~---
>

--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

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.

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.

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 <marchal@...

<marchal@...>> 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/~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/

--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Brent Meeker-2]

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 <marchal@...
>>>>> <mailto:marchal@...>
>>>>> <mailto:marchal@...>> 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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Rex Allen]

On Tue, Nov 10, 2009 at 1:29 PM, Brent Meeker <meekerdb@... wrote:
>
> 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."

I would think that it's pretty much a given that out of all possible
computations, we surely will be able to find some way of representing
physics, the brain, and the contents of conscious experience.

If we can't find some way to symbolically/logically represent these
things...what would that mean?  Wouldn't it mean that we ourselves
aren't capable of grasping them?

So, I don't think I see the significance of success in this
project...I would think that success in finding some
logico-mathematical representation of physics and the rest is the
expected outcome, and that conclusive failure would be big news.

So with computationalism, you can't see beneath the substitution level
to the underlying "processor" substrate of what really exists.  The
conscious experience that results from the computation doesn't have to
reveal anything about the nature of the computer...below the
substitution level could be neurons, transistors, falling dominoes,
dust clouds (a la Egan), numbers, platonic objects, alien matter
existing in some alternate universe, Wang's Carpet (Egan again),
ROCKS...basically anything capable of supporting computation...who
knows?  It would all look the same to us above the substitution level,
right?

If we were to go with Bruno's proposal, wouldn't it be because a
substrate of platonically existing numbers seemed like a more
plausible substrate than a contingently existing physical universe of
matter and energy and laws which sprang from...nothing?  Has existed
eternally?  What?

--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

On 10 Nov 2009, at 19:29, Brent Meeker wrote:

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."

Hmm... The seventh step comes after six other steps. I think you confuse UDA and Tegmark or Egan speculation on the mathematical nature of physics. But when we assume comp, the physical appearance cannot be describe by *any* computation a priori: it *has* to be retrieve from all computation. Roughly speaking, if we are universal machine, we do belong to an infinity of computation, and matter, or anything below our substitution level, has to be described by "all computations". It is an open problem if that sum converge toward something we could describe by "one" computation. It is the whole point of the reasoning. It is "theorem" in the comp theory that matter emerges from all computations. From this you can prove that comp implies the non-cloning of any piece of matter, like it proves the existence of a strong form of indeterminacy, etc. 

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?

Right. There is a vocabulary problem about what is a function, and unfortunately english speaker and french speaker have different conventions, and sometimes I slip from one to other, and this does not help. Usually a function from N to N is supposed to be defined on all element of N. And thus a computable function will have an algorithm which does stop on all of its input.

But the Kleene diagonalization shows that there is no computable list of all computable functions, so if a language is universal, it means that the computable functions can only belong to a list of something else. That something else are called partial computable function: they are allowed to be not necessarily define on some natural number. So to get ALL functions, in some computable way, we have to take something larger: all partial functions, and to get all execution of all algorithm, we will have to dovetail, and from the first person point of view, there is an emerging continuum of computations, and it plays the role of the background roots of the physical laws, below our substitution level.

The physical world is not just a mathematical space among mathematical spaces, it is really a sort of summary of the whole border of the whole set of "mathematical spaces" as seen by mean universal machines. That the laws of physics seems computable is a mystery now.

I am just showing that the comp theory reduces the mind-body problem to a pure arithmetical (or combinatorial, ...) body problem.

Bruno

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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

On 11 Nov 2009, at 08:48, Rex Allen wrote:

>
> On Tue, Nov 10, 2009 at 1:29 PM, Brent Meeker  
> <meekerdb@... wrote:
>>
>> 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."
>
> I would think that it's pretty much a given that out of all possible
> computations, we surely will be able to find some way of representing
> physics, the brain, and the contents of conscious experience.
>
> If we can't find some way to symbolically/logically represent these
> things...what would that mean?  Wouldn't it mean that we ourselves
> aren't capable of grasping them?
>
> So, I don't think I see the significance of success in this
> project...I would think that success in finding some
> logico-mathematical representation of physics and the rest is the
> expected outcome, and that conclusive failure would be big news.
>
> So with computationalism, you can't see beneath the substitution level
> to the underlying "processor" substrate of what really exists.  The
> conscious experience that results from the computation doesn't have to
> reveal anything about the nature of the computer...below the
> substitution level could be neurons, transistors, falling dominoes,
> dust clouds (a la Egan), numbers, platonic objects, alien matter
> existing in some alternate universe, Wang's Carpet (Egan again),
> ROCKS...basically anything capable of supporting computation...who
> knows?  It would all look the same to us above the substitution level,
> right?

No, as i said to Brent, comp says exactly what is below our  
substitution level: all computations. If our consciousness supervenes  
on state S, it means we have to take all computations going through  
state S.
If we look below our computational substitution level, and find a  
computation, like in classical physics, then we know that either we  
are not machine, or that we are in some simulation (and this has  
probability zero from our first person perspective, so that if we see  
classical computable laws, from our first person perspective we can no  
more be machine). Here, of course the quantum data confirms that we  
could be machine. QM is an ally of digital mechanism. If the physical  
truth was classical physics, UDA would be a proof that we are not  
digital machine.


>
> If we were to go with Bruno's proposal, wouldn't it be because a
> substrate of platonically existing numbers seemed like a more
> plausible substrate than a contingently existing physical universe of
> matter and energy and laws which sprang from...nothing?  Has existed
> eternally?  What?

I agree with you. A physical universe is a bit like a creationist  
concept, it does not explain neither consciousness nor matter. But  
with comp, the point is that it is not a proposal, but a logical  
consequence, if I may insist. It is the UDA point.

Bruno

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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Brent Meeker-2]

Rex Allen wrote:

> On Tue, Nov 10, 2009 at 1:29 PM, Brent Meeker <meekerdb@... wrote:
>  
>> 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."
>>    
>
> I would think that it's pretty much a given that out of all possible
> computations, we surely will be able to find some way of representing
> physics, the brain, and the contents of conscious experience.
>  

But it's the "picking out" that's problem.  That's the generic problem
with the everything-theories.  Sure the UD generates all possible
strings and physics must be in there somewhere - so what.  Tegmark
hypothesizes all possible mathematical structures exist - so yeah
physics must be in there too.

> If we can't find some way to symbolically/logically represent these
> things...what would that mean?  Wouldn't it mean that we ourselves
> aren't capable of grasping them?
>
> So, I don't think I see the significance of success in this
> project...I would think that success in finding some
> logico-mathematical representation of physics
IF you can *find* it among all the detritus.

> and the rest is the
> expected outcome, and that conclusive failure would be big news.
>
> So with computationalism, you can't see beneath the substitution level
> to the underlying "processor" substrate of what really exists.  The
> conscious experience that results from the computation doesn't have to
> reveal anything about the nature of the computer...below the
> substitution level could be neurons, transistors, falling dominoes,
> dust clouds (a la Egan), numbers, platonic objects, alien matter
> existing in some alternate universe, Wang's Carpet (Egan again),
> ROCKS...basically anything capable of supporting computation...who
> knows?  It would all look the same to us above the substitution level,
> right?
>
> If we were to go with Bruno's proposal, wouldn't it be because a
> substrate of platonically existing numbers seemed like a more
> plausible substrate than a contingently existing physical universe of
> matter and energy and laws which sprang from...nothing?  Has existed
> eternally?  What?

Platonic existence seems like a very thin concept to me and it's not
very plausible (to me) that it can provide the ontology of the
universe.  I see numbers part of the description.  That the universe
sprang from nothing is a going theory in cosmogony supported by the
observation that whatever conserved quantities are evaluated, energy,
momentum, charge, entropy,..., the total for the universe comes out
zero.  The philosophical difference that seems to divide people is that
some are happy to accept that some things are contingent and others feel
it better to hypothesize infinities in order to secure determinism.

Brent

--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Brent Meeker-2]

Bruno Marchal wrote:

>
> On 10 Nov 2009, at 19:29, Brent Meeker wrote:
>
>
>>>
>> 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."
>
>
> Hmm... The seventh step comes after six other steps. I think you
> confuse UDA and Tegmark or Egan speculation on the mathematical nature
> of physics. But when we assume comp,

But it seems there is a shift the meaning of "assume comp" here.  We
start with comp = "Consciousness is something a brain does.  A brain
does a lot of things (metabolizes, takes up space,...) but the thing it
does that produces consciousness is a kind of computation, i.e.
information processing. "  Almost all scientists and philosophers think
that is good hypothesis and one they would assume.  But then it seems
you use comp2 = "We - our stream of consciousness - IS a computation
that exists in the Platonic sense."  This seems slightly different.

> the physical appearance cannot be describe by *any* computation a priori:
But the main evidence for the comp hypothesis is that physics is so
successfully described by computations.


> it *has* to be retrieve from all computation. Roughly speaking, if we
> are universal machine,

But assuming "we are a universal machine" is assuming more than "our
brains do computations and that produces consciousness."

> we do belong to an infinity of computation, and matter, or anything
> below our substitution level, has to be described by "all
> computations". It is an open problem if that sum converge toward
> something we could describe by "one" computation.
If it is proven that it doesn't, would that refute comp2?  Would we be
left with no explanation of the perceived unity of individual consciousness?


> It is the whole point of the reasoning. It is "theorem" in the comp
> theory that matter emerges from all computations. From this you can
> prove that comp implies the non-cloning of any piece of matter, like
> it proves the existence of a strong form of indeterminacy, etc.

What's the non-cloning proof?

>
>
>>>>>
>>>> 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?
>
>
> Right. There is a vocabulary problem about what is a function, and
> unfortunately english speaker and french speaker have different
> conventions, and sometimes I slip from one to other, and this does not
> help. Usually a function from N to N is supposed to be defined on all
> element of N. And thus a computable function will have an algorithm
> which does stop on all of its input.
> But the Kleene diagonalization shows that there is no computable list
> of all computable functions, so if a language is universal, it means
> that the computable functions can only belong to a list of something
> else. That something else are called partial computable function: they
> are allowed to be not necessarily define on some natural number. So to
> get ALL functions, in some computable way, we have to take something
> larger: all partial functions, and to get all execution of all
> algorithm, we will have to dovetail,

Thanks, I did understand, but sometimes I need reassurance that I've
grasped it.

> and from the first person point of view, there is an emerging
> continuum of computations, and it plays the role of the background
> roots of the physical laws, below our substitution level.

But how is the "first person point of view" defined?  Can this theory
tell me how many persons exist at a given time?

Brent

>
> The physical world is not just a mathematical space among mathematical
> spaces, it is really a sort of summary of the whole border of the
> whole set of "mathematical spaces" as seen by mean universal machines.
> That the laws of physics seems computable is a mystery now.
>
> I am just showing that the comp theory reduces the mind-body problem
> to a pure arithmetical (or combinatorial, ...) body problem.
>
> Bruno
>
>
> 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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

On 11 Nov 2009, at 19:52, Brent Meeker wrote:

>
> Bruno Marchal wrote:
>>
>> On 10 Nov 2009, at 19:29, Brent Meeker wrote:
>>
>>
>>>>
>>> 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."
>>
>>
>> Hmm... The seventh step comes after six other steps. I think you
>> confuse UDA and Tegmark or Egan speculation on the mathematical  
>> nature
>> of physics. But when we assume comp,
>
> But it seems there is a shift the meaning of "assume comp" here.  We
> start with comp = "Consciousness is something a brain does.  A brain
> does a lot of things (metabolizes, takes up space,...) but the thing  
> it
> does that produces consciousness is a kind of computation, i.e.
> information processing. "  Almost all scientists and philosophers  
> think
> that is good hypothesis and one they would assume.  But then it seems
> you use comp2 = "We - our stream of consciousness - IS a computation
> that exists in the Platonic sense."  This seems slightly different.

When some materialists, like some neuroscientists, assume the brain  
does computations at some high level, like with neuronal processing. I  
am not sure all are aware of the digitality assumption needed for  
making sense to the word computation.
But if we assume the brain obeys to the physical laws, then we assume  
comp already, given that the physical laws are, as far as we know,  
Turing emulable.

Comp is NOT the hypothesis that "consciousness is something brain  
does". This is not even a precise definition of comp, given that  
strictly speaking we don't know what a brain is, nor what  
consciousness. But that's ok, because comp is very close to that,  
perhaps equivalent deending of what you mean by "consciousness is  
something brain does".

Comp is two things: "yes doctor", which means: there is a level such  
that I survive (or feel nothing) when may brain is substitute for  
digital part made at that level". This does not use any neither a  
definition of brain, except it is something which can be described by  
some machine (but not necessarily the one in the skull), nor any idea  
of consciousness, above what we can ask to a doctor (will I make it  
Doc?).

And then I believe you did understand the seventh step. In a "concrete  
universe with a UD running in it (even materially), well, if my comp  
state is S, my future subjective experience is given by a sum on all  
computations going through S. So if the laws of physics still applies,  
they have to be recover from the mathematics of computations, which is  
a branch of math. In physics the notion does not admit definition  
which is different from the one by mathematicians. And quantum  
computation, actually a mathematical notion, is already close to the  
idea of sum on infinities of computations.

After the seven step, you can still invoke, to save both comp and  
materialist, that we live in a universe which is too little for a  
universal dovetailing to be executed integrally or on some large  
portion.

That is why there is an eight step, which shows that the universal  
machine (that we all provably are, even if comp is false) cannot, once  
comp is true, make the difference, for a short time on which bear the  
probabilities, distinguish between any implementations made below its  
substitution level, notably between "physically implemented" or  
"arithmetically implemented". Step 8 shows that consciousness is not  
produced by the brain. Consciousness is "produced" by the arithmetical  
relation (or XYZ-ical relation with XXX being a first order  
specification of any universal system.
In that case the move to a little universe can not work, and reality,  
or more aptly the realities (corresponding to each points of view)  
have to emerge from the XYZ-relations.

I don't need any more "platonic reality" than I need to explain what  
is Church thesis, what is a universal machine or number, etc. No book  
of physics assume less.





>
>> the physical appearance cannot be describe by *any* computation a  
>> priori:
> But the main evidence for the comp hypothesis is that physics is so
> successfully described by computations.

Not necessarily. If you take Old QM (SWE + Collapse), the collapse of  
the wave, and its result,  IS NOT the output of a computation.
If you take the "new" QM, which assumes comp, the physical appearance  
is already described by infinities of computations. The only problem  
is that by assuming comp and taking it seriously into account (meaning  
taking the first and third person distinction into account) the UDA-
MGA argument shows that the SWE has to be derived from comp, that is  
from number theory (or the XYZ-theory).

I take XYZ = Arithmetic, just because Arithmetic is already universal,  
and is already taught in high school.

As I said, it would help if you could say where in SANE04 you have a  
problem. I will send to the list a new version of MGA quite close to  
the one already sent. (MGA is just sketched in SANE04).


>
>
>> it *has* to be retrieve from all computation. Roughly speaking, if we
>> are universal machine,
>
> But assuming "we are a universal machine" is assuming more than "our
> brains do computations and that produces consciousness."

No, it is less. I can prove to you that you are at least a universal  
machine.
Comp is that you are Turing emulable, and this means that you are not  
MORE than a universal machine.
Universal here is used in respect of computability, or emulability,  
not in the sense of provability or anything else.


>
>> we do belong to an infinity of computation, and matter, or anything
>> below our substitution level, has to be described by "all
>> computations". It is an open problem if that sum converge toward
>> something we could describe by "one" computation.
> If it is proven that it doesn't, would that refute comp2?

Why? Not necessarily. Unless you mean that all physical result is  
given by that "one" computation, which is already not the case with  
"new QM".



> Would we be
> left with no explanation of the perceived unity of individual  
> consciousness?

Consciousness is when (universal) machine bets (instinctively at  
first) on "transcending realities", like their parents, their local  
neighborhood (to begin with), up to things like  "physical universe",  
"Gods" or the Number Realm.
It is always hypothetical. It is not always consciously "hypothetical".

>
>
>> It is the whole point of the reasoning. It is "theorem" in the comp
>> theory that matter emerges from all computations. From this you can
>> prove that comp implies the non-cloning of any piece of matter, like
>> it proves the existence of a strong form of indeterminacy, etc.
>
> What's the non-cloning proof?

UDA1--7 is enough. To predict the exact state of any object, you have  
to run the whole dovetailer. This is not possible, so the exact state  
of any piece of matter, although it may be simulated quickly with a  
big accuracy, would need the whole running of the UD to be emulated.

>
>>
>>
>>>>>>
>>>>> 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?
>>
>>
>> Right. There is a vocabulary problem about what is a function, and
>> unfortunately english speaker and french speaker have different
>> conventions, and sometimes I slip from one to other, and this does  
>> not
>> help. Usually a function from N to N is supposed to be defined on all
>> element of N. And thus a computable function will have an algorithm
>> which does stop on all of its input.
>> But the Kleene diagonalization shows that there is no computable list
>> of all computable functions, so if a language is universal, it means
>> that the computable functions can only belong to a list of something
>> else. That something else are called partial computable function:  
>> they
>> are allowed to be not necessarily define on some natural number. So  
>> to
>> get ALL functions, in some computable way, we have to take something
>> larger: all partial functions, and to get all execution of all
>> algorithm, we will have to dovetail,
> Thanks, I did understand, but sometimes I need reassurance that I've
> grasped it.

Tanks for telling. I think many does not grasp it, or does grasp it  
since a longer time.
I will sum up, but people would help by telling if they have grasped  
Cantor diagonalization proof of the non enumerability of N^N. Then I  
can explain with more assurance  Kleene very similar, yet completely  
different result and their consequence.

People should reread perhaps the "coffee bar machine" thread, or the  
"combinator" thread, or learn some programming language to familiarize  
themselves with example of universal system. But all what I need does  
not depend on any particular system. I refer to the numbers because  
everyone know them, but once a universal system is very simple, it  
becomes rather long and tedious to show that is universal. There is an  
hard pedagogical dilemma here.



>
>> and from the first person point of view, there is an emerging
>> continuum of computations, and it plays the role of the background
>> roots of the physical laws, below our substitution level.
>
> But how is the "first person point of view" defined?  Can this theory
> tell me how many persons exist at a given time?


In the UDA, the first person view is defined very simply by the  
personal memory, or the personal diary of the teleported candidate.  
The key is that such a memory is annihilated and reconstituted when  
the experiencer is annihilated or reconstituted. (Which explain what  
the first person will not "feel the split" (to talk like Everett).
The third person description is given by what is not annihilated, like  
a local observer, or eventually the number theoretical relations  
themselves.

IN QM, roughly speaking the third person view can be described by  
Everett universal wave, or Deutsch (Heisenbergian) universal matrix.  
And the first person views are given by what the machine observer  
memories in each branch of that differentiating waves.

But with comp, eventually the third person description is given by the  
relation between number (and definable with + and *), and the "Everett  
wave" is retrievable as a first person (plural) point of view.

Thanks to Everett QM, we have very strong evidence, assuming comp,  
that we are multiple (infinities) but share deep and long  
computations. QM saves comp from solipsism, but matter, well Matter,  
does not go through.

That's a good thing because no one really can defined it, nor provide  
evidence that it exists, beyond a naïve extrapolation of the boolean  
mind from its local neighborhood.
And once you assume Matter, the mind body problem become non  
resoluble, you can even get divorce between human and exact science,  
leading to people having no idea what is going on, yet having all  
means of destruction/creation at their disposal ... Brrr...

Bruno


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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

On 11 Nov 2009, at 19:52, Brent Meeker wrote:

But how is the "first person point of view" defined?  Can this theory
tell me how many persons exist at a given time?

I come back on this. The question "how many persons?" is a question which remains very hard in the mechanist theory.

To answer it, let me ask you a question. Suppose that old fashioned time travel is possible, and that Brent Meeker of the future decides to travel in the past, and to say hello to the younger Brent Meeker. They met in a kitchen and drink coffee. Nobody else is present in the kitchen. How many person are there in the kitchen? What would you say?

I think this: if you answer one, then I will tend to say that there is only one person in the multiverse, but it manifests itself in different overlapping contexts. If you answer "two", then I will tend to say that there are an infinity of persons in the multiverse.

What do you think?

Note that in UDA, I use a definition of first person which identify a person with its personal memory, and so where many different persons can exist.

But in AUDA, I use a more mathematical definition which eventually identify all persons. Then they can differentiate through a mixture of amnesia (they forget that they are the "universal person"), and personal memories (which they will use as self-identification means).

Bruno

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@....
To unsubscribe from this group, send email to everything-list+unsubscribe@....
For more options, visit this group at http://groups.google.com/group/everything-list?hl=.