LESSWRONG
LW

All of Splat's Comments + Replies

Rationality Quotes: February 2010
Splat40

Replying out of order:

2) A quick search of Google Scholar didn't net me a Chaitin definition of K-complexity for a structure. This doesn't surprise me much, as his uses of AIT in logic are much more oriented toward proof theory than model theory. Over here you can see some of the basic definitions. If you read page 7-10 and then my explanation to Silas here you can figure out what the K-complexity of a structure means. There's also a definition of algorithmic complexity of a theory in section 3 of the Chaitin.

According to these definitions, the complex... (read more)

Reply
1Eliezer Yudkowsky
Relevant link: http://lesswrong.com/lw/vh/complexity_and_intelligence/
1SteveLandsburg
Splat: Thanks again for bringing insight and sanity to this discussion. A few points: 1) Your description of the structure N presupposes some knowledge of the structure N; the program that prints out the structure needs a first statement, a second statement, etc. This is, of course, unavoidable, and it's therefore not a complaint; I doubt that there's any way to give a formal description of the natural numbers without presupposing some informal understanding of the natural numbers. But what it does mean, I think, is that K-complexity (in the sense that you're using it) is surely the wrong measure of complexity here---because when you say that N has low K-complexity, what you're really saying is that "N is easy to describe provided you already know something about N". What we really want to know is how much complexity is imbedded in that prior knowledge. 1A) On the other hand, I'm not clear on how much of the structure of N is necessarily assumed in any formal description, so my point 1) might be weaker than I've made it out to be. 2) It has been my position all along that K-complexity is largely a red herring here in the sense that it need not capture Dawkins's meaning. Your observation that a pot of boiling water is more K-complex than a squirrel speaks directly to this point, and I will probably steal it for use in future discussions. 3) When you talk about T(N), I presume you mean the language of Peano arithmetic, together with the set of all true statements in that language. (Correct me if I'm wrong.) I would hesitate to call this a theory, because it's not recursively axiomatizable, but that's a quibble. In any event, we do know what we mean by T(N), but we don't know what we mean by T(squirrel) until we specify a language for talking about squirrels---a set of constant symbols corresponding to tail, head, etc., or one for each atom, or....., and various relations, etc. So T(N) is well defined, while T(squirrel) is not. But whatever language you settle on,
Rationality Quotes: February 2010
Splat30

I'm responding here to your invitation in the parent, since this post provides some good examples of what you're not getting.

I didn't say that. Read it again. I said that there is some finite axiom list that can describe squirrels, but it's not just the axioms that suffice to let you use arithmetic.

Simulating squirrels and using arithmetic require information, but that information is not supplied in the form of axioms. The best way to imagine this in the case of arithmetic is in terms of a structure.

Starting from the definition in that wikipedia page,... (read more)

Reply
0SilasBarta
I wasn't careful to distinguish axioms from other kinds of information in the model, and I think it's a distraction to do so because it's just an issue of labels (which as you probably saw from the discussion is a major source of confusion). My focus was on tabulating the total complexity of whatever-is-being-claimed-is-significant. For that, you only need to count up how much information goes into your "message" describing the data (in the "Minimum Message Length criterion" sense of "message"). Anything in such a message can be described without loss of generality as an axiom. If I want to describe squirrels, I will find, like most scientists find, that the job is much easier of I can express things using arithmetic. Arithmetic is so helpful that, even after accounting for the cost of telling you how to use it (the axioms-or-whatever of math), I still save in total message length. Whether you call the squirrel info I gathered from nature, or the specification of math, the "axioms" doesn't matter. But it's not the same arithmetic SteveLandsburg is talking about, if you follow through to the implications he claims fall out from it. He claims arithmetic -- the infinitely complex one -- runs the universe. It doesn't. The universe only requires the short message specifying N, plus the (finite) particulars of the universe. Whatever infinitely-complex thing he's talking about from a "different level of description" isn't the same thing, and can't be the same thing. What's more, the universe can't contain that thing because there is no (computable) isomorphism between it and the universe. As we derive the results of longer and longer chains of reasoning, our universe starts to contain more and more complex pieces of that thing, but it still wouldn't be somehow fundamental to the universe's operation -- not if we're just now getting to contain pieces of it. I'm sorry, I don't see how that contradicts what I said or shows a different parallel. Now, I certainly didn't use
David Pearce on Hedonic Moral realism
Splat20

You really need to offer an argument for at least one of these two things to make your point:

  • A utilitarian aiming to maximize subjectively hypervaluable states will not tile orgasmium.
  • It is good to tile orgasmium.
Reply
David Pearce on Hedonic Moral realism
Splat40

The neurology, while detailed, seems a little confused. In particular, adding mu-opioid receptors to every neuron in the brain sounds more like a recipe for epilepsy than for superhappiness.

Reply
Applying utility functions to humans considered harmful
Splat10

I found the detail helpful. Even more detail might have been good, but you'd have had to write a sequence.

Reply
Rationality Quotes: February 2010
Splat30

Well, if you need to simulate a squirrel for just a little while, and not for unbounded lengths of time, a substructure of N (without closure under the operations) or a structure with a considerable amount of sharing with N (like 64-bit integers on a computer) could suffice for your simulation.

The problem you encounter here is that these substructures and near-substructures, once they reach a certain size, actually require more information to specify than N itself. (How large this size is depends on which abstract computer you used to define your instance... (read more)

Reply
3SteveLandsburg
Splat: 1) This depends on what you mean by "specify". To distinguish N from other mathematical structures requires either an infinite (indeed non-recursive) amount of information or a second order specification including some phrase like "all predicates". Are you referring to the latter? Or to something else I don't know about? 2) I do not know Chaitin's definition of the K-complexity of a structure. I'll try tracking it down, though if it's easy for you to post a quick definition, I'll be grateful. (I do think I know how to define the K-complexity of a theory.) I presume that if I knew this, I'd know your answer to question 1). 3) Whatever the definition, the question remains whether K-complexity is the right concept here. Dawkins's argument does not define complexity; he treats it as "we know it when we see it". My assertion has been that Dawkins's argument applies in a context where it leads to an incorrect conclusion, and therefore can't be right. To make this argument, I need to use Dawkins's intended notion of complexity, which might not be the same as Chaitin's or Kolmogorov's. And for this, the best I can do is to infer from context what Dawkins does and does not see as complex. (It is, clear from context that he sees complexity as a general phenomenon, not just a biological one.) 4) The natural numbers are certainly an extremely complex structure in the everyday sense of the word; after thousands of years of study, people are learning new and surprising things about them every day, and there is no expectation that we've even scratched the surface. This is, of course, a manifestation of the "wildly nonrecursive" nature of T(N), all of which is reflected in N itself. And this, again, seems pretty close to the way Dawkins uses the word. 5) I continue to be most grateful for your input. I see that SIlas is back to insisting that you can't simulate a squirrel with a simple list of axioms, after having been told forty eight bajillion times (here and elsewhe
Rationality Quotes: February 2010
Splat40

It is in fact provably impossible to construct a computable nonstandard model (where, say, S and +, or S and × are both computable relations) in a standard model of computation. What I was referring to was a nonstandard model that was computable according to an equally nonstandard definition of computation, one that makes explicit the definitional dependence of Turing Machines on the standard natural numbers and replaces them with nonstandard ones.

The question I'm wondering about is whether such a definition leads to a sensible theory of computation (at l... (read more)

Reply
0Douglas_Knight
Would you give a reference? I found it easy to find assertions such as "the completeness theorem is not constructively provable," but this statement is a little stronger.
Rationality Quotes: February 2010
Splat30

And so is skepticism of canonical Turing machines, as far as I can tell. Specifically, skepticism that there is always a fact of the matter as to whether a given TM halts.

I think you might be able to make the skeptical position precise by constructing nonstandard variants of TMs where the time steps and tape squares are numbered with nonstandard naturals, and the number of symbols and states are also nonstandard, and you would be able to relate these back to the nonstandard models that produced them by using a recursive description of N to regenerate the ... (read more)

Reply
2Eliezer Yudkowsky
I'm not sure, but I think it's impossible to construct a computable nonstandard model of the integers (one where you can implement operations like +).
Rationality Quotes: February 2010
Splat130

Your biggest problem here, and in your blog posts, is that you equivocate between the structure of the standard natural numbers (N) and the theory of that structure (T(N), also known as True Arithmetic). The former is recursive and (a reasonable encoding of) it has pretty low Kolmogorov complexity. The latter is wildly nonrecursive and has infinite K-complexity. (See almost any of Chaitin's work on algorithmic information theory, especially the Omega papers, for definitions of the K-complexity of a formal system.)

The difference between these two structu... (read more)

Reply
2SteveLandsburg
Splat: Thanks for this; it's enlightening and useful. The part I'm not convinced of this: A squirrel is a finite structure; it can be specified by a sequence of A's, C's, G's and T's, plus some rules for protein synthesis and a finite number of other facts about chemistry. (Or if you think that leaves something out, it can be described by the interactions among a large but finite collection of atoms.) So I don't see where we need all of N to simulate a squirrel.
Welcome to Heaven
Splat20

For that matter, so does falling asleep in the normal way.

Reply