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.
I am not familiar with it, feel free to link or explain...
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.