3
$\begingroup$

Can the following two statistics be bounded:

  1. the proportion of halting programs vs non-halting programs
  2. 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.

$\endgroup$
  • 1
    $\begingroup$ Does this paper approach the sort of questions that you're interested in? arxiv.org/abs/math/0504351 $\endgroup$ – Sam Jones Jul 17 '14 at 15:19
  • $\begingroup$ questions of this type are extremely theoretical and at the edges of what is knowable (aka terra incognita) and there are very few results/theorems in the area (other than eg Chaitins research). yes there are many angles on this question & some rough analysis can be done incl empirically eg see this recent tcs.se question asymptotic density of ambiguous CFGs $\endgroup$ – vzn Jul 17 '14 at 18:38
2
$\begingroup$

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$:

  1. (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$.
  2. (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$.
  3. 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.
$\endgroup$
  • 1
    $\begingroup$ There is a well-defined notion of asymptotic density, at least in the countable case. For example, there are asymptotically more composites than primes even though both sets are countably infinite. $\endgroup$ – Yuval Filmus Jul 17 '14 at 3:44
  • $\begingroup$ Given any $0 \leq \alpha \leq \beta \leq 1$ where $\alpha$ and $\beta$ are computable real numbers, one can easily construct an effective enumeration of the set of all programs such that the halting programs have lower asymptotic density $\alpha$ and upper asymptotic density $\beta$. $\endgroup$ – Amit Kumar Gupta Jul 17 '14 at 4:06
  • $\begingroup$ Kudos on the asymptotic remark... However I don't see how we can enumerate asymptotically more halting programs :( $\endgroup$ – user13675 Jul 17 '14 at 4:31
  • 3
    $\begingroup$ "All aforementioned infinities are the same countable infinity" -- wrong. The set of all languages is uncountable, the set of decidable languages is countable, and hence the set of undecidable languages is uncountable. $\endgroup$ – Raphael Jul 17 '14 at 8:02
  • 1
    $\begingroup$ @AmitKumarGupta That would be non-standard then. I assume languages $L \subseteq \Sigma^*$ for some countable alphabet $\Sigma$. Since $\Sigma^*$ is countable, there are as many such languages as there are functions $\mathbb{N} \to \{0,1\}$, and this set is uncountable. In other words, the set of all languages is $2^{\Sigma^*}$, i.e. the power set of a countably infinite set, and hence uncountable. $\endgroup$ – Raphael Jul 17 '14 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.