Re: probabilities measures computable universes
On Fri, Jan 23, 2004 at 09:04:20PM -0800, Hal Finney wrote: Do you think it would come out differently with a universal distribution? There are an infinite number of universal distributions. Some of them assign greater probability to even integers, some of them assign greater probability to odd integers. For those who think that a theory of everything should specify a unique prior over universes, observers, or observer-moments, I think this multiplicity of universal distributions is a big problem. My view is that a unique prior is not necessary. Instead the prior can be thought of as a representation of how much one cares about each universe, observer, or observer-moment, and therefore is a purely subjective preference. The more conventional interpretation would use the probability computed over all numbers less than n, and take the limit as n approaches infinity. This would say that the probability of being even is 1/2. I think this is how such results are derived as the one mentioned earlier by Bruno, that the probability of two random integers being coprime is 6/pi^2. These kinds of results are useful when you have a uniform distribution over all integers less than n, with n large. Then you can use these results to approximate probabilities under the actual distribution. I don't think you can use these results to say that somehow the *real* probability of being even is 1/2. I'd imagine that this result would not hold using a universal distribution. Are these mathematical results fundamentally misguided, or is this an example where the UD is not the best tool for the job? I'm not sure what you mean here.
recommended books
These books have been mentioned on the list before, but I'm recommending them again because a lot of new members have joined since we last talked about them. To motivate you to read these books, I've given some questions that each book helps answer or provide the necessary background knowledge to discuss. I'd say that the first book in this list should be required reading for all members of this list, while the other two are more optional. If anyone else has more book recommendations, please feel free to add to this list. _An Introduction to Kolmogorov Complexity and Its Applications_, Ming Li and Paul Vitanyi (What is measure, prior, universal distribution? How can we explain why laws of physics exist and why we don't see random deviations from the laws of physics?) _Theory of Recursive Functions and Effective Computability_, Hartley Rogers (What does computable mean? What do we know about uncomputable mathematical structures? Should we assume that we're in a computable universe?) _The Foundations of Causal Decision Theory_, James Joyce (What justifies using numbers between 0 and 1 to represent degrees of belief and using probability theory to constrain/manipulate those numbers (i.e. probabilities)? Is the use of probabilities still appropriate if all possible universes exist, and if so how should it work? How should we make decisions if all possible universes exist?)
Re: Modern Physical theory as a basis for Ethical and Existential Nihilism
I have to say that I sympathize with Caesar, but my position is slightly different. I think there is a possibility that that objective morality does exist, but we're simply too stupid to realize what it is. Therefore we should try to improve our intelligence, through intelligence amplication, or artificial intelligence, before saying that objective morality is impossible and therefore we should just pursue other goals like survival, comfort or happiness. Some people have argued that in fact survival is an objective goal, because evolution makes sure that people who don't pursue survival don't exist. But if we assume that everything exists, the above statement has to be modified to an assertion that people who don't pursue survival have low measure. However the choice of measure itself is subjective, so why shouldn't one use a measure in which people who don't pursue survival have high measure (e.g., one which favors universes where those people survive anyway through good luck or benevolent gods)?
Re: Modern Physical theory as a basis for Ethical and Existential Nihilism
There are statements of fact, statements of logic (also called analytic or a priori), and statements of value. Statements of fact are verified or falsified empirically. Statements of logic include mathematical theorems and are verified or falsified by following the rules of logic or mathematics. Statements of value - which includes ethics and aesthetics - are expressions of one's feelings or wishes, are not, by their nature, right or wrong (except in the trivial sense of whether one is being truthful about one's feelings). Now, ethical statements may actually include statements of fact, and this part can be verified or falsified objectively. For example, I may say, (a) any activity which causes net human suffering is bad; (b) abortion causes net human suffering; therefore, (c) abortion is bad. Look first at the logical structure: classic syllogism, no problem. Second, look at premiss (b). There is a lot of research to do before allowing this as true: can a foetus at a certain stage experience pain? Is the harm to the foetus outweighed by the harm to the mother and unwanted child if there is no abortion? Finally, look at premiss (a). If asked why I believe this it may turn out to in fact be another composite, to be analysed as above. However, at some point, I will not be able to give any further explanation, and THAT is the basic ethical belief. If I stop with (a) above, I am simply saying that this is how I feel about suffering, and this feeling is not contingent on the state of affairs in any actual or possible world [there, I got it in!]. From: Wei Dai [EMAIL PROTECTED] To: [EMAIL PROTECTED] [EMAIL PROTECTED] CC: [EMAIL PROTECTED] Subject: Re: Modern Physical theory as a basis for Ethical and Existential Nihilism Date: Sat, 24 Jan 2004 06:47:39 -0500 I have to say that I sympathize with Caesar, but my position is slightly different. I think there is a possibility that that objective morality does exist, but we're simply too stupid to realize what it is. Therefore we should try to improve our intelligence, through intelligence amplication, or artificial intelligence, before saying that objective morality is impossible and therefore we should just pursue other goals like survival, comfort or happiness. Some people have argued that in fact survival is an objective goal, because evolution makes sure that people who don't pursue survival don't exist. But if we assume that everything exists, the above statement has to be modified to an assertion that people who don't pursue survival have low measure. However the choice of measure itself is subjective, so why shouldn't one use a measure in which people who don't pursue survival have high measure (e.g., one which favors universes where those people survive anyway through good luck or benevolent gods)? _ Get less junk mail with ninemsn Premium. Click here http://ninemsn.com.au/premium/landing.asp
Re: Is the universe computable
Dear Bruno, Interleaving. - Original Message - From: Bruno Marchal [EMAIL PROTECTED] To: [EMAIL PROTECTED]; [EMAIL PROTECTED] Cc: [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Friday, January 23, 2004 9:42 AM Subject: Re: Is the universe computable Dear Stephen, At 12:39 21/01/04 -0500, Stephen Paul King wrote: Dear Bruno and Kory, Interleaving. - Original Message - From: Bruno Marchal [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Wednesday, January 21, 2004 9:21 AM Subject: Re: Is the universe computable At 02:50 21/01/04 -0500, Kory Heath wrote: At 1/19/04, Stephen Paul King wrote: Were and when is the consideration of the physical resources required for the computation going to obtain? Is my question equivalent to the old first cause question? [KH] The view that Mathematical Existence == Physical Existence implies that physical resources is a secondary concept, and that the ultimate ground of any physical universe is Mathspace, which doesn't require resources of any kind. Clearly, you don't think the idea that ME == PE makes sense. That's understandable, but here's a brief sketch of why I think it makes more sense than the alternative view (which I'll call Instantiationism): [SPK] I should respond to Kory's ME == PE idea. In PE we find such things as thermodynamic entropy and temporality. If we are to take Kory's idea (that Mathspace doesn't require resources) seriously, ME does not. This seems a direct contradiction! Perhaps Kory has a paper on-line that lays out his thesis of Instantiationism. [SPK] Again, the mere postulation of existence is insufficient: it does not thing to inform us of how it is that it is even possible for us, as mere finite humans, to have experiences that change. We have to address why it is that Time, even if it is ultimately an illusion, and the distingtion between past and future is so intimately intetwined in our world of experience. [BM] Good question. But you know I do address this question in my thesis (see url below). I cannot give you too much technical details, but here is a the main line. As you know, I showed that if we postulate the comp hyp then time, space, energy and, in fact, all physicalities---including the communicable (like 3-person results of experiments) as the uncommunicable one (like qualie or results of 1-person experiment) appears as modalities which are variant of the Godelian self-referential provability predicates. As you know Godel did succeed in defining formal provability in the language of a consistent machine and many years later Solovay succeeds in formalising all theorems of provability logic in a couple of modal logics G and G*. G formalizes the provable (by the machine) statements about its own provability ability; and G* extends G with all true statements about the machine's ability (including those the machine cannot prove). [SPK] In my thinking all 1st person experiences are best possible simulations. The problem I find is that we can not use the modern equivalent to Leibniz' preordained harmony, whether in the form of a universal prior or modelization of some modal logic, since the list of all possible interactions is not enumerable. This is the aspect that I have tried to address by referencing Wolfram on the computational intractibility of some key aspects of physicality. There is also the seperate issue of how does one aspect of a logic address some other? We have the example of a Turing Machine that considers a tape and a head: there are separate in that one can move relative to the other all the while the transitions of the state of the head and the spot on the tape change. I do not see how some form of Monism can explain this. Additionally, there is the problem of simulating QM using formal logics. I have reference the Calude et al paper on this and you have said that it is good, but you seem to not have actually read it and let its implications set in. ;-) [BM] Now, independently, temporal logicians have defined some modal systems capable of formalizing temporal statements. Also, Brouwer developed a logic of the conscious subject, which has given rise to a whole constructive philosophy of mathematics, which has been formalize by a logic known as intuitionist logic, and later, like the temporal logic, the intuitionist logic has been captured formally by an modal extension of a classical modal logic. Actually it is Godel who has seen the first that Intuitionist logic can be formalised by the modal logic S4, and Grzegorczyk makes it more precise with the extended system S4Grz. And it happens that S4Grz is by itself a very nice logic of subjective, irreversible (anti-symmetric) time, and this gives a nice account too of the relationship Brouwer described between time and consciousness. Now, if you remember, I use the thaetetus trick of defining (machine) knowledge
RE: probabilities measures computable universes
The notion of complex-valued or even quaternionic or octonionic probabilities has been considered; see http://physics.bu.edu/~youssef/quantum/quantum_refs.html for some pointers into the literature. -- Ben Goertzel -Original Message- From: scerir [mailto:[EMAIL PROTECTED] Sent: Friday, January 23, 2004 9:23 AM To: [EMAIL PROTECTED] Subject: Re: probabilities measures computable universes Are probabilities always and necessarily positive-definite? I'm asking this because there is a thread, started by Dirac and Feynman, saying the only difference between the classical and quantum cases is that in the former we assume the probabilities are positive-definite. Thus, speaking of MWI, we could also ask: what is the joint probability of finding ourselves in a universe alpha and of finding ourselves in a universe beta, which is 180 degrees out of phase with the first one (whatever that could mean)? s.
Re: Subjective measure? How does that work?
Can you explain briefly why the choice of measure is subjective? I haven't read any of the books you mentioned (will try to get to them) but am familiar with computability theory and decision theory. In my favourite interpretation of the multiverse, as a very long (possibly lengthening) qubitstring containing all of the possible information-states implied in such a long bitstring, the absolute measure of any information-state (instantaneous state of some universe) would be the same as any other state of the same bitstring length. In that framing of things, I guess there's another definition of measure, which goes something like this: Let Ui be an internal-time-ordered set of information-states s1,s2,...,s(now)comprising an observable universe. Ui, to be observable, is constrained to be an informationally self-consistent (too complex a concept to get into right here) set of information-states. There is a constraint on any information-state which qualifies to be s(now+1) in any observable universe path s1,s2,...,S(now). Specifically, any information-state that can be S(now+1) must be informationally consistent (not law violating) in conjunction with s1,s2,...,S(now). Furthermore, the history that has evolved as s1,s2,...,s(now) has the result of determining the Ui-relative probability of any particular other information-state being able to become s(now+1) in that observable path. That now-in-an-observable-universe-relative probability of successorhood in that universe of any other information-state is then a universe-specific measure value, or more specifically, a now-state-of-universe specific measure value. That now-in-an-observable-universe measure (for potential successor information states for that universe state-set) may correspond to the probabilities of all the outcomes of all the wave equations of quantum-states which are observable in the now moment in that universe. As a comp sci person and not a physicist, I look forward to your read on where my interpretation is misguided, and for a better interpretation. Eric Wei Dai wrote: I have to say that I sympathize with Caesar, but my position is slightly different. I think there is a possibility that that objective morality does exist, but we're simply too stupid to realize what it is. Therefore we should try to improve our intelligence, through intelligence amplication, or artificial intelligence, before saying that objective morality is impossible and therefore we should just pursue other goals like survival, comfort or happiness. Some people have argued that in fact survival is an objective goal, because evolution makes sure that people who don't pursue survival don't exist. But if we assume that everything exists, the above statement has to be modified to an assertion that people who don't pursue survival have low measure. However the choice of measure itself is subjective, so why shouldn't one use a measure in which people who don't pursue survival have high measure (e.g., one which favors universes where those people survive anyway through good luck or benevolent gods)?
Re: Subjective measure? How does that work?
I find some inconsistencies in your post: qubitstring containing all of the possible information-states implied in such a long bitstring,... possible, of course, to OUR knowledge (imagination). Anthropomorph thinking about the MW. Let Ui be an internal-time-ordered set of information-states s1,s2,...,s(now)comprising an observable universe. How 'bout the Uis where 'time' has not evolved? Excluded? Observable by what means? We have a pretty narrow range in mind. Would you restrict the MWI to our cognitive inventory of 2004? Does that mean that the MW was smaller in 1000 (with the then epistemized contents of cognition)? ... must be informationally consistent (not law violating) in conjunction ... what law? presumed omniscient? Just malicious remarks. I appreciate to try and to criticize. I have no better ones. JM - Original Message - From: Eric Hawthorne [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, January 24, 2004 3:21 PM Subject: Re: Subjective measure? How does that work? Can you explain briefly why the choice of measure is subjective? I haven't read any of the books you mentioned (will try to get to them) but am familiar with computability theory and decision theory. In my favourite interpretation of the multiverse, as a very long (possibly lengthening) qubitstring containing all of the possible information-states implied in such a long bitstring, the absolute measure of any information-state (instantaneous state of some universe) would be the same as any other state of the same bitstring length. In that framing of things, I guess there's another definition of measure, which goes something like this: Let Ui be an internal-time-ordered set of information-states s1,s2,...,s(now)comprising an observable universe. Ui, to be observable, is constrained to be an informationally self-consistent (too complex a concept to get into right here) set of information-states. There is a constraint on any information-state which qualifies to be s(now+1) in any observable universe path s1,s2,...,S(now). Specifically, any information-state that can be S(now+1) must be informationally consistent (not law violating) in conjunction with s1,s2,...,S(now). Furthermore, the history that has evolved as s1,s2,...,s(now) has the result of determining the Ui-relative probability of any particular other information-state being able to become s(now+1) in that observable path. That now-in-an-observable-universe-relative probability of successorhood in that universe of any other information-state is then a universe-specific measure value, or more specifically, a now-state-of-universe specific measure value. That now-in-an-observable-universe measure (for potential successor information states for that universe state-set) may correspond to the probabilities of all the outcomes of all the wave equations of quantum-states which are observable in the now moment in that universe. As a comp sci person and not a physicist, I look forward to your read on where my interpretation is misguided, and for a better interpretation. Eric PS I stay out of the 'ethix - morality' discussion, which IMO is definitely Earthbound - human - cultural - debatable. Eric mentioned lately the group-evolution, in which respect altruism (moral thinking?) is not out, but go 1 step higher - still within the earthly biosphere - and morality turns into foodchain. Dine or dined. There is no goal only change. Survival is a result. Human groups can identify what is good for them. E.g. to eat animals and plants - fellow living creatures.
Re: Subjective measure? How does that work?
John M wrote: I find some inconsistencies in your post: qubitstring containing all of the possible information-states implied in such a long bitstring,... possible, of course, to OUR knowledge (imagination). Anthropomorph thinking about the MW. I'm really talking about "convertible to binary-representation" information states here. i.e. formal notion of information i.e. a count and structuring of discrete differences. As such, the number of information-states representable in a qubitstring of length n is 2 ^ n. Let Ui be an "internal-time-ordered" set of information-states s1,s2,...,s(now)comprising an observable universe. How 'bout the Uis where 'time' has not evolved? Excluded? Those Uj's are not observable (unless we change the conventional meaning of that word.) "Observe" as conventionally meant is defined with respect (at least indirectly) to notions of time. Observable by what means? Any means where information can be conveyed from something outside of the observer SAS, at the speed of light or lower, to the representing mechanism inside the observer. BY THE WAY. I'M NOT A PHYSICIST. Can someone who knows please clarify the answer to the rather basic question of whether something like the slit-experiment means anything (or DOES anything to the quantum phenomena of the photons) in the absence of a perceiving observer like ourselves. I'm fairly basically and profoundly ignorant on that score. i.e. can "the measuring experiment machine itself" without the person (or AI etc, or dog, say) to perceive the result, still cause a difference in "what happens" to the photons? We have a pretty narrow range in mind. Would you restrict the MWI to our cognitive inventory of 2004? Does that mean that the MW was "smaller" in 1000 (with the then epistemized contents of cognition)? The observable, classicized portion of the Ui observable universe was smaller in 1000, or at any previous time-within-itself than now, yes. Of course, to be precise, now actually means here-now, as these are inseparable in relativistic physics. ... must be informationally consistent (not law violating) in conjunction ... what "law"? presumed omniscient? Observed and verified physical laws of the Ui universe. Just malicious remarks. I appreciate to try and to criticize. I have no better ones. No problemo JM Eric
Re: Modern Physical theory as a basis for Ethical and Existential Nihilism
On Sun, Jan 25, 2004 at 01:01:42AM +1100, Stathis Papaioannou wrote: If I stop with (a) above, I am simply saying that this is how I feel about suffering, and this feeling is not contingent on the state of affairs in any actual or possible world [there, I got it in!]. (a) as stated is ill defined. In order to actually reason with it in practice, you'd have to define what activity, cause, net, human, and suffering mean, but then it's hard to see how one can just have a feeling that statement (a), by now highly technical, is true. What about a slightly different variation of (a), where the definition of human or suffering is given a small tweak? How do you decide which of them reflects your true feelings? The mere presense of many similar but contradictory moral statements might give you a feeling of arbitrariness that causes you to reject all of them. Difficulties like this lead to the desire for a set of basic moral axioms that can be defined precisely and still be seen by everyone as obvious and non-arbitrary. Again, maybe it doesn't exist, but we can't know for sure unless we're much smarter than we actually are.
Re: Modern Physical theory as a basis for Ethical and Existential Nihilism
Morality, ethics, virtue, etc. imply a struggle for control -- at least within oneself, but often more widely. If morality had a set of obvious axioms, such as to lead to firm reliable answers to all moral questions in practice, it would be know-how, not morality. For everything there is a season a time, according to Ecclesiastes, but neither Ecclesiastes nor anything else always tells us just when those times seasons are. opportunity _ _ _ _ _ _ risk safeness _ _ _ _ _ _ _ futility ***For everything*** hope _ _ _ _ _ _ _ _ _ fear confidence _ _ _ _ _ _ despair ***there is a season*** courage _ _ _ _ _ _ _ prudence due confidence _ _ _ _ realism ***and an out-of-season*** rashness _ _ _ _ _ _ _ cowardice complacency _ _ _ _ _ defeatism (Note: the above structure entails that Aristotle's doctrine of virtue as a 'mean' between two extremes is at best a sloppy heuristic that captures a sense of maintaining some sort of poise or grace under pressure.) Even when we agree on what the evil is -- a forest fire approaching the town for example -- still to fight it, may require the moral virtues of courage due confidence, lest in one's heart one succumb to cowardly or defeatist thoughts about the fire. To refuse to fight it instead to flee in one's car may require the moral virtues of prudence realism -- lest one succumb to rash or complacent thoughts about the fire. Sometimes boldness is good, sometimes caution is good. Courage is appropriately hopeful action despite pressure not to be hopeful. Pressure -- a struggle, as I said. Most traditional virtues can be defined in such manner. Why would one be under such pressure but through conflict among one's own values? The moral value system is not independent self-contained but depends on non-entirely-moral values -- the value of the town, the trees, etc. -- on knowledge on understanding things about oneself others. The moral value of the town is based on consideration! s of which many are themselves not moral or not directly moral. Morality cannot provide easy answers when easy answers cannot be provided for many relevant non-moral or not purely moral questions -- e.g, what are the stakes? what are the threats? what are the opportunities? Applying our axiomatic moral/ethical mathematic will probably land us in still more moral/ethical quandaries. We are left asking, when, specifically, singularly, are these seasons times of which Ecclesiastes speaks? Of course we're left asking. How could it be otherwise? Furthermore, from a risk-management perspective, opportunity equals risk. Safeness equals futility. As Freud said, life presents a choice not between pleasure pain, but between both neither. Any moral system will set up opportunity/risk situations where the risk is that of violating the morality. If we're talking not just about morality in the usual narrow sense, but in the sense of excellence, the virtues of character, then morality guarantees trials tests for those who would be moral. (That doesn't make morality bad -- a bad morality is one that tends to assure that those who seek to be moral shall lose.) And to the extent that we disagree about human nature, disagreements about morality may run corespondingly deep. - Ben Udell - Original Message - From: Wei Dai [EMAIL PROTECTED] To: Stathis Papaioannou [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Saturday, January 24, 2004 9:00 PM Subject: Re: Modern Physical theory as a basis for Ethical and Existential Nihilism Stathis Papaioannou wrote: If I stop with (a) above, I am simply saying that this is how I feel about suffering, and this feeling is not contingent on the state of affairs in any actual or possible world [there, I got it in!] Wei Dai responded: (a) as stated is ill defined. In order to actually reason with it in practice, you'd have to define what activity, cause, net, human, and suffering mean, but then it's hard to see how one can just have a feeling that statement (a), by now highly technical, is true. What about a slightly different variation of (a), where the definition of human or suffering is given a small tweak? How do you decide which of them reflects your true feelings? The mere presense of many similar but contradictory moral statements might give you a feeling of arbitrariness that causes you to reject all of them. Difficulties like this lead to the desire for a set of basic moral axioms that can be defined precisely and still be seen by everyone as obvious and non-arbitrary. Again, maybe it doesn't exist, but we can't know for sure unless we're much smarter than we actually are.
Re: Subjective measure? How does that work?
On Sat, Jan 24, 2004 at 12:21:40PM -0800, Eric Hawthorne wrote: Can you explain briefly why the choice of measure is subjective? I haven't read any of the books you mentioned (will try to get to them) but am familiar with computability theory and decision theory. Since you do not mention that you're familiar with the theory of algorithmic complexity, I suggest that you read the first book on that list ASAP. The following response might not make sense until you do. Basically, all of the sensible proposed measures are based on the universal distribution, which assigns a larger probabilities to strings that have lower algorithmic complexities. However there's actually an infinite class of universal distributions, one for each universal Turing machine, and there's no objective criteria for determining which one should be used. Another problem is that using the universal distribution forces you to assume that non-computable universes do not exist. If one does not want to make this assumption, then a more dominant measure need to be used (for example, based on a TM with an oracle for the halting problem or the complexity of a string's logical definition) but then there are even more measures to choose from (how high up the computability hierarchy do you go? how high up the set theoretic hierarchy?). Now suppose that two people, Alice and Bob, somehow agree that a measure M is the objectively correct measure, but Bob insists on using measure M' in making decisions. He says So what if universe A has a bigger measure than universe B according to M? I just care more about what happens in universe B than universe A, so I'll use M' which assigns a bigger measure to universe B. What can Alice say to Bob to convince him that he is not being rational? I don't see what the answer could be.
Re: Subjective measure? How does that work?
Wei Dai wrote: Now suppose that two people, Alice and Bob, somehow agree that a measure M is the objectively correct measure, but Bob insists on using measure M' in making decisions. He says So what if universe A has a bigger measure than universe B according to M? I just care more about what happens in universe B than universe A, so I'll use M' which assigns a bigger measure to universe B. What can Alice say to Bob to convince him that he is not being rational? I don't see what the answer could be. But measures aren't just about making decisions about what to *do*, the main argument for a single objective measure is that such a measure could make predictions about what we *see*, like why we see regular laws of physics and never see any white rabbits. Although Bob can decide that only universes where gravity is repulsive matter to him in terms of his decision-making (so that he'd be happy to bet his life's savings that a dropped ball would fall up), he'll have to agree with Alice on what is actually observed to happen when a particular ball is dropped. Without an objective measure, I don't think there's any way to explain why we consistently see outcomes that obey the known laws of physics (like why we always see dropped balls fall towards the earth). Jesse Mazer _ Rethink your business approach for the new year with the helpful tips here. http://special.msn.com/bcentral/prep04.armx
Re: Subjective measure and turing machine terminology
Wei Dai wrote: On Sat, Jan 24, 2004 at 12:21:40PM -0800, Eric Hawthorne wrote: Can you explain briefly why the choice of measure is subjective? I haven't read any of the books you mentioned (will try to get to them) but am familiar with computability theory and decision theory. Since you do not mention that you're familiar with the theory of algorithmic complexity, I suggest that you read the first book on that list ASAP. The following response might not make sense until you do. I took some small smattering of that stuff in comp sci undergrad, but essentially what it lets met understand is that some algorithms are O(1), O(n), O(nlogn),O(n^2) O(e^n) etc. I'm also generally familiar with Turing Machine concepts, but I'm rusty on the details. I'm a bit confused as to what is meant by a string having a lower algorithmic complexity. Does that mean that ths shortest program that could result in a symbol string of that form has a vertain algorithmic complexity that is lower than the algorithmic complexity that could compute some other string? What are these strings anyway? Symbol strings which are a finite subpart of the turing machine's tape, conceptually? A question that would arise with that definition above of what the "algorithmic complexity of a string" means is: Shortest algorithm that could generate that string starting with what as its input? Surely if the input were a string that was, say, just one value in one tape-position different than the output string, then any output string can be computed by a trivial turing machine program (one step or so) from that special input. So how do you define what the input is in assessing "the algorithmic complexity of a string?" Or is the string a sequence of instructions and datastore positions comprising the turing machine program itself? and we're discussing the inherent computational complexity of that particular program, for any (or average or whatever) input? I guess I have more trouble mapping directly in my head from turing machine programs to multiverse states than I do mapping raw bitstrings to multiverse states. The general question I asked above would seem to come down to "isn't the complexity of getting to some subsequent information state determined by what the previous information state is?" Second terminology thing: When you say "each universal Turing machine, again I get confused". Isn't "a turing machine" just the abstraction consisting of the movable read/write head and a tape? Isn't the correct terminology "each turing machine PROGRAM which is NP-complete" or which is "universal"? How can we have different machines themselves? Or is it conventional to say that "a turing machine" is "the movable head, plus its current position, plus a particular set of values on a tape (i.e. a particular program?) In normal computing terminology, the machine is the machine and the software program is the software program and the data is the data. If you can just help me a little with these terminology stumbling blocks, I'm sure I (and other computational-complexity-theory-tourists on the list) can understand the concepts. Basically, all of the sensible proposed measures are based on the universal distribution, which assigns a larger probabilities to strings that have lower algorithmic complexities. However there's actually an infinite class of universal distributions, one for each universal Turing machine, and there's no objective criteria for determining which one should be used. Another problem is that using the universal distribution forces you to assume that non-computable universes do not exist. If one does not want to make this assumption, then a more dominant measure need to be used (for example, based on a TM with an oracle for the halting problem or the complexity of a string's logical definition) but then there are even more measures to choose from (how high up the computability hierarchy do you go? how high up the set theoretic hierarchy?). Now suppose that two people, Alice and Bob, somehow agree that a measure M is the objectively correct measure, but Bob insists on using measure M' in making decisions. He says "So what if universe A has a bigger measure than universe B according to M? I just care more about what happens in universe B than universe A, so I'll use M' which assigns a bigger measure to universe B." What can Alice say to Bob to convince him that he is not being rational? I don't see what the answer could be.
