Density of halting Turing machines If we enumerate all Turing machines, $T_1$, $T_2$, $T_3,\ldots,T_n,\ldots$,
What is 
$$\lim_{m\to\infty}\frac{\#\{k\mid k\lt m \text{ and }T_k\text{ halts}\}}{m}\quad?$$
Or does this depend on how we enumerate them ?
 A: As I pointed out in the comments above, if the enumeration isn't required to be computable, then the value of the limit definitely depends on the enumeration. In fact, it depends upon the enumeration anyway. To wit, fix two machines $T$, which halts, and $S$, which doesn't halt. Given an enumeration (computable or not), use the padding lemma to insert $T$ frequently enough into the enumeration (thus creating a new enumeration) to ensure that the limit is 1. Or do the same with $S$ to ensure that the limit is 0.
A: This question is exactly the theme of my article, "The halting problem is decidable on a set of asymptotic probability one,"  (J. D.
Hamkins and A. Miasnikov, Notre Dame J.
Formal Logic 47, 2006, various links available at http://boolesrings.org/hamkins/haltingproblemdecidable/).
Similar questions have arisen several times on mathoverflow:


*

*Probability that Turing
machine is
universal?

*Solving NP problems in (usually) polynomial
time?

*Turing machines the read the entire
tape?

*Proability a random Turing machine is
DFA?

*Limits of
non-halting?
The answer is that it depends on the model of computation. (This fact comes after the issue of enumeration raised in the comments and in the answer of Quinn Culver, which seems partially addressed by the fact that we have several canonical enumeration of Turing machine programs based on the fact that for any $n$ there are only finitely many programs having $n$ states.)
One of the ideas is that it may be more natural to consider the asymptotic density  of the desired set of programs, by considering the limit of the proportion of all $n$-state programs with the property, as $n$ goes to infinity. This seems to avoid the trivializing effects of arbitrary rearranged enumerations.
For example, here is one easy thing to say. Suppose that
your Turing machines have alphabet $\{0,1\}$, a set $Q$
of $n$ states, a single halt state (not counted inside
$Q$), and the ability to move the head left and right, so
that a program is a function $p:Q\times\{0,1\}\to
(Q\cup\{\text{halt}\})\times\{0,1\}\times\{\text{left},\text{right}\}$,
where $p(s,i)=(t,j,\text{left})$ means that when in state
$s$ reading symbol $i$, the program changes to state $t$,
writes symbol $j$ and moves left. In particular, for this
model the total number of programs is $(4(n+1))^{2n}$.
Consider now the collection of programs that have no
transition to the halt state. The total number of such
programs is $(4n)^{2n}$, and the interesting thing here is
that $$\lim_{n\to\infty}{(4n)^{2n}\over
(4(n+1))^{2n}}=\lim_{n\to\infty}[{n\over
n+1}]^{2n}=\frac{1}{e^2}$$ which is about 13.5%.
Thus, for this model of computation, at least 13.5% of the
programs never halt on any input.
The topic is fun, because we are in effect considering the
behavior of a random program, where each new program line
is chosen randomly from among all the legal program lines.
The main theorem of my article with Miasnikov is the
following.
Theorem. There is a set $A$ of Turing machine
programs (for machines with one-way infinite tape, single
halt state, any finite alphabet) such that:


*

*One can easily decide whether a program is in $A$; it is polynomial time decidable.

*Almost every program is in $A$; the proportion of all
$n$-state programs that are in $A$ converges to $1$ as $n$
becomes large.

*The halting problem is decidable for members of $A$.


Thus, there is a decision procedure to decide almost every
instance of the halting problem. The way the proof goes is
to calculate, for any fixed input, the probability that a
Turing machine will exhibit a fatally trivializing behavior
(falling off the left end of the tape before repeating a
state), and observing that in fact this occurs with
probability $1$. Basically, the behavior of a random Turing
machine is sufficiently close to a random walk that one can
achieve the Polya recurrence phenomenon.
Corollary. For this model of computation, for any enumeration listing the programs in order of the number of states, your limit is $0$. 
The reason is that the probability that an
$n$-state program is halting (in the sense of reaching the
halt state) goes to zero as $n$ becomes large, since almost
every program exhibits the trivializing behavior of falling
off the tape. Furthermore, the set of programs with that
behavior is decidable.
The theorem can be extended to other models of computation,
such as the model with two-way infinite tapes and halting
determined by specifying a subset of the states to be
halting states. In this model, as you can guess, machines
are likely to halt very quickly (since each new state has
50% chance of being halting), and in particular, the halting problem
becomes decidable for this reason.
Theorem. For the halting state model of computation, for any enumeration listing the programs by the number of states, your limit is $1$. 
A: Hamkins & Miasnikov's result answers the first part of your question: for Turing machines as we typically model them, you can approximate the halting problem. Quinn's reasoning also shows that you can easily change the way you enumerate programs to get any limit you want.
Now, can you say interesting things about interesting kinds of enumerations? There is one particularly natural class of enumerations: optimal ones. An enumeration $A_1, A_2, ...$ is optimal if for any other enumeration of programs $B_1, B_2, ...$ there exists a constant $K$ such that every program $B_i$ is equivalent to some program $A_j$ with $j<i+K$. These are the same building blocks that you use to define Kolmogorov complexity.
For those, if you define:
$$p_m = \frac{\#\{k\mid k\lt m \text{ and }A_k\text{ halts}\}}{m}$$
you get a very interesting sequence. This sequence does not converge, and all of its accumulation points are $\emptyset'$-random, which mean that their binary expansion is incompressible, even for a Turing machine with access to an oracle giving the answer to the halting problem (see this Wikipedia article for more details).
We can also say interesting things about $\limsup_m p_m$: not only is it $\emptyset'$-random, but it's also $\emptyset'$-upper-semicomputable (which means upper semicomputable by a Turing machine having access to a halting problem oracle). Oh, and both conditions are equivalent: given any $\emptyset'$-random, $\emptyset'$-upper-semicomputable number between $0$ and $1$, you can build an optimal machine having this number as the $\limsup_m p_m$ for this machine.
These results appear in a paper
I co-authored about this problem, and some related questions. It was published at ICALP 2015, and the long version was later published in LMCS.
