This seems like a good example to have at hand. I'm skeptical that it's much easier than what we really care about, but I guess we'll see (eventually).
Rather than a very big physical computer, it might be a bit easier to imagine a world full of (stochastic) hypercomputers that can solve their own (stochastic) evaluation problems, i.e. reflective oracles. This involves reflection but not computational limitations, so seems to capture a lot of what you care about without including the whole AI problem.