### Re: Provable vs Computable

from George Levy, 1 Jun 2001: A purely mechanical model no matter how complicated, including random variables, cannot replicate the results generated by Quantum mechanics + probability theory. This is exactly what Bell's inequality implies. In fact Bell proved his inequality using Quantum theory and probability. Therefore Juergens' erector (fr: meccano) set approach using pseudo-random generators, would definitely violate Bell's inequality theorem, and would not be phenomenally or experimentally equivalent to quantum mechanics. I do not agree, of course. Since you keep insisting on this, I suggest you clearly write down all implicit assumptions and why exactly you believe Bell's inequality is not compatible with pseudorandomness and algorithmic TOEs. http://www.idsia.ch/~juergen/everything/html.html http://www.idsia.ch/~juergen/toesv2/

### Re: Provable vs Computable

John and Hal, Bruno and all everythingers, sorry for the delay guys, I was travelling and had lots of work. Bruno, I just scanned your post quickly. It seems to me we are going in the right direction but I shall need time to digest what you wrote. I shall reply to you later Let me first reply to John and Hal because it is the shortest reply. Let's go back to the original Juergens' post [EMAIL PROTECTED] wrote: > Example: a never ending universe history h is computed by a finite > nonhalting program p. To simulate randomness and noise etc, p invokes a > short pseudorandom generator subroutine q which also never halts. The > n-th pseudorandom event of history h is based on q's n-th output bit > q(n) which is initialized by 0 and set to 1 as soon as the n-th element > of an ordered list of all possible program prefixes halts. Whenever q > modifies some q(n) that was already used in the previous computation of > h, p appropriately recomputes h since the n-th pseudorandom event. > > Such a virtual reality or universe is perfectly well-defined. I replied: >Such a universe would violate Bell' inequality theorem. Quantum randomness >cannot be simulated by hidden variables. We have to move beyond >realism..to get a model of objective reality we must first develop a >model of consciousness. A purely mechanical model no matter how complicated, including random variables, cannot replicate the results generated by Quantum mechanics + probability theory. This is exactly what Bell's inequality implies. In fact Bell proved his inequality using Quantum theory and probability. Therefore, Juergens' erector (fr: meccano) set approach using pseudo-random generators, would definitely violate Bell's inequality theorem, and would not be phenomenally or experimentally equivalent to quantum mechanics. Some of his (our) choices are: 1) Quantum mechanics + probability -> Bell's inequality and give up on a mechanical hidden variable, on pseudo random generators, and more generally, on realism. 2) Something else of power equivalent to Quantum mechanics in describing natureGood Luck!!! I do not believe the route to this solution is the erector set technique. Many a 19th and early 20th century physicist has broken a tooth on that bone! George jamikes wrote: George, thanks for your reply, which is almost as convoluted and hard-to-follow as was my question. You wrote: > I am not restricting anything. I am only saying that Juergens has to choose > between violating Bell's inequality theorem and all that this implies, or not > and all that this implies. My stand is that we shouldn't. > George > So ;let me rephrase the question: is your stand that if an imaginary universe would violate eg. Bell's theorem, it should be excluded from consideration as a possibility, - or - we should rather conclude that Bell's theorem (or any other fundemntal "human" rule) has a limited validity and does not cover every possible universe? John

### Re: Provable vs Computable

Dear George: I do not see how the aspect of Juergen's approach he cited at the initiation of this part of the thread causes a dilemma re Bell's inequality. As I understand it the history h is not THE history until the applicable portion of h stops changing. But p and q are both non halting. No part of h may settle in a finite time. So what? The generator q is not in h. The fact that p may recompute virtually any amount of h depending on what happens to q(n) is not a non locality in h but rather a substitution of a new h for the old h. The old h is no longer relevant. However, p itself being global seems to me to allow the violation of Bell's inequality in its universe. My formal system has the same feature as does a UD IMO. As far as I know the violation of Bell's inequality was already well established in our universe. Hal At 5/22/01, you wrote: jamikes wrote: George Levy [EMAIL PROTECTED] wrote Saturday, May 05, 2001 : (SNIP Jurgen's remark about such a universe whatever, my remark is not topical, rather principle:) Such a universe would violate Bell' inequality theorem. Quantum randomness cannot be simulated by hidden variables. We have to move beyond realism..to get a model of objective reality we must first develop a model of consciousness. George Can you restrict a universe according to its compliance with or violation of a theory, no matter how ingenious, or vice versa? Are WE the creators who has to perform according to some rules/circumstances of human logic or computability? John Mikes I am not restricting anything. I am only saying that Juergens has to choose between violating Bell's inequality theorem and all that this implies, or not and all that this implies. My stand is that we shouldn't. George

### Re: Provable vs Computable

George, thanks for your reply, which is almost as convoluted and hard-to-follow as was my question. You wrote: I am not restricting anything. I am only saying that Juergens has to choose between violating Bell's inequality theorem and all that this implies, or not and all that this implies. My stand is that we shouldn't. George So ;let me rephrase the question: is your stand that if an imaginary universe would violate eg. Bell's theorem, it should be excluded from consideration as a possibility, - or - we should rather conclude that Bell's theorem (or any other fundemntal human rule) has a limited validity and does not cover every possible universe? John

### Re: Provable vs Computable

jamikes wrote: George Levy [EMAIL PROTECTED] wrote Saturday, May 05, 2001 : (SNIP Jurgen's remark about such a universe whatever, my remark is not topical, rather principle:) Such a universe would violate Bell' inequality theorem. Quantum randomness cannot be simulated by hidden variables. We have to move beyond realism..to get a model of objective reality we must first develop a model of consciousness. George Can you restrict a universe according to its compliance with or violation of a theory, no matter how ingenious, or vice versa? Are WE the creators who has to perform according to some rules/circumstances of human logic or computability? John Mikes I am not restricting anything. I am only saying that Juergens has to choose between violating Bell's inequality theorem and all that this implies, or not and all that this implies. My stand is that we shouldn't. George

### Re: Provable vs Computable

Well I thought the whole point was to restrict the universe (that we're in) by the anthropic principle. But if the anthropic principle is to meant to include all intelligent beings, then some theory will be necessary to say in what respects the universe could differ and still produce intelligent beings. Have you read Tegmark's paper, quant-ph/9907009v2 10 Nov 1999, which shows that entangled quantum probabilities are not necessary for consciousness - only ordinary randomness. Brent Meeker As far as the laws of mathematics refer to reality, they are not certain, and as far as they are certain, they do not refer to reality. -- Albert Einstein On 22-May-01, George Levy wrote: jamikes wrote: George Levy [EMAIL PROTECTED] wrote Saturday, May 05, 2001 : (SNIP Jurgen's remark about such a universe whatever, my remark is not topical, rather principle:) Such a universe would violate Bell' inequality theorem. Quantum randomness cannot be simulated by hidden variables. We have to move beyond realism..to get a model of objective reality we must first develop a model of consciousness. George Can you restrict a universe according to its compliance with or violation of a theory, no matter how ingenious, or vice versa? Are WE the creators who has to perform according to some rules/circumstances of human logic or computability? John Mikes I am not restricting anything. I am only saying that Juergens has to choose between violating Bell's inequality theorem and all that this implies, or not and all that this implies. My stand is that we shouldn't. George Regards

### Re: Provable vs Computable

George Levy [EMAIL PROTECTED] wrote Saturday, May 05, 2001 : (SNIP Jurgen's remark about such a universe whatever, my remark is not topical, rather principle:) Such a universe would violate Bell' inequality theorem. Quantum randomness cannot be simulated by hidden variables. We have to move beyond realism..to get a model of objective reality we must first develop a model of consciousness. George Can you restrict a universe according to its compliance with or violation of a theory, no matter how ingenious, or vice versa? Are WE the creators who has to perform according to some rules/circumstances of human logic or computability? John Mikes

### Re: Provable vs Computable

Dear Juergen: I am not so much interested in provability as I am in whether or not the noise in a universe's evolution is pseudorandom or random and forging an Everything that was as free of information [selection] as possible. I try to use incompleteness in various forms to show that as far as an individual universe is concerned the noise comes from outside that universe. I believe that many proposals on this list are more in agreement than we might at first glance think. Below I use the approach of producing numbers using the null set to try to demonstrate this. Using the symbol * to represent the null set and {} to represent sets with elements: horizontal the on this page isomorphically isomorphic linked anisomorphic links string * :::* =0 {*} = 1 {*,{*}} = 10 {*,{*},{*,{*}}} = 11 : : : : : : = 11001110111...0110 || active and inactive page vertical isomorphic links to this string : : = 11100110111...0011 || active and inactive page vertical isomorphic links to this string : : etc. The page horizontal isomorphic links on the right hand side are the usual ones. The page vertical isomorphic links are the ones I have used in my model. Each of these vertical isomorphic links [there can be more than one per string] uses a portion of the string to which it links to define its self contained FAS. The rest of the string determines the associated state of the vertical isomorphism. The current state of a vertical isomorphism is the active link for that isomorphism. All inactive links are either past or future states of isomorphisms. The self contained FAS of a particular vertical isomorphism determines which links are acceptable immediate successor states of that isomorphism. Depending on the nature of the FAS there could be more than one acceptable immediate successor state for that isomorphism. The symbol ::: indicates that the isomorphism tree structure - The Everything - vanishes upon occasion and the anisomorphic null set - The Nothing - resumes. This is the E/N alternation. Neither the anisomorphic null set nor the isomorphism tree since they both contain no information can internally address the unavoidable question of their own durability. This bilateral incompleteness drives the E/N alternation. The alternation since it destroys any record of the previous mix of active/inactive vertical isomorphic links causes a new random active/inactive mix each time the isomorphism tree resumes. This avoids a selected structure to The Everything. In order for a vertical isomorphic link to transfer to another string both the current link and an acceptable successor link must be simultaneously active. The transfer inactivates the prior link. Vertical isomorphic links driven active or inactive by the E/N alternation absent an active acceptable successor is simply in stasis. For a transfer to take place both the current and acceptable successor link must be simultaneously active. It is the transfer that is an event to an isomorphism. Are UD's or other such string generating machines vertical isomorphic links? I think so if I understand them correctly. Simply concatenate all the output strings of a UD so that successor vertical link shifts are just based on very localized regions of the overall string. I also think this process is

### Re: Provable vs Computable

Dear Juergen: My little isomorphism tree did not transmit very well. The second column heading should read: horizontal on this page isomorphic links The third should read: the isomorphically linked string All the binary strings should be under the third column. Yours Hal * :::* =0 {*} = 1 {*,{*}} = 10 {*,{*},{*,{*}}} = 11 : : : : : : = 11001110111...0110 || active and inactive page vertical isomorphic links to this string : : = 11100110111...0011 || active and inactive page vertical isomorphic links to this string : : etc. The page horizontal isomorphic links on the right hand side are the usual ones. The page vertical isomorphic links are the ones I have used in my model. Each of these vertical isomorphic links [there can be more than one per string] uses a portion of the string to which it links to define its self contained FAS. The rest of the string determines the associated state of the vertical isomorphism. The current state of a vertical isomorphism is the active link for that isomorphism. All inactive links are either past or future states of isomorphisms. The self contained FAS of a particular vertical isomorphism determines which links are acceptable immediate successor states of that isomorphism. Depending on the nature of the FAS there could be more than one acceptable immediate successor state for that isomorphism. The symbol ::: indicates that the isomorphism tree structure - The Everything - vanishes upon occasion and the anisomorphic null set - The Nothing - resumes. This is the E/N alternation. Neither the anisomorphic null set nor the isomorphism tree since they both contain no information can internally address the unavoidable question of their own durability. This bilateral incompleteness drives the E/N alternation. The alternation since it destroys any record of the previous mix of active/inactive vertical isomorphic links causes a new random active/inactive mix each time the isomorphism tree resumes. This avoids a selected structure to The Everything. In order for a vertical isomorphic link to transfer to another string both the current link and an acceptable successor link must be simultaneously active. The transfer inactivates the prior link. Vertical isomorphic links driven active or inactive by the E/N alternation absent an active acceptable successor is simply in stasis. For a transfer to take place both the current and acceptable successor link must be simultaneously active. It is the transfer that is an event to an isomorphism. Are UD's or other such string generating machines vertical isomorphic links? I think so if I understand them correctly. Simply concatenate all the output strings of a UD so that successor vertical link shifts are just based on very localized regions of the overall string. I also think this process is similar to observer moments if observer moment means active links. Since the null set just is then the process may satisfy the idea that the Everything just is. It is the isomorphic tree that undergoes change. Now I see nothing wrong with FAS that have a do not care content to their rules determining acceptable successor links. My goal is to try to show that universes [vertical isomorphic links] that can support SAS have at least some do not care content in the rules. To do this I turn to Chaitin and explore the viability of deterministic cascades. By deterministic I mean each state has only one possible prior and one possible successor - the computational exercise is by

### Re: Provable vs Computable

George Levy wrote: [EMAIL PROTECTED] wrote: Example: a never ending universe history h is computed by a finite nonhalting program p. To simulate randomness and noise etc, p invokes a short pseudorandom generator subroutine q which also never halts. The n-th pseudorandom event of history h is based on q's n-th output bit q(n) which is initialized by 0 and set to 1 as soon as the n-th element of an ordered list of all possible program prefixes halts. Whenever q modifies some q(n) that was already used in the previous computation of h, p appropriately recomputes h since the n-th pseudorandom event. Such a virtual reality or universe is perfectly well-defined. Such a universe would violate Bell' inequality theorem. Quantum randomness cannot be simulated by hidden variables. We have to move beyond realism..to get a model of objective reality we must first develop a model of consciousness. George I disagree. Hidden variables are indeed excluded, but that doesn't mean that deterministic models proposed by Jürgen or 't Hooft are in conflict with Bell's theorem. In the case of the model proposed by 't Hooft, you have a universe that is very chaotic. Quantum mechanics arises in a statistical description of the theory. Particles such as electrons, photons etc. don't describe the degrees of freedom of the original deterministic theory, but rather they arise only in the statistical description of this theory. In other words: Mach was right in not believing that atoms exist. In the case of the two slits experiment, a hidden variable theory would tell you through what particular slit an elecron travelled, and this is not possible. Okay, but does the electron exist in the first place? I think not. The electron is just a mathematical tool that allows you to calculate probabilities and is unphysical, just like virtual particles and ghosts in Feynman diagrams. Why believe in electrons, but not in the Fadeev-Popov ghost? Saibal

### Re: Provable vs Computable

scerir wrote: Juergen Schmidhuber wrote: Which are the logically possible universes? Max Tegmark mentioned a somewhat vaguely defined set of self-consistent mathematical structures'' implying provability of some sort. The postings of Bruno Marchal and George Levy and Hal Ruhl also focus on what's provable and what's not. Is provability really relevant? Philosophers and physicists find it sexy for its Goedelian limits. But what does this have to do with the set of possible universes? Many people think that if a formal statement is neither provable nor refutable, then it should be considered neither true, nor false. But it is not that way that we - normally - use the term true. Somebody wrote: Suppose that I have a steel safe that nobody knows the combination to. If I tell you that the safe contains 100 dollars - and it really does contain 100 dollars - then I'm telling the truth, whether or not anyone can prove it. And if it doesn't contain 100 dollars, then I'm telling a falsehood, whether or not anyone can prove it. (A multi-valued logics can deal with statements that are either definitely true or definitely false, but whose actual truth value may, or may not, be known, or even be knowable.). That is basicaly the difference between classical logic with gap between proof and truth, and intuitionistic logic, or constructive logic, which equivote truth and provability. And that is something which will be translated in the language of the machine ... It is part of the proof I explain currently. I have begin the explanations of logic with classical logics. But other logics are fundamental in the derivation (mainly intuitionist and quantum logics). Bruno

### Re: Provable vs Computable

Juergen Schmidhuber wrote Which are the logically possible universes? Max Tegmark mentioned a somewhat vaguely defined set of ``self-consistent mathematical structures,'' implying provability of some sort. The postings of Bruno Marchal and George Levy and Hal Ruhl also focus on what's provable and what's not. You know that Hal Ruhl doesn't distinguish computability and provability, so it is open for me if his approach is nearer your's or mine. The difference relies more between averaging on the (local) set of consistent extensions defined in the whole UD*, or finding a priori defining universes probabilities, or Universal prior. I communicate with the sound lobian machine because I agree (in arithmetic) with the laws of exclude middle, and all classical logic. Provable plays the role of thoroughly verifiable scientific communication. (BTW *you* were the guy asking for formalisation!). Now we are working at the metalevel (as George aptly remarks) and we will interview the machine on its self-reference abilities. Recall the goal consists in translating UDA in a language interpretable by a sound UTM. And UDA is a self-referential thought experiment. It will happen that the incompleteness phenomenon will force us to take into account the nuance between []p and ([]p p) and ([]p p) in the discourse of the machine. They will correspond to provable p, knowable p, probability(p)=1. Knowable will give rise to intuitionist logic and probability 1 will give quantum logic. Probability(p) 1 will really be no more that 1) there is consistent extension, 2) p is true in all those consistent extension. (Only in an ideal frame we have []p - p, remember that in the cul-de-sac world []p is always true). Is provability really relevant? Philosophers and physicists find it sexy for its Goedelian limits. But what does this have to do with the set of possible universes? Wait and see. Remember I told George we have not yet really beging the proof. The hard and tiedous thing is to arithmetise the provability predicate. I will define knowledge and observable (in the UDA sense) *in* the language of the machine and I will show that the observable propositions obeys some quantum logic. I will only consider the case observable with a probability one. This will give a concrete purely arithmetical interpretation of a quantum logic. The probabilities are taken on the set of relative consistent (UD accessible) extensions, and by consistent I just mean -[]- with [] Goedel's provability predicate. (so you can guess the role of provability). The UD will be translated in the form of the set of all (true) \Sigma_1 sentences. Is provability really relevant? Philosophers and physicists find it sexy for its Goedelian limits. But what does this have to do with the set of possible universes? It has to do with the origin of the belief in universe(s) once we bet we do survive digital substitution. I believe the provability discussion distracts a bit from the real issue. If we limit ourselves to universes corresponding to traditionally provable theorems then we will miss out on many formally and constructively describable universes that are computable in the limit yet in a certain sense soaked with unprovable aspects. Actually, provability is just a step in my derivation (and we have still not begin to discusse it! nor to define it). We have just seen some modal logic which have a priori nothing to do with provability. You are still anticipating. It is a good thing you are open to unprovable aspects, and it makes weirder you are not open to uncomputable aspects. (Although I know provability is relative and computability is absolute (Church's Thesis) Do you really believe than one of us limit universes to sets of provable theorems. I am myself just defining the local *discourse* of a machine-scientist. Such a virtual reality or universe is perfectly well-defined. At some point each history prefix will remain stable forever. Even if we know p and q, however, in general we will never know for sure whether some q(n) that is still zero won't flip to 1 at some point, because of Goedel etc. So this universe features lots of unprovable aspects. I have no problem with that. As you should know from our earlier discussion. Remember that the big role in my work comes from (G* minus G), which is a logic of the *unprovable* statements. G ang G* will be defined formally soon, but you can also consult Solovay 1976 or Boolos ... By logic here I mean a well defined set (of formulas) logically closed for modus ponens. Note also that observers evolving within the universe ... The UDA shows that such an expression has no meaning. The movie graph (or Maudlin's Olympia) illustrates how non trivial the mind-body problem is with comp. I am aware there is something very hard to swallow here. But it is a consequence of comp. ...may write books about all kinds of unprovable things; they may also write down inconsistent

### Re: Provable vs Computable

[EMAIL PROTECTED] wrote: Example: a never ending universe history h is computed by a finite nonhalting program p. To simulate randomness and noise etc, p invokes a short pseudorandom generator subroutine q which also never halts. The n-th pseudorandom event of history h is based on q's n-th output bit q(n) which is initialized by 0 and set to 1 as soon as the n-th element of an ordered list of all possible program prefixes halts. Whenever q modifies some q(n) that was already used in the previous computation of h, p appropriately recomputes h since the n-th pseudorandom event. Such a virtual reality or universe is perfectly well-defined. Such a universe would violate Bell' inequality theorem. Quantum randomness cannot be simulated by hidden variables. We have to move beyond realism..to get a model of objective reality we must first develop a model of consciousness. George

### Re: Provable vs Computable

Juergen Schmidhuber wrote: Which are the logically possible universes? Max Tegmark mentioned a somewhat vaguely defined set of self-consistent mathematical structures'' implying provability of some sort. The postings of Bruno Marchal and George Levy and Hal Ruhl also focus on what's provable and what's not. Is provability really relevant? Philosophers and physicists find it sexy for its Goedelian limits. But what does this have to do with the set of possible universes? Many people think that if a formal statement is neither provable nor refutable, then it should be considered neither true, nor false. But it is not that way that we - normally - use the term true. Somebody wrote: Suppose that I have a steel safe that nobody knows the combination to. If I tell you that the safe contains 100 dollars - and it really does contain 100 dollars - then I'm telling the truth, whether or not anyone can prove it. And if it doesn't contain 100 dollars, then I'm telling a falsehood, whether or not anyone can prove it. (A multi-valued logics can deal with statements that are either definitely true or definitely false, but whose actual truth value may, or may not, be known, or even be knowable.). - scerir

### Re: Provable vs Computable

Juergen Schmidhuber wrote: Which are the logically possible universes? Max Tegmark mentioned a somewhat vaguely defined set of self-consistent mathematical structures'' implying provability of some sort. The postings of Bruno Marchal and George Levy and Hal Ruhl also focus on what's provable and what's not. Is provability really relevant? Philosophers and physicists find it sexy for its Goedelian limits. But what does this have to do with the set of possible universes? scerir writes an enjoyable version on the last part of the quote. Let me address the first part about possible universes. Of course Juergen was cautious and included logically in his phrase. Logically most likely refers to human (on this list: even mathematical) logic. Do we really think that human (math) logic is the restrictive principle for nature? What we see (what we want to see?) seems to point to that, but do we see'em all? Isn't possible what we don't see or understgand or realize? Didn't our horizon (logic, math) increase over some time? Are we at the end? In considering plenitude/multiverse, does it make sense to select part of it (maybe a small, unimportant segment only)? Even if we cannot develop knowledge about the rest, we should not deny its possibility of existence. The farthest from this list would be a closed mind! John Mikes

### Re: Provable vs Computable (post not done)

Sorry, some how my mailer decided I wanted to send this. Clearly it is not done. Dear Juergen: I am not so much interested in provability as I am in whether or not the noise in a universes history is pseudorandom or random and forging an . At 5/4/01, you wrote: Which are the logically possible universes? Max Tegmark mentioned a somewhat vaguely defined set of ``self-consistent mathematical structures,'' implying provability of some sort. The postings of Bruno Marchal and George Levy and Hal Ruhl also focus on what's provable and what's not. Is provability really relevant? Philosophers and physicists find it sexy for its Goedelian limits. But what does this have to do with the set of possible universes? I believe the provability discussion distracts a bit from the real issue. If we limit ourselves to universes corresponding to traditionally provable theorems then we will miss out on many formally and constructively describable universes that are computable in the limit yet in a certain sense soaked with unprovable aspects. Example: a never ending universe history h is computed by a finite nonhalting program p. To simulate randomness and noise etc, p invokes a short pseudorandom generator subroutine q which also never halts. The n-th pseudorandom event of history h is based on q's n-th output bit q(n) which is initialized by 0 and set to 1 as soon as the n-th element of an ordered list of all possible program prefixes halts. Whenever q modifies some q(n) that was already used in the previous computation of h, p appropriately recomputes h since the n-th pseudorandom event. Such a virtual reality or universe is perfectly well-defined. At some point each history prefix will remain stable forever. Even if we know p and q, however, in general we will never know for sure whether some q(n) that is still zero won't flip to 1 at some point, because of Goedel etc. So this universe features lots of unprovable aspects. But why should this lack of provability matter? It does not do any harm. Note also that observers evolving within the universe may write books about all kinds of unprovable things; they may also write down inconsistent axioms; etc. All of this is computable though, since the entire universe history is. So again, why should provability matter? Juergen Schmidhuber http://www.idsia.ch/~juergen/toesv2/