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