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.


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



You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 

Reply via email to