So, for statements like “the billionth digit of pi is even”, it’s provable from your beliefs. But you’re still uncertain of it. So, the problem is, what’s its probability? Well, 1⁄2, probably, but from what principled theory can you derive that?
I don’t mean to butt in, but for God’s sakes, can somebody please tell me what keywords to search in order to find Solomonoff or Kolmogorov-type work for putting a probability measure on countably infinite sets of structured objects? Is this just a matter of defining the correct \sigma-algebra, with countable additivity of subsets? The actual problem here is very simple: it’s just a matter of taking the definition of an inductive type and putting a sensible probability measure over the resulting objects.
The problem is that you can’t just assign equal probability mass to each constructor (with parameterized constructors “containing” each possible tuple of parameters as an event inside their portion of the probability mass), as this results in believing (at least, as a prior) that 50% of all linked lists are empty.
I don’t mean to butt in, but for God’s sakes, can somebody please tell me what keywords to search in order to find Solomonoff or Kolmogorov-type work for putting a probability measure on countably infinite sets of structured objects? Is this just a matter of defining the correct \sigma-algebra, with countable additivity of subsets? The actual problem here is very simple: it’s just a matter of taking the definition of an inductive type and putting a sensible probability measure over the resulting objects.
The problem is that you can’t just assign equal probability mass to each constructor (with parameterized constructors “containing” each possible tuple of parameters as an event inside their portion of the probability mass), as this results in believing (at least, as a prior) that 50% of all linked lists are empty.
Why not start with a probability distribution over (the finite list of) objects of size at most N, and see what happens when N becomes large?
It really depends on what distribution you want to define though. I don’t think there’s an obvious “correct” answer.
Here is the Haskell typeclass for doing this, if it helps: https://hackage.haskell.org/package/QuickCheck-2.1.0.1/docs/Test-QuickCheck-Arbitrary.html
Because there is no defined “size N”, except perhaps for nodes in the tree representation of the inductive type.