Hi Mirek,

## Advertising

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