<p>Let <span class="math-container">$TM(k,2)$</span> be the set of Turing machines with <span class="math-container">$k$</span>-states and <span class="math-container">$2$</span> symbols.  Let <span class="math-container">$h(k)$</span> be the number of machines in <span class="math-container">$TM(k,2)$</span> that halt when run on the blank input.</p>
<p>Is
<span class="math-container">$\lim_{k \to \infty} \frac{h(k)}{|TM(k,2)|} = 0$</span>? That is, do most Turing machines not halt?</p>
<p>I guess related to this, I would be interested in hearing about any non-trivial bounds on <span class="math-container">$h(k)$</span>.  I guess as a variation, I would be interested in bounds for the smaller function <span class="math-container">$h_{all}(k)$</span> that counts the Turing machines on <span class="math-container">$k$</span>-states that halt on all possible inputs.</p>
<p>I am sure precise bounds depend on the specific model of Turing machines, however maybe the above limit question does not.</p>
<p>Thanks for the thoughts!</p>

CC BY-SA 4.0
2021-06-29T13:23:52.817Z
It is also related to the chosen enumeration. A similar question (and good answer) can be found [here](https://math.stackexchange.com/questions/73187/density-of-halting-turing-machines).
Marzio De Biasi
CC BY-SA 4.0
2021-06-30T07:22:40.057Z
Thanks @MarzioDeBiasi - following your link, we get to another [answer](https://mathoverflow.net/questions/70397/turing-machines-that-read-the-entire-program-tape/70453#70453) that says that the above limit is in fact 1.
user101010
<computability><turing-machines>
Halting behavior of a randomly selected Turing machine?
user101010
# Halting behavior of a randomly selected Turing machine?

(Asked by: username_0 on 2021-06-29)

Let $TM(k,2)$ be the set of Turing machines with $k$-states and $2$ symbols. Let $h(k)$ be the number of machines in $TM(k,2)$ that halt when run on the blank input.

Is
$\lim\_{k \to \infty} \frac{h(k)}{|TM(k,2)|} = 0$? That is, do most Turing machines not halt?

I guess related to this, I would be interested in hearing about any non-trivial bounds on $h(k)$. I guess as a variation, I would be interested in bounds for the smaller function $h\_{all}(k)$ that counts the Turing machines on $k$-states that halt on all possible inputs.

I am sure precise bounds depend on the specific model of Turing machines, however maybe the above limit question does not.

Thanks for the thoughts!

**Tags:** computability, turing-machines
> **Comments:**
> **username_1**: It is also related to the chosen enumeration. A similar question (and good answer) can be found [here](https://math.stackexchange.com/questions/73187/density-of-halting-turing-machines).  
> **username_0**: Thanks @MarzioDeBiasi - following your link, we get to another [answer](https://mathoverflow.net/questions/70397/turing-machines-that-read-the-entire-program-tape/70453#70453) that says that the above limit is in fact 1.  

---

## 0 answers

