Is there a way to measure the number of Turing Machines for which the Halting problem can be solved?

Question

The Halting problem means that there is no algorithm which correctly determines whether an arbitrary program will halt. However, there may be a program which is able to correctly predict whether one program will halt given a certain input. For example, a program that just changes a single cell and then halts is easy to predict. The algorithm simply always outputs "Yes, it will halt." On the other hand, it is impossible to write an algorithm that can predict whether a Universal Turing Machine will halt given an arbitrary input, because that would solve the Halting problem, since Universal Turing machines can simulate any program given any input. In-between these two examples are Turing machines which sometimes halt and sometimes do not depending on the input, and for which an algorithm exists which always correctly says which will occur. For example, if the initial cell is 0, it will halt. If the initial cell is 1, it will not halt.

Is there an algorithm which can determine for all programs whether or not there exists an algorithm which can predict given a certain input whether it will halt? Note: this is not the same as the Halting problem because even if I can tell that the Halting problem cannot be solved for a given program, I still cannot tell which specific inputs are indeterminable. Is there some way to quantify the amount of Turing machines which have this property or don't probabilistically? Obviously since there are infinite Turing machines the choice would be somewhat arbitrary, but I guess I'm looking for something like "x % of programs with n states have an algorithm that predicts if they will halt."

Answer 1

Consider "two-part" programs $P_y$ parametrized by bit-strings $y$. Given input $x$, $P_y$ first simulates a universal Turing machine on the input $y$. If that halts, it then simulates a universal Turing machine on input $x$. Thus if $y$ happens to be an input for which the universal Turing machine runs forever, then $P_y$ will never halt, and your hypothetical algorithm should say "yes, there is an algorithm" (namely always say "it won't halt"). But if $y$ happens to be an input for which the universal Turing machine halts, then your hypothetical algorithm should say "no". Your hypothetical algorithm would thus have to solve the Halting Problem, and that is impossible.