You can even write an algorithm that goes through all possible algorithms (universal dovetailer). Yet this algorithm doesn’t solve any problem. So you still have to select an algorithm to solve a problem.
You can even write an algorithm that goes through all possible algorithms (universal dovetailer)
The universal dovetailer runs through all possible programs, which is a superset of all algorithms. You can’t use it to get access to just the genuine algorithms in any algorithmic fashion- if you could you could solve the Halting problem.
I agree. That’s why is say “this algorithm doesn’t solve any problem”, it isn’t in a problem solving algorithm in the sense I used in my post. Any “just go through all XYZ” doesn’t solve my stated problem, because it doesn’t select the actual useful solution.
That’s not the issue here. The issue is more subtle. Dovetaling doesn’t go through every algorithm but goes through every program. That is, it runs a program whether or not that program will halt.
it isn’t in a problem solving algorithm in the sense I used in my post
I’m not completely sure what you mean by a problem solving algorithm. Variations of universal dovetailing that are very close to it can be problem solving algorithms by most reasonable notions of the term. Consider for example the following:
Proposition: If P=NP then there is an explicitly constructable algorithm which gives explicit solutions to 3-SAT in polynomial time.
Proof sketch: For a given 3-SAT dovetail through all programs. Whenever a program gives an output, check if that output is a solution to the 3-SAT problem. If so, you’ve found your answer. It isn’t too hard to see that this process will terminate in polynomial time if P=NP.
(I’m brushing some issues here under the rug, like what we mean by explicitly constructable, and there’s an implicit assumption here of some form of w-consistency for our axiomatic system.)
This sort of construction works for a large variety of issues so that one can say that morally speaking if an algorithm exists to do so something in some complexity class then dovetailing will find an example of such an algorithm.
You can even write an algorithm that goes through all possible algorithms (universal dovetailer). Yet this algorithm doesn’t solve any problem. So you still have to select an algorithm to solve a problem.
The universal dovetailer runs through all possible programs, which is a superset of all algorithms. You can’t use it to get access to just the genuine algorithms in any algorithmic fashion- if you could you could solve the Halting problem.
I agree. That’s why is say “this algorithm doesn’t solve any problem”, it isn’t in a problem solving algorithm in the sense I used in my post. Any “just go through all XYZ” doesn’t solve my stated problem, because it doesn’t select the actual useful solution.
That’s not the issue here. The issue is more subtle. Dovetaling doesn’t go through every algorithm but goes through every program. That is, it runs a program whether or not that program will halt.
I’m not completely sure what you mean by a problem solving algorithm. Variations of universal dovetailing that are very close to it can be problem solving algorithms by most reasonable notions of the term. Consider for example the following:
Proposition: If P=NP then there is an explicitly constructable algorithm which gives explicit solutions to 3-SAT in polynomial time. Proof sketch: For a given 3-SAT dovetail through all programs. Whenever a program gives an output, check if that output is a solution to the 3-SAT problem. If so, you’ve found your answer. It isn’t too hard to see that this process will terminate in polynomial time if P=NP.
(I’m brushing some issues here under the rug, like what we mean by explicitly constructable, and there’s an implicit assumption here of some form of w-consistency for our axiomatic system.)
This sort of construction works for a large variety of issues so that one can say that morally speaking if an algorithm exists to do so something in some complexity class then dovetailing will find an example of such an algorithm.