Yep, modern probability theory is dependent on being able to define a sample space that has an associated sigma algebra. The problem posed by the examples (eg “this Turing machine halts”) is that we have no obvious way to construct such a sample space (that is non-trivial) apriori. The innovation here is that there seem to be at least two ways to construct proxy sample spaces based on some of the surrounding constraints provided in the problem definition (since an many cases the sample space is binary, as the original article notes). The authors last question is whether these two approaches (that seem incompatible) can be used together.

I think it would really interesting if you could demonstrate that such 'external' probabilities could improve reasoning to better than chance because it would suggest that the answer to logic problems is partially constrained by their formulation, however I have this sense that it might also be the case that for some questions (eg the haling problem example above) no information would be shared between the question an its constraints.