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.
If it's worth saying, but not worth its own post (even in Discussion), then it goes here.