If you presuppose that the universe is not "mathematically possible", you can't really prove that it is possible for anyone to ask it that question. For that matter, it might just say "it halts" and be right. (It's a mathematically impossible world, and you're using math both when you're deciding what the algorithm will do and what the box should answer.)
By the way, the usual statement for the halting problem is that you can't make an algorithm that solves it, and by algorithm it usually means something a Turing machine, i.e. everything the algorithm does can be done by a Turing machine. In this case, assuming it makes sense to use math to reason about it, “Feed this algorithm to the magic box” is not actually something a Turing machine can do (it only has heads and tapes, no magic boxes). If you also give it the magic box it's no longer just a Turing machine, it's a [Turing machine + Turing oracle], which is something a bit different.
Imagine the magic box accepts algorithms expressed in Lisp (which theoretically allows unlimited memory). How do you express "feed something to the magic box" in Lisp?
By the way, does anyone know if it's proven impossible (or even if discussed) to build a limited halting-problem solving algorithm that works for all algorithms except those that contain (complete or limited) halting solver algorithms as subroutines, in which case they also halt but say something like "don't be an ass"?
There are at least ten different conceptions of how the World can be made of many worlds.
But are those just definitional disputes? Or are they separate claims that can be evaluated. If they are distinct, in virtue of what are they distinct. Finally, do we have good grounds to care (morally) about those fine distinctions?
Max Tegmark's taxonomy is well known here.
Brian Greene's is less, and has 9, instead of four, kinds of multiverse, I'll risk conflating the Tegmark ones that are superclasses of these, feel free to correct me:
I don't understand branes well enough (or at all) to classify the others. The holographic one seems compatible with a multitude, if not all, previous ones.
Besides all those there is David Lewis's Possible Worlds in which all possible worlds exist (in whichever sense the word exist can be significantly applied, if any). For Lewis, when we call our World the Actual World, we think we mean the only one that is there, but what we mean is "the one to which we happen to belong". Notice it is distinct from the Mathematical/Ultimate in that there may be properties of non-mathematical kind.
So Actuallewis= Our world and Actualmost everyone else=Those that obtain, exist, or are real.
The trouble with existence, or reality, is that it is hard to pin down what it is pointing at. Eliezer writes:
and elsewhere
Now another interesting way of looking at existence or reality is
Reality=I should care about what takes place there
It is interesting because it is what is residually left after you abandon the all too stringent standard of "causally connected to me", which would leave few or none of the above, and cut the party short.
So Existenceyud and Existencemoral-concern are very different. Reality-fluid, or Measure, in quantum universes is also different, and sometimes described by some as the quantity of existence. Notice though that the Measure is always a ratio - say these universes here are 30% of the successors of that universe, the other 70% are those other ones - not an absolute quantity.
Which of the 10 kinds of multiverses, besides our own, have Existenceyud Existencemoral-concern and which can be split up in reality-fluid ratios?
That is left as an exercise, since I am very confused by the whole thing...