I just edited the above comment, because I had forgotten about Kolmogrov complexity, and in particular how K-complexity varies only by a constant between turing-complete machines. That link should explain it pretty well; now that I remembered this I'm significantly less convinced that the problem is isomorphic.