Envelopes and limits

A tricky trick from D-squared, since we all know that having to solve a math problem under time pressure is Hell. Real questions: are there two hells? And how can we choose between them?

Maybe … my aim (I’m most definitely not sure I’ve achieved it) is to suggest that the real guts of these paradoxes is not something to do with limits but more likely that they all come down to something similar to the assumption that names which look like they refer to something actually do so.

Basically, there is a particular class of exponential diophantine equations which have the property that you can’t tell whether they have a solution or not unless you can also solve the halting problem for a Turing machine. So, if you are working on problem 1 and being offered the option to switch to problem 2, then you are being offered something fairly analogous to the deal in Brian’s second, coin-tossing version of the envelope problem; a choice between a process that might take a finite time or might take forever, and a process which also might take a finite time or take forever, but which appears to be stochastically dominated. Except that in this case, there’s no issue of taking limits; your uncertainty is right there as soon as the problem is posed.

F*ck the equations. Make yourself comfortable. Order room service. Tell the angel you need to hire some staff – intermediate terms administrator (x2), infrastructure support (x4), office manager. Take them on team-building exercises. Hell only starts when you finish. The angel has made a MAJOR mistake.

If I understand correctly, your only chance to switch is after 1 week. At that point, you will be stuck with one problem, and if it is unsolvable then you will spend eternity in Purgatory (I assume that the problem takes place there, since the other ones did. You don’t specify, though.) I will henceforth refer to “eternity in Purgatory” as “Hell”. (If my understanding is wrong, and you intend to let people switch back and forth weekly, like some commenters imply, then the rest of my posting is moot.)

The “paradox” only comes up if the subject cannot determine whether the problem is solvable within a week. If so, then they basically have a 50% chance of staying in Hell and a 50% chance of a finite time in Purgatory. There’s no way to tell which is which… basically, this boils down to the angel saying “I’ll flip a coin. If you lose, you go to Hell, but if you win, you eventually go to Heaven.” There’s no paradox there, just a very tense gambling situation.

The “1 day less” aspect is equivalent to the angel saying “If you choose Heads and win, you’re Purgatory time will be less than if you choose Tails and win.” Again, no paradox (though it may raise questions about whether the angel is trying to trick you)…just a gamble with different results for different choices.

A nearly optimal solution to this problem is to spend equal amounts of time on each envelope (perhaps a week at a time on each?) constantly switching back and forth.

If you are forced to re-start your calculations after each switch, then the optimal solution probably involves spending ever-increasing amounts of time on each (such as one week, then two, then four, etc.)

If you only can switch once, you should (though when is up to you). Using the halting problem (which I understand better) as an argument, I would say that while it’s impossible to come up with an algorithm that determines whether an arbitrary TM will halt on an arbitrary input, a machine that will halt tends to do so sooner rather than later. So the longer I work on a TM without it halting (or showing obvious signs that it won’t), the more likely I am to want to switch.

Look at it this way. Say that the average (TM + input) of length N that is going to halt does so in D days with a probability roughly proportional to 2^(-D). Of course, the actual numbers will vary considerably from this, but it serves as a reasonable model. Anyway, we know that (according to the article linked in this post) the probability of a random (TM + input) of length N halting is in itself a random variable with a more or less uniform distribution in [0, 1].

Now, unless the Angel is trying to trick us by making our first TM a particularly long-running (but halting) one, we can come up with a good strategy. Note that we assign both TM’s a prior probability of halting of 50% (the average probability of halting, because we don’t know any better). Now, if we’ve spent any time on the first TM and it doesn’t halt, the probability that it is going to halt is reduced. We can then safely switch to the second TM. However, the longer we spend on the first TM, the more certain we can be that we’re not abandoning the one that will send us to heaven. BUT, if we work on the wrong one, we will stay in purgatory forever instead of going to hell and then heaven. So, we balance the possibility of an eternity running TM simulations in purgatory against the (ever-increasing) amount of hell-time we’ll have to suffer, and make a decision of when to switch.

What makes this problem distinctly different from the others is that by working on the first problem, we get at least some information about it that lets us make a more educated choice later on. We still have nice probabilities, and in this case, we probably don’t even have to take limits.

Given the Angel’s track record in Brian’s problems, you should certainly assume it is “quite likely” (where “quite likely” is a probability not estimable by any alogrithmic procedure) that he is trying to put one over on you in exactly this manner.

Ah. Well, then he’s probably picked a problem with a ridiculously long solution time, so even if you do manage to solve it you’re spending a tremendous amount of time in hell. In that case, I might pick one of the problems and just not work on it very hard, so that I never leave purgatory.

The exact point that Chaitin makes is that there is no procedure with a well-defined halting probability which can tell whether particular Diophantines have a finite or infinite number of solutions.

I’m not sure that’s what it’s saying. What it seems like to me is (a) there is no algorithm that can tell you whether there is a solution for an arbitrary Diophantine equation, and (b) the probability that a member of the set of Diophantine equations with representation length N has a solution is entirely random (distributed uniformly in [0, 1]) for any N.

Now, that’s not to say that we don’t get any additional information by working on the problem a little. Like I said, I don’t know much about Diophanes, but the article seemed to suggest that finding solutions was equivalent to solving the halting problem. This would make the set of equations with solutions recursively enumerable, not undecidable. Since there are at most 2^N equations with representation length N, the set of such equations is finite, and therefore the subset of equations with solutions must be null or finite.

There is, therefore, a maximally difficult solution to find (in terms of computation time) among the solvable Diophantines of length N. The problem is that for arbitrary N, we have no idea what that computation time is, or even how many of the equations of length N are solvable (if any). If we knew what that maximally difficult solution was, we could just do that much computation and see if we solved the equation or not. However, it can be shown that not only do we not know the computation length for the hardest problem in the set of length N, but that T(N) in general is not bound above by any computable function!

However, there is also a minimally difficult solution for the set of problems of encoding length N. Through the magic of padding, at least in the halting problem, it is possible to come up with a number of problems of length N that halt in an very short time. I suspect the Diophantines problem is the same way. So, by doing even a little bit of computation, you can eliminate some of the possible equations with solutions.

Now, since we don’t know the probability that a problem of length N is solvable, eliminating a few possibilities by doing a little computation not only suggests that the particular problem you have is not in the set of problems with solutions, but also suggests that the probability of solution for length N is less than 50%. The two might balance each other out, but by doing some hand-waving, and invoking the same magic that inspires the tau distribution, I think you can make the argument that the overall chance you have a bad problem increases with the time you spend on it. Determining exactly how much it increases, though, is beyond my mathematical ability.

Doesn’t this just show that the real interest of the supposed paradox lies much less deep? The original issue appears to be simply soluble but that apparently simple solution produces impossible answers.

By this I mean the supposedly obvious calculation that switching boosts your expectation by 25%.

In this new case, anybody capable of jumping to a swift conclusion would probably be quite happy to remain in purgatory doing maths in any case but will also be used to the strange behaviour of distributions with infinite expectation. In short, they may work hard to work out what the right solution is but they won’t find it paradoxical.

Dsquared,

“But the halting probability (the probability that any algorithmic process for solving the equation will halt in time T) is strictly unknowable … There is no way of making an estimate of the halting probability in step 1 (by which I mean, no algorithmic procedure which will ever deliver an informative estimate).”

I disagree fundamentally with much of this statement. However, it doesn’t change the basic point: once you put my limiting procedure in, there is no longer a dominance argument; it is no longer the case that, for all possible outcomes, you prefer envelope 1 to envelope 2. Therefore, no paradox.

…

Okay, just a few more points about the quote above.

1) Probability describes a state of information. Probability isn’t “unknowable,” you don’t “estimate” probabilities, as if they were facts about the world you are trying to discover. You assign them to be consistent with your information.

2) You may be arguing that no probability is consistent with the state of information given in the problem. You would have to show that, if we assign probability p, it leads to a contradiction for any p. I do not see this in the paper (although I may not recognize it if I see it).

Even if it were true that there is no consistent probability, it doesn’t produce a paradox, it merely doesn’t give an answer. (What is the probability that “This sentence is false” is true? No answer, but no paradox either, any more than “What is the probability that Bill is six feet tall given that he is less than five feet tall and more than seven feet tall?”)

3) The paper’s use of the word “random” blurs the distinction between uncertainty (not knowing what will happen) and complexity (irreducibility). Probability theory models uncertainty, dynamic systems theory models complexity. I claim that you shouldn’t “mush” the two together; you should analyze the unknown and the complex separately, then put them together using standard mathematical tools.

ping

I think this problem still has a badly-behaving limit in it.

Here’s a rough sketch of how the argument goes (rough, because my knowledge of complexity theory is). With a Turing machine, the amount of addressable memory is proportional to the length of time it runs, and the size of the state space is proportional to the exponent of the memory used. So the maximum number of possible solvable equations rises exponentially with the amount of time your Turing machine can run. As a result, you get an ill-defined expectation when you try to compute the mean expected runtime of the terminating Diophantine exponentials — you don’t have a proper limit.

I think the best you can do is to take Dave’s suggestion: alternate between the two problems, and rely on the fact that -one- of them is (allegedly) guaranteed to terminate. At worst you’ll take twice as long as if you had picked the right one and worked on it exclusively.

Dsquared,

“There isn’t a well-behaved limit as N goes to infinity in this case”

If this is true, that means there is no answer, not that there is a paradox. Once you formulate it as a limit (even if the limit doesn’t exist), there is no sure-thing argument like there is in standard two-envelope problems (i.e. no matter what you see in envelope one, you prefer it to envelope two with its “infinite expectation”). Once that argument disappears, the paradox disappears as well.

Also, your argument seems to imply that we can’t solve even a finite problem: say N is the maximum time you are allowed to spend in Hell solving the problem (You’ve not been that bad, God can’t justify keeping you in there longer :-). Can you solve the problem now? It seems not if you claim that the probabilities “are unknowable.”

If you can’t solve the finite problem, then this is a different sort of difficulty than in Brian’s two-envelope problem.

Also, your argument seems to imply that we can’t solve even a finite problem: say N is the maximum time you are allowed to spend in Hell solving the problem.

What does the problem even mean if you limit the time you’re permitted to stay?