A Request for Open Problems

It only took 7 years to make substantial progress on this problem: Logical Induction by Garrabrant et al..

Scott Aaronson and many others in his field have essentially bet their careers that P ≠ NP (at least, I think the whole hierarchy of complexity classes would collapse if P = NP), while only a bunch of cranks (so far as I've heard) have bet a substantial amount of their life's efforts on P = NP. That's as good a statement of betting odds as any.

As for whether it's legitimate to do so, well, that's Bayesian probability for you. You've got to have some way of dealing with subjective uncertainty, and you get better results in the long run if your method of dealing with it is like unto the laws of probability.

Here are some papers I found recently that seem to represent the state of the art on the issue of how to deal with uncertainty in mathematics. None of them really get very far beyond "let's try to apply probability theory", but at least the problem is not being completely ignored by mathematicians and philosophers.

• Bayesianism in mathematics, a book chapter in Towards a Philosophy of Real Mathematics by David Corfield
• Non-deductive Logic in Mathematics, by James Franklin
• Bayesian Networks for Logical Reasoning, by Jon Williamson

(Retracted; useless speculation.)

I suspect the answer is no, at least not the kind of formal languages that have been suggested so far. The problem is this: as soon as you define a formal language, I can say "the lexicographically first object which can't be described in less than a million bits in your language". Given the uniqueness of this object, why should it be a priori as unlikely as a random million-bit string?

That depends on what you mean by "best".

Is speed of calculation important? What about suitability for humans? I guess you want one where complexities are as small as possible.

Given 2 languages, L1 & L2, and their complexity measures, K1 & K2.

If K1(L2) < K2(L1) then I take that as a sign that L1 is better for use in the context of Ockhams razor. It is also a sign that L1 is more complex than L2, but that effect can be removed by doing lots of comparisons like that, so the unnecessarily complex languages loose against those that are actually good. Or one can use 3 languages in a comparison: K1(L3) < K2(L3) is a sign that L1 is better.

The idea here is that a good language should more easily represent systems, such as other languages.

What sort of languages are best in this measure? Not the simplest ones, but rather the more expressive ones. Programs for Turing machines use some complexity for tape traversing and storage systems, so I guess they are not so good. Cellular automata have the same problems. Combinatory Logic is very simple, with complex operators even for simple stuff, but its system for storage and access can be simpler, since it is a tree. I guess Lambda Calculus is one of the better languages, as it is both simple and very expressive, because of its more direct tree structure.

I guess the best language would use an even more expressive structure, such as graphs, perhaps bi-graphs, since those are maximally expressive. The Scheme language can be used as a general graph language thanks to the set-car! and set-cdr! procedures.

As I pointed out in that thread, their solution doesn't work. You would need to choose an aggregation mechanism to combine votes. Different mechanisms will cause different systematic outcomes. Notably, some mechanisms will result in always choosing actions from one category; some mechanisms will result in sampling from different categories proportionally to their votes (much as, eg., the American system always chooses the most popular candidate, resulting in a 2-party system equilibrium; many European systems allocate seats proportionally to votes, allowing equilibria with more than 2 parties.)

You need to choose which kind of outcome you prefer in order to choose your aggregation mechanism, in order to implement their solution. But if you could do that, you wouldn't need their solution in the first place!

It's still a great question. I do not know how far we can get formalizing it, but my hunches tell we could get pretty close.

Scott Aaronson has a STOC paper on this: http://arxiv.org/abs/cs.CC/0406061

If there were a common pattern, you could sample the opinions in a population, or over time, and estimate how much longer it would take, or how much knowledge would be needed, to arrive at a correct opinion.

Some people like mathematics so much that they define it as encompassing all clearly defined problems. Some people like philosophy so much that they define it as encompassing all problems whatsoever. Both of these definitions are clearly wrong, and the product of affective death spirals.

You say that as if a problem can only belong to one field.

See Wikipedia's list for a few examples.

The distinction between clearly defined and otherwise is somewhat subjective. I have not heard anyone talking about the subject yet, so brought it up.

Since Rationality seems to be strongly related to Bayes' theorem, it makes some sense that a lot of problems could be presented in a fashion where we only have to answer a few questions about priors to understand which actions to take.

I don't know if this answers your question.

I think that problem is too hard for us. As a general rule, sweeping definitions made without respect to a particular purpose are of limited utility. But thanks for commenting, and please don't let my response deter you from commenting again.

Quite a bit is known about the neurology behind face recognition. No one understands the algorithm well enough to build a fusiform gyrus from scratch, but that doesn't mean the fact that there is an algorithm is mysterious.

"The uniform distribution centered at c" does not seem to make sense. Did you perchance mean the Gaussian distribution? Further, 'deviates' looks like jargon to me. Can we use 'samples'? I would therefore rephrase as follows, with specific example to hang one's visualisation on:

Heights of male humans are known to have a Gaussian distribution of width 10 cm around some central value ; unfortunately you have forgotten what the central value is. Joe is 180 cm, Stephen is 170 cm. The probability that is between these two heights is 50%; explain why. Then find a better confidence interval for .

A lot of our irrationality seems to be rationality tuned for small sample sizes. When you live in a tribe of <200 people, any given event or opinion has a lot of weight. We evolved to do science on a small scale. How do we get around Dunbar's limit?

This isn't a formal problem that can be "solved" with a formal solution. I am specifically talking about problems like the Angel problem or P = NP.

Examples I can think of from the top of my head are Newcomb's problem and the Prisoner's dilemma. Both of these can be expressed formally with Bayesian terms. Have the problems been solved? I assumed so or I would have brought them up in my post.

For fun, I am starting to work out what is needed to tackle Newcomb's problem and it certainly seems doable. I figured it is a good test of my new Bayesian skillz. Game theory claims to have "solved" one-shot PDs but not in a way that makes sense in helping someone decide what to do in a real life example. Newcomb's seemed easier so I am starting with that.

If all humans currently alive collectively represent every possible variable combination in this regard, the maximum value for the answer is 32.7 bits[1]. That is, 33 on/off switches completely decide whether or not you will put off doing your homework[2]. Is the correct value higher or lower?

Much, much higher. The humans currently alive represent only a very sparse sampling of possible combinations of genes, and an even sparser sampling of possible combinations of life experiences. I don't see any obvious reason why the answer to this question shouldn't be greater than the number of subatomic particles in your body.

Well, it doesn't seem all that long to me. We're not in one of Eliezer's stories after all.

And if you get enough philosophically-minded folks around a table, we spend the first hour or so talking about the table, and then the next hour or so talking about our discussion of the table.

EDIT: changed 'they' and 'their' to 'we' and 'our'