The proportion of halting programs vs non-halting programs, of decidable programs vs undecidable languages

Can the following two statistics be bounded:

• the proportion of halting programs vs non-halting programs

• the proportion of decidable vs undecidable languages

For example, can we say that one class is much larger than the other, almost all problems are such and such, or both are similar in size?

By Chaitin's argument on the Omega number, we know that the halting probability is undecidable, so it is difficult to obtain an exact statistic on the number (if not impossible). However, Omega numbers have been computed for specific universal machines for prefix-free programs using probability measures decreasing in length (cf. Calude et al.).

So are there known valid statements about these proportions? My intuition (following the argument of the scarcity of life in the universe) would lead me to believe that there are much more undecidable languages than decidable ones. But it is only an intuition that is not backed.

EDIT: There are countably many recursive languages, and uncountably many non-recursive languages, so there are way more non-recursive languages.

There are countably infinitely many halting programs and non-halting programs alike. I can't think of an interesting structure you can put on the set of programs that includes a concept of "proportion" where you end up being able to say anything interesting about the proportion of halting programs, unfortunately.

For instance, one natural structure to put on the set of programs is to give them a computable well-ordering. One can make sense of questions about how big an infinite co-infinite subset of a countable set is if that countable set is well-ordered. For example, the notion of asymptotic density can give credence to the intuition that there are more non-square integers than there are integers. It basically says that the percentage of numbers that are not square tends towards 100% as you consider larger and larger finite initial segments of the naturals. Asymptotic density makes sense for subsets of the naturals which have a canonical (computable) well-ordering. The same cannot be said, however, for subsets of the set of all programs. Since there is no canonical enumeration of the programs, there's no canonical answer to the question of proportion of halting programs in terms of asymptotic density.

Proposition: If $0 \leq \alpha \leq \beta \leq 1$ where $\alpha, \beta$ are computable real numbers, then there is an effective enumeration of the set of all programs such that the lower asymptotic density of the halting programs is $\alpha$, and the upper asymptotic density is $\beta$.

Proof Sketch: Let $\pi_1, \pi_2, \dots$ be a computable enumeration of all programs. Let $\eta_n$ be the program:

print n
exit

Let $\nu_n$ be the program:

print n
loop {}

Note that $\eta_1, \eta_2, \dots$ is an effective enumeration of (some, obviously not all) programs that halt, and $\nu_1, \nu_2, \dots$ is an effective enumeration of programs that don't halt.

Let $0.a_1a_2\dots$ be the decimal expansion of $\alpha$, and $0.b_1b_2\dots$ the expansion of $\beta$. Note that since $\alpha, \beta$ are computable, the sequences $a_1, a_2, \dots$ and $b_1, b_2, \dots$ are also computable.

Our goal is to build an effective enumeration of all the programs such that the lower and upper asymptotic densities of the halting programs are $\alpha$ and $\beta$ respectively. We're going to build this enumeration in stages. Each stage is going to have 3 parts:

At stage $n$:

• (Sketch) Select programs from the front of the $\eta$ and $\nu$ lists that aren't already in our partially-constructed enumeration so far, and append them to the partial enumeration. In this selection of programs, the proportion of $\eta$ (halting) programs chosen should be $0.a_1a_2\dots a_n$. Select a lot of programs so that the proportion in the overall list (what had already been construct plus what has just been appended) is pretty close to $0.a_1a_2\dots a_n$ as well. If we do this carefully at each stage $n$, we can assure ourselves that the lower density of the halting programs will be $\alpha$.

• (Sketch) Do the same thing, this time so that the proportion of halting programs in the selection is $0.b_1b_2\dots b_n$. Again, select a lot so that after appending these programs to the list so far, the overall proportion is close to $0.b_1b_2\dots b_n$. If we do this carefully, we assure ourselves that the upper density of the halting programs will be $\beta$.

• If $\pi_n$ isn't already in the list, append it to the end. This ensures us that the enumeration we're building really does enumerate all the programs.

StackExchange Computer Science Q#28475, answer score: 3