Don't import java.util.*; use import java.util.List and java.util.Map

I am curious about the compression algorithm that would compress "import java.util.List; import java.util.Map" to a shorter string than "import java.util.*;".

Unless you would artificially make it compress the latter very inefficiently -- but, of course, using that kind of strategy you could "prove" almost anything.

I believe I've encountered a problem with either Solomonoff induction or my understanding of Solomonoff induction. I can't post about it in Discussion, as I have less than 20 karma, and the stupid questions thread is very full (I'm not even sure if it would belong there).

I've read about SI repeatedly over the last year or so, and I think I have a fairly good understanding of it. Good enough to at least follow along with informal reasoning about it, at least. Recently I was reading Rathmanner and Hutter's paper, and Legg's paper, due to renewed interest in AIXI as the theoretical "best intelligence," and the Arcade Learning Environment used to test the computable Monte Carlo AIXI approximation. Then this problem came to me.

Solomonoff Induction uses the size of the description of the smallest Turing machine to output a given bitstring. I saw this as a problem. Say AIXI was reasoning about a fair coin. It would guess before each flip whether it would come up heads or tails. Because Turing machines are deterministic, AIXI cannot make hypotheses involving randomness. To model the fair coin, AIXI would come up with increasingly convoluted Turing machines, attempting to compress a bitstring that approaches Kolmogorov randomness as its length approaches infinity. Meanwhile, AIXI would be punished and rewarded randomly. This is not a satisfactory conclusion for a theoretical "best intelligence." So is the italicized statement a valid issue? An AI that can't delay reasoning about a problem by at least labeling it "sufficiently random, solve later" doesn't seem like a good AI, particularly in the real world where chance plays a significant part.

Naturally, Eliezer has already thought of this, and wrote about it in Occam's Razor:

The formalism of Solomonoff Induction measures the "complexity of a description" by the length of the shortest computer program which produces that description as an output. To talk about the "shortest computer program" that does something, you need to specify a space of computer programs, which requires a language and interpreter. Solomonoff Induction uses Turing machines, or rather, bitstrings that specify Turing machines. What if you don't like Turing machines? Then there's only a constant complexity penalty to design your own Universal Turing Machine that interprets whatever code you give it in whatever programming language you like. Different inductive formalisms are penalized by a worst-case constant factor relative to each other, corresponding to the size of a universal interpreter for that formalism.

In the better (IMHO) versions of Solomonoff Induction, the computer program does not produce a deterministic prediction, but assigns probabilities to strings. For example, we could write a program to explain a fair coin by writing a program that assigns equal probabilities to all 2^N strings of length N. This is Solomonoff Induction's approach to fitting the observed data. The higher the probability a program assigns to the observed data, the better that program fits the data. And probabilities must sum to 1, so for a program to better "fit" one possibility, it must steal probability mass from some other possibility which will then "fit" much more poorly. There is no superfair coin that assigns 100% probability to heads and 100% probability to tails.

Does this warrant further discussion, if at least to validate or refute this claim? I don't think Eliezer's proposal for a version of SI that assigns probabilities to strings is strong enough, it doesn't describe what form the hypotheses would take. Would hypotheses in this new description be universal nondeterministic Turing machines, with the aforementioned probability distribution summed over the nondeterministic outputs?

He may like being out among the stars, but that's no reason to cut his fun on Earth short unnecessarily. Like, if the Earth were to be destroyed, and all the horcruxes hidden there with it, he'd regard having the Pioneer horcrux left as vastly superior to nonexistence, but that doesn't mean he wouldn't like to continue hanging out on Earth.

Edit: Also, if he's afraid that someone like Harry could accidentally explode the Sun, taking the Pioneer Plaque with it, he has reason to stick around to stop that from happening. Also, if Bacon's diary wasn't a horcrux, how do you account for Voldemort telling Harry it's nearly indestructible?

Ideal Bayesian updates assume logical omniscience, right? Including knowledge about logical fact of what EDT would do for any given input.

Note that step 1 is "Assume that I saw myself doing X," not "Assume that EDT outputs X as the optimal action." I believe that excludes any contradictions along those lines. Does logical omniscience preclude imagining counterfactual worlds?

What I'm saying is that the only way to solve any decision theory problem is to learn a causal model from data.

I think there are a couple of confusions this sentence highlights.

First, there are approaches to solving decision theory problems that don't use causal models. Part of what has made this conversation challenging is that there are several different ways to represent the world- and so even if CDT is the best / natural one, it needs to be distinguished from other approaches. EDT is not CDT in disguise; the two are distinct formulas / approaches.

Second, there are good reasons to modularize the components of the decision theory, so that you can treat learning a model from data separately from making a decision given a model. An algorithm to turn models into decisions should be able to operate on an arbitrary model, where it sees a -> b -> c as isomorphic to Drunk -> Fall -> Death.

To tell an anecdote, when my decision analysis professor would teach that subject to petroleum engineers, he quickly learned not to use petroleum examples. Say something like "suppose the probability of striking oil by drilling a well here is 40%" and an engineer's hand will shoot up, asking "what kind of rock is it?". The kind of rock is useful for determining whether or not the probability is 40% or something else, but the question totally misses the point of what the professor is trying to teach. The primary example he uses is choosing a location for a party subject to the uncertainty of the weather.

It just doesn't make sense to postulate particular correlations between an EDT agent's decisions and other things before you even know what EDT decides!

I'm not sure how to interpret this sentence.

The way EDT operates is to perform the following three steps for each possible action in turn:

1. Assume that I saw myself doing X.
2. Perform a Bayesian update on this new evidence.
3. Calculate and record my utility.

It then chooses the possible action which had the highest calculated utility.

One interpretation is you saying that EDT doesn't make sense, but I'm not sure I agree with what seems to be the stated reason. It looks to me like you're saying "it doesn't make sense to assume that you do X until you know what you decide!", when I think that does make sense, but the problem is using that assumption as Bayesian evidence as if it were an observation.

Um... doesn't it take exponential time in order to simulate quantum mechanics on a classical computer?

Uncountability doesn't seem like a big deal to me. Just give the Turing machine an auxiliary tape containing the real parameter.

I can't work out whether this works or not. Here's a really simple example system: each output is 0 or 1, drawn with a fixed probability. If the probability is an uncomputable number, then no algorithm with a finite initial state can generate output with exactly that probability; there has to be a rational number inbetween the real probability and the simulated one, which means there's an attacker that can distinguish the two given enough outputs.

If instead the simulator can read the real probability on an infinite tape... obviously it can't read the whole tape before producing an output. So it has to read, then output, then read, then output. It seems intuitive that with this strategy, it can place an absolute limit on the advantage that any attacker can achieve, but I don't have a proof of that yet.

A related question is whether a Turing machine can fully simulate the dynamical system, that is, whether it can compute the state at any future time to any precision using only finitely many bits from the starting parameters.

Obviously if this can be done then what I ask can be done. I had thought this impossible, which is why I wanted to substitute an easier question about distinguishability.

I think the answer to that differential equations with initial conditions a computable real number can evolve to an uncomputable real number. But if the initial random number is not arbitrary, but guaranteed random, maybe it is computable. (That is, maybe the inputs with computable futures have full measure.)

Well that's clearly true, if the dynamical system is that when t = 0 then y = 0 and dy/dt = 1, then y will pass through lots of uncomputable values at uncomputable times. Some kind of computable uncertainty about the initial state may address the cardinality issue, but I'm not sure how to formalise that.

Another key factor here is that the machine that does this would operate inside an alien environment compared to existing life - it would operate in a clean vacuum, possibly at low temperatures, and would use extremely stiff subunits made of covalently bonded silicon or carbon

If you have to do this, then the threat of nanotech looks a lot smaller. Replicators that need a nearly perfect vacuum aren't much of a threat.

Also, this is one place where AI comes in. The universe doesn't have any trouble modeling the energetics of a large network of atoms. If we have trouble doing the same, even using gigantic computers made of many many of these same atoms, then maybe the problem is we are doing it a hugely inefficient way. An entity smarter that humans might find a way to re-formulate the math for many orders of magnitude more efficient calculations, or it might find a way to build a computer that more efficiently uses the atoms it is composed of.

This sounds very close to a default assumption that these processes are genuinely easy to not just compute, but to actually work out what solutions one wants. Answering "how will this protein most likely fold?" is computationally much easier (as far as we can tell) than answering "what protein will fold like this?" It may well be that these are substantially computationally easier than we currently think. Heck, it could be that P=NP, or it could be that even with P != NP that there's still some extremely slow growing algorithm that solves NP complete problems. But these don't seem like likely scenarios unless one has some evidence for them.

I just found this nice quote on The Last Conformer which is supposed to prove that betting on major events is qualitatively different from betting on coinflips:

I wouldn't even offer bets on this kind of probability because that would just invite better informed people to take my money.

It seems to me that the problem exists for coinflips as well. If I flip a coin and don't show you the result, your beliefs about the coin are probably 50/50. But if I offer you to bet at 50/50 odds that the coin came up heads, you'll probably refuse, because I know which way the coin came up and you don't.

According to the Dutch book argument for rationality, we are supposed to accept either side of any bet offered at the odds corresponding to our beliefs. In my example, that idea breaks down, because getting the offer is evidence that you shouldn't take the bet. But then how do we formulate the Dutch book argument?