Consider a function $f:\mathbb{N} \to \{0,1\}$ whose is defined in terms of some universal Turing machine $U$. If $U$ halts when given $x$ as input then $f(x)=1$, otherwise $f(x)=0$.

Clearly the function $f$ is undecidable. Now consider a new function $g:\mathbb{N}\to \{0,1\}$, defined by $$ g(x) = \begin{cases} f(x/10^{6}) & \text{if $x \mathop{\%} 10^{6}=0$} \\ 0 & \text{otherwise.} \end{cases} $$

It's equally clear that $g$ is undecidable. However, informally it seems that there should be some sense in which $g$ is less undecidable than $f$, since, informally speaking, it looks like the value of $g$ can be determined for $99.999\%$ of its inputs just by checking if they're divisible by a million.

My first question is whether there's any sense in which the intuitive claim that $f$ is more undecidable than $g$ can be made into a rigorous one.

If there is, I'm interested in whether there are any functions that are particularly "densely" undecidable. I have in mind something like a universal Turing machine that not only halts for about 50% of possible inputs, but also when it fails to halt it does so for a wide variety of different non-trivial reasons. (If this were not the case one could generate a second Turing machine to spot the majority of non-halting cases, so it wouldn't be densely undecidable.)

To ask more or less the same question in a different way: the vast majority of randomly-generated strings will halt immediately (with a compile error) if fed to a C compiler. The probability that randomly generated C code will fail to halt is very low, and the probability that it will fail to halt for some non-trivial reason is much lower still. I'm interested in whether one can define a language (or model of computation) that, when given random input, is quite likely to do something strange and non-trivial that makes its output difficult to predict.

  • 6
    $\begingroup$ Somewhat related: The halting problem is decidable on a set of asymptotic probability one. $\endgroup$ Commented Apr 15, 2014 at 7:44
  • $\begingroup$ I think there have been a couple f questions about the density of undecidable problems on MathOverflow and Mathematics. You may want to check them. Fixing a machine model (as your U does) one can define the density of halting problem for the model, however it is not a robust definition as slight changes in the encoding of machines in the model will change the result. You can take the limit of the bounded problem as the size of the input goes to $+\infty$. $\endgroup$
    – Kaveh
    Commented Apr 15, 2014 at 11:00
  • $\begingroup$ the boundary of decidable/undecidable is an active/ongoing area of research. this seems to relate to chaitins study of Omega. see also a recent proof sketch by YF against existence of probabilistic halting detectors. have done empirical experiments that show many random "small" TMs are decidable. etc. anyone interested plz reply in Theoretical Computer Science Chat $\endgroup$
    – vzn
    Commented Apr 15, 2014 at 15:10
  • $\begingroup$ see also ratio of undecidable problems cs.se $\endgroup$
    – vzn
    Commented Apr 17, 2014 at 4:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.