[edanm]

I still don't see how you can be confident that the Turing Machine that solves your problem isn't an exponential amount "down" in the list of Turing machines. What if its size is 2^n for problem size n?

Also, more importantly, I still don't see how Universal Search solves what parent actually said, which is that even without knowing the algorithm this will work. The link you added seems to suggest you need to know the actual P algorithm for this to work.

[stephencanon]

It doesn't matter how far down it is. It has some constant index independent of the problem size, so for "large enough" problems, it's just a constant factor on the time required.