<p>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$.</p>

<p>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}) &amp; \text{if $x \mathop{\%} 10^{6}=0$} \\
0 &amp; \text{otherwise.} \end{cases}
$$</p>

<p>It's equally clear that $g$ is undecidable. However, informally it seems that there should be some sense in which $g$ is <em>less</em> 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.</p>

<p>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. </p>

<p>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.)</p>

<p>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.</p>

CC BY-SA 3.0
2014-04-15T07:44:49.350Z
Somewhat related: [The halting problem is decidable on a set of asymptotic probability one](http://arxiv.org/abs/math/0504351).
Marzio De Biasi
CC BY-SA 3.0
2014-04-15T11:00:39.443Z
I think there have been a couple f questions about the density of undecidable problems on MathOverflow and [math.se]. 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$.
Kaveh
CC BY-SA 3.0
2014-04-15T15:10:40.347Z
the boundary of decidable/undecidable is an active/ongoing area of research. this seems to relate to chaitins study of [Omega](http://en.wikipedia.org/wiki/Chaitin's_constant). see also a recent proof sketch by YF against existence of [probabilistic halting detectors](http://cs.stackexchange.com/questions/21581/possible-to-construct-a-probabilistic-halting-problem-solver). have done empirical experiments that show many random "small" TMs are decidable. etc. anyone interested plz reply in [chat]
vzn
CC BY-SA 3.0
2014-04-17T04:06:49.663Z
see also [ratio of undecidable problems](http://cs.stackexchange.com/questions/155/ratio-of-decidable-problems) cs.se
vzn
<computability>
density of undeciability
N. Virgo
# density of undeciability

(Asked by: username_0 on 2014-04-15)

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.

**Tags:** computability

> **Comments:**
> **username_1**: Somewhat related: [The halting problem is decidable on a set of asymptotic probability one](http://arxiv.org/abs/math/0504351).  
> **username_2**: I think there have been a couple f questions about the density of undecidable problems on MathOverflow and [math.se]. 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$.  
> **username_3**: the boundary of decidable/undecidable is an active/ongoing area of research. this seems to relate to chaitins study of [Omega](http://en.wikipedia.org/wiki/Chaitin's_constant). see also a recent proof sketch by YF against existence of [probabilistic halting detectors](http://cs.stackexchange.com/questions/21581/possible-to-construct-a-probabilistic-halting-problem-solver). have done empirical experiments that show many random "small" TMs are decidable. etc. anyone interested plz reply in [chat]  
> **username_3**: see also [ratio of undecidable problems](http://cs.stackexchange.com/questions/155/ratio-of-decidable-problems) cs.se  

---

## 0 answers

