- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Bruno Marchal <marchal.domain.name.hidden>

Date: Thu, 31 Jan 2008 14:56:26 +0100

Hi Mirek,

Le 30-janv.-08, à 13:42, Mirek Dobsicek a écrit :

*>
*

*>
*

*> Hi Bruno and everybody,
*

*>
*

*>>> I
*

*>>> hope to send my comments and/or 'OK' sign :-) on Monday.
*

*>>
*

*>> Take it easy. There is no deadline on the list.
*

*>
*

*> Making a declaration helps me to get things done. Yet I'm late.
*

*> Whenever
*

*> you see such sentences in my posts, you can skip it, they are mostly
*

*> for
*

*> me :-)
*

Am I suppose to skip this one too? :)

*>
*

*> ---------------
*

*> I'll try to write a summary in my own words. Let's see how much I did
*

*> understand.
*

*>
*

*> Prepositions:
*

*> A .... finite alphabet
*

*> A* .... finite words over A (it is enumerable, moreover effectively
*

*> enumerable)
*

*> L ..... a language over A.
*

*> E .... a subset of A*, a set of valid expressions in L (obviously, it
*

*> is at least enumerable)
*

*> M ..... a machine which understands to L
*

*> f ..... a total function from N to N.
*

*>
*

*> Goal: I want to develop a universal language L which describes all
*

*> and only all functions f. Given an expression from E, M computes the
*

*> result in finite time. Given the restrictions on L, the result is a
*

*> number and nothing else.
*

*>
*

*> The set of all functions f from N to N is not enumerable (by Cantor's
*

*> diagonal). Thus there is no bijection to E. Thus, I have to find a
*

*> smaller set of functions. I will call this set a set of computable
*

*> functions, C. Inevitably, this is computability by definition, by
*

*> definition of L. So L should be 'really good' in order to encompass as
*

*> much functions f from N to N as possible.
*

*>
*

*>
*

*> Now, I think of a bijection between E and C.
*

*> 0 --- E_0 ~ f_0
*

*> 1 --- E_1 ~ f_1
*

*> 2 --- E_2 ~ f_2
*

*> 3 --- E_3 ~ f_3
*

*> ....
*

*> ....
*

*>
*

*> Since E are efficiently enumerable, C are efficiently enumerable ...
*

I guess you want to say "effectively enumerable". Typo error.

*> ... as well. Yes, it might happen that f_i = f_j for i != j, but is
*

*> does not
*

*> matter as long as all unique f_i are in the enumeration.
*

*>
*

*> Time for the Kleene diagonal argument. Opps, a language L that I dreamt
*

*> of does not exist. I have to relax from the condition that M on E_i
*

*> always return a number in a finite time. Well, what to return if not a
*

*> number ... nothing -> M experiences an infinite loop.
*

*>
*

*> What a world, ok, my language has to describe total functions from N to
*

*> N and as well as strict partial functions from N to N.
*

OK.

*> And it is clear
*

*> that I cannot know whether E_i corresponds to a total function or a
*

*> strict partial function.
*

Clear for you, apparently. Is it clear for everybody? This follows from

the Diagonal argument applied on the "programs" in L.

*> f' stands for any function descriable by L.
*

*>
*

*> 0 --- E_0 ~ f'_0
*

*> 1 --- E_1 ~ f'_1
*

*> 2 --- E_2 ~ f'_2
*

*> 3 --- E_3 ~ f'_3
*

*> ....
*

*> ....
*

*>
*

*> N, E and C are enumerable, moreover obviously effectively enumerable.
*

*> Any subset of C is at least enumerable. A subset of C corresponding to
*

*> total functions is no effectively enumerable. It cannot be.
*

*>
*

*> Well, a language L which describes both total and strict partial
*

*> functions and hereby defines a set of computable functions is not
*

*> refuted by Kleene's diagonal.
*

OK. I guess that you see now that is by allowing a universal machine to

do infinite task which makes CT consistent (possible). OK?

*>
*

*> It is not obvious to me how strong sort of evidence that universal L
*

*> exists, it is to survive Kleene's diagnonal. Droping an apple on the
*

*> floor is in favor of Newton's law but not very convincing :-)
*

Because the diagonal argument is *the* tool for demolishing the idea

that such or such set is universal or complete, but then it does not

work on language like Lambda, Turing, etc. This entails a strong form

of incompleteness.

Then, Judson Webb, argued that Godel's incompleteness confirmed such

incompleteness, and thus CT, and thus Mechanism, Comp ...

*>
*

*> Oh, now I realize that my question is actually weird. Since the set of
*

*> computable functions is defined by L, and L is said to be universal if
*

*> it describes exactly these functions - it is simple to develop a
*

*> trivial
*

*> L -> it defines a set of computable functions ... and of course
*

*> universal L exists.
*

OK, but this is due to your "definition" above of the set of computable

functions. Recall that we do have some starting intuition of what is an

intuitively computable functions. Church thesis is the assertion that

LAMBDA (or FORTRAN, or whatever programming system you love) does

capture that starting intuition. CT is both philosophical (linking an

epistemic concept with a mathematical class of functions) and

scientific (refutable in Popper sense: CT would be refuted in case we

find a clearly humanly computable function which would be uncomputable

in Lambda (and thus in Turing, Java, or any modern all-purpose

computer, etc.).

*>
*

*> In this sence a universal language L always exists. So I write it
*

*> rather
*

*> like this:
*

*>
*

*> If we develop many sufficiently different programming languages and
*

*> they
*

*> turn out to be all equivalent, it might convince me that the set of
*

*> 'computable functions' is fixed.
*

Yes, and that is the case. I guess (from your thesis) that you are very

well aware that the quantum computer itself does not compute more

functions than FORTRAN, LISP, JAVA, PYTHON, Billiard Ball, Games of

Life, etc.

*> Although, written like this I can think
*

*> of educated (math) people who will tell me: This is all you have????
*

*>
*

*> So, what are like 2-3 most direct consequences of CT which make CT to
*

*> seem rock-solid? Here I assume that CT basically says that the set of
*

*> functions descriable by the lambda calculus is all what I can ever
*

*> compute.
*

Of course, the power of *evidences* could depend on your own

background. Personally, the fact that the collection of partial

computable functions is closed for the diagonalization procedure seems

to me to be a very powerful reason to believe in CT. Of course it is

not enough, you could try as exercise to build a class of functions

closed for the diagonalization, yet not Turing-universal!. The evidence

comes from the empirical facts that all attempts have lead to the same

class, *together* with the fact that that the diagonal does not lead

outside the defined set, + some particularly good analysis of what is a

computation, mainly, imo, like the Turing's arguments, Church's one,

Emil Post's one.

*> -------------
*

*> Regarding points 3)-5) of your summary, I am lost on terms such as
*

*> Absolute ontic TOE, Observer Moments, Aristotelian principles, Machine
*

*> theology, ...
*

All right, all right .... that was an anticipation, at least relatively

to the current thread. We will come back on this, but to give you some

food I could say this:

Absolute Ontic Toe: that concerns the (minimal) ontological commitment,

i.e. what I will take as existing independently of me, or (because this

is just a question of phrasing) the set of sentences that I consider

being true independently of me or of any observer whatsoever.

I can explain that on,ce we accept comp (if only for the sake of the

conversation) then ontically we need not more than the number

theoretical truth (this is perhaps not obvious, but it should be

obvious that this follows from the UD Argument).

Observer Moment is a key informal "everything-list" concept. It has

been introduced by Nick Bostrom in together with the notion of

Self-Sampling Assumption, but the term is defensible in the comp

context, with the condition to be clear on the distinction between

states and the first person perspective. We can go back on this: I

argue that if comp is true, then the physical world in an internal view

of number theory as seen from inside. I like to paraphrase Kronecker:

God created the numbers, all the rest are inventions by ... numbers.

Aristotelian principle: well, concerning matter it is just the quite

common idea that there is a substancial world, made of "matter" ... I

call that sometimes weak materialism: the belief in a notion of primary

matter. Physicalism is very close to that idea: the dea that physics is

the fundamental science.

Machine theology: once you assume Church's thesis, it is easy to show

that most truth ABOUT machines can be written as relations between

numbers. Those relations are either true or false. The theology ABOUT

machine M is the set of all true relations among numbers which can be

interpreted as relations about the machine (albeit not necessarily so

by the machine). Due to the incompleteness phenonemon, this set is

different of the set of provable (by M) relations among numbers

(including again those relations bearing on the machine). In a

nutshell: theology is the science of truth (about machines, and other

entities), science itself corresponds to the provable relations. See my

Plotinus paper for more. We have to go back on this in due time.

*> -------------
*

*> I wrote down a list of short-term goals on what I would like to have
*

*> some background/knowledge with a help from this list:
*

*>
*

*>
*

*> 1\ I saw somewhere a sentence saying approximately this:
*

*> ".... so universe is performing a computation. Is then universe a big
*

*> computer? No."
*

*>
*

*> I would like to know in a broad sense what it tries to say a why one
*

*> shoud rather accept it or reject.
*

*>
*

*> 2\ Bruno, you recently wrote that you do not agree with Wolfram's
*

*> Principle of Computational Equivalence. As I understand to that
*

*> principle, Wolfram says that universe is a big cellular automata. What
*

*> is the evidence that it is unlikely this way?
*

The shortest answer is that you cannot simulate "in real time" a

quantum computer with a classical cellular automata. OK?

Also: what does that mean that the universe is a big cellular automata?

Now the main reason to find that unlikely is that such a vison is based

on the idea that pour consciousness and experiences are related to the

actual running of a machine/brain. This is shown just epistemologically

unlikely through the UD Argument.

Your points 1) and 2) are related. I maintain that if comp is true,

then the physical or observable "universe" cannot be a computational

object: i.e. it cannot be the output of a program nor can it be related

to the running of a special program, except in some very weak sense.

Why? that is really all what the UDA is about. And then the interview

of the lobian machine will consist in making a rough, (but highly non

trivial) arithmetical translation of UDA in the language of the

(universal, even Lobian) machine. A Loebian machine is mainly an

enlightened machine: a universal machine which knows that it (she ...)

is a universal entity.

The reason why, IF we are digitalizable machines, then the physical

world cannot a priori be a machine, nor a product of a machine, comes

from the fact that we cannot know which computations does actually go

through our local states, and there is an infinity of such

computations. To predict our local and relative "future" we have to

take into account *all* such computations. Comp predicts that if I

observe myself at a level below the level of substitution (where I

survive substitution by comp), then I will observe the trace of many

parallel computations. I take QM (without collapse) as a confirmation

of this.

Did you grasp the first-person indeterminacy? Are you ok with the idea

that comp makes us duplicable, at some level, and if we are duplicable

(at that level) then if we are actually duplicated (copy and

annihilated in Brussels, say, and reconstituted in Sidney and Beijing

(say), do you accept that in Brussels we cannot predict with any

certainty which places we will feel to be there?

I must go and perhaps comment your other post later (about ordinal, I

will have the opportunity to give some effective use of them related to

the notion of universality).

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.domain.name.hidden

To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden

For more options, visit this group at http://groups.google.com/group/everything-list?hl=en

-~----------~----~----~----~------~----~------~--~---

Received on Thu Jan 31 2008 - 08:56:20 PST

Date: Thu, 31 Jan 2008 14:56:26 +0100

Hi Mirek,

Le 30-janv.-08, à 13:42, Mirek Dobsicek a écrit :

Am I suppose to skip this one too? :)

I guess you want to say "effectively enumerable". Typo error.

OK.

Clear for you, apparently. Is it clear for everybody? This follows from

the Diagonal argument applied on the "programs" in L.

OK. I guess that you see now that is by allowing a universal machine to

do infinite task which makes CT consistent (possible). OK?

Because the diagonal argument is *the* tool for demolishing the idea

that such or such set is universal or complete, but then it does not

work on language like Lambda, Turing, etc. This entails a strong form

of incompleteness.

Then, Judson Webb, argued that Godel's incompleteness confirmed such

incompleteness, and thus CT, and thus Mechanism, Comp ...

OK, but this is due to your "definition" above of the set of computable

functions. Recall that we do have some starting intuition of what is an

intuitively computable functions. Church thesis is the assertion that

LAMBDA (or FORTRAN, or whatever programming system you love) does

capture that starting intuition. CT is both philosophical (linking an

epistemic concept with a mathematical class of functions) and

scientific (refutable in Popper sense: CT would be refuted in case we

find a clearly humanly computable function which would be uncomputable

in Lambda (and thus in Turing, Java, or any modern all-purpose

computer, etc.).

Yes, and that is the case. I guess (from your thesis) that you are very

well aware that the quantum computer itself does not compute more

functions than FORTRAN, LISP, JAVA, PYTHON, Billiard Ball, Games of

Life, etc.

Of course, the power of *evidences* could depend on your own

background. Personally, the fact that the collection of partial

computable functions is closed for the diagonalization procedure seems

to me to be a very powerful reason to believe in CT. Of course it is

not enough, you could try as exercise to build a class of functions

closed for the diagonalization, yet not Turing-universal!. The evidence

comes from the empirical facts that all attempts have lead to the same

class, *together* with the fact that that the diagonal does not lead

outside the defined set, + some particularly good analysis of what is a

computation, mainly, imo, like the Turing's arguments, Church's one,

Emil Post's one.

All right, all right .... that was an anticipation, at least relatively

to the current thread. We will come back on this, but to give you some

food I could say this:

Absolute Ontic Toe: that concerns the (minimal) ontological commitment,

i.e. what I will take as existing independently of me, or (because this

is just a question of phrasing) the set of sentences that I consider

being true independently of me or of any observer whatsoever.

I can explain that on,ce we accept comp (if only for the sake of the

conversation) then ontically we need not more than the number

theoretical truth (this is perhaps not obvious, but it should be

obvious that this follows from the UD Argument).

Observer Moment is a key informal "everything-list" concept. It has

been introduced by Nick Bostrom in together with the notion of

Self-Sampling Assumption, but the term is defensible in the comp

context, with the condition to be clear on the distinction between

states and the first person perspective. We can go back on this: I

argue that if comp is true, then the physical world in an internal view

of number theory as seen from inside. I like to paraphrase Kronecker:

God created the numbers, all the rest are inventions by ... numbers.

Aristotelian principle: well, concerning matter it is just the quite

common idea that there is a substancial world, made of "matter" ... I

call that sometimes weak materialism: the belief in a notion of primary

matter. Physicalism is very close to that idea: the dea that physics is

the fundamental science.

Machine theology: once you assume Church's thesis, it is easy to show

that most truth ABOUT machines can be written as relations between

numbers. Those relations are either true or false. The theology ABOUT

machine M is the set of all true relations among numbers which can be

interpreted as relations about the machine (albeit not necessarily so

by the machine). Due to the incompleteness phenonemon, this set is

different of the set of provable (by M) relations among numbers

(including again those relations bearing on the machine). In a

nutshell: theology is the science of truth (about machines, and other

entities), science itself corresponds to the provable relations. See my

Plotinus paper for more. We have to go back on this in due time.

The shortest answer is that you cannot simulate "in real time" a

quantum computer with a classical cellular automata. OK?

Also: what does that mean that the universe is a big cellular automata?

Now the main reason to find that unlikely is that such a vison is based

on the idea that pour consciousness and experiences are related to the

actual running of a machine/brain. This is shown just epistemologically

unlikely through the UD Argument.

Your points 1) and 2) are related. I maintain that if comp is true,

then the physical or observable "universe" cannot be a computational

object: i.e. it cannot be the output of a program nor can it be related

to the running of a special program, except in some very weak sense.

Why? that is really all what the UDA is about. And then the interview

of the lobian machine will consist in making a rough, (but highly non

trivial) arithmetical translation of UDA in the language of the

(universal, even Lobian) machine. A Loebian machine is mainly an

enlightened machine: a universal machine which knows that it (she ...)

is a universal entity.

The reason why, IF we are digitalizable machines, then the physical

world cannot a priori be a machine, nor a product of a machine, comes

from the fact that we cannot know which computations does actually go

through our local states, and there is an infinity of such

computations. To predict our local and relative "future" we have to

take into account *all* such computations. Comp predicts that if I

observe myself at a level below the level of substitution (where I

survive substitution by comp), then I will observe the trace of many

parallel computations. I take QM (without collapse) as a confirmation

of this.

Did you grasp the first-person indeterminacy? Are you ok with the idea

that comp makes us duplicable, at some level, and if we are duplicable

(at that level) then if we are actually duplicated (copy and

annihilated in Brussels, say, and reconstituted in Sidney and Beijing

(say), do you accept that in Brussels we cannot predict with any

certainty which places we will feel to be there?

I must go and perhaps comment your other post later (about ordinal, I

will have the opportunity to give some effective use of them related to

the notion of universality).

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.domain.name.hidden

To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden

For more options, visit this group at http://groups.google.com/group/everything-list?hl=en

-~----------~----~----~----~------~----~------~--~---

Received on Thu Jan 31 2008 - 08:56:20 PST

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:14 PST
*