I've been trying to understand in light of a few apparent paradoxes for me. It appears reasonable that we could prove any mathematical problem that has a well defined answer can be solved by a mathematician (or group) given enough time. Yet, this is known to be false due to the existence of the halting problem (and other undecidable series of problems): any mathematician with unlimited time and paper is not guaranteed to be able to prove whether a problem halts.
1. Are the interesting problems that we do solve part of an infinite class $P_D$ of decidable problems? (or are we bound to only be able to solve finitely many "interesting" problems?)
Alternatively, I think this may be phrased as
1b. What is the largest known class $P_{max}$ of decidable problems?
I've been trying to put 1b in more rigorous terms. Define a partial halting solver as a program that outputs $1$ if it finds a proof that an input halts, $0$ if it proves that it does not halt and $2$ if it is unsure.
We might seek the best of this partial solvers, ordered defined by some metric:
$$M(P) = \liminf_{n \to \infty} \frac{1}{n} \sum_{i=1}^{n}{D_i}$$
Where $D_i = 1$ if input $i$ yields output $0$ or $1$ by some program $P$.
Indeed we easily can see there must exist a program with positive $M$. For example, all programs with the following prefix don't halt (assume without loss of generality that it uses the C language):
- for(i=1;i!=0;i++){}
Since this prefix has $19$ characters $c \in [0,255]$, we know that at least $1$ every $256^{19}$ program of length greater than $19$ will be known not to halt, hence $\max\limits_P{M} \ge \frac{1}{256^{19}}$.
Is there a known bound on $M$, giving $P_{max}$?
I welcome any references that would help me understand those questions better.