A Query regarding the Halting Problem (Omega): Halting Probability for Given Input Size I was studying the Halting Problem in context of the Probability and had a few doubts regarding it. Hope someone could help me out.
I am aware of the probability of a Random program halting on a Universal Turing Machine (with a randomly chosen input) is given by Chatin's Constant (which is normal and transcendental) number thus cannot be exactly computed.
My Query is the following:
Suppose one is given a Specific Universal Turing Machine Model (T) for doing all the computations. Also the following facts are given:


*

*The size of the randomly chosen Program (P) is 'at most' (Pk) bits. 

*The size of the randomly chosen Input (I) for the Program (P) is 'at most' (Ik) bits.


**The Program and Input are nothing but two randomly chosen strings.
Now given a random instance of a program and the Input for the Turing Machine (T) [with the size limits for Pk and Ik known]:
a. Is it possible for one to calculate the probability of any random  Pair halting on the Turing machine (T) ?
b. If not possible to calculate the exact probability (the value being transcendental) then the first few Most Significant Bits, let us say first Min(Pk, Ik) bits of the Probability i.e. just an aproximation ?
c. Is is possible to comment on a rather modified Probability Statement (and find an aproximation) which is as follows:
Probability(P, I, Lk) : Its defined as the Probability that a random  Pair will halt after exactly Lk Steps/Operations on the Turing Machine T ?
d. How do we go about finding it as the Chatin's formula is for an infinite Series?
Hope someone could help me out here.
 A: "
Hi Tarandeep, 
The halting probability for a random n-bit program certainly won't be transcendental -- in fact it's rational ( # halting progs / 2^n )! On the other hand, that probability clearly isn't computable given n as input, since if it was then you could use it to solve the halting problem. 
Hope that helps, 
Scott
"
Thanks to Prof. Scott Aaronson. 
A: One answer to your question is that it depends on the underlying model of computability you are using. 
Specifically, although this is a little different than your set-up, but for one of the standard models of computability---Turing machines with a one-way infinite tape and single halt state---Alexei Miasnikov and I proved that the halting problem is decidable with asymptotic probability one. See also this MO
answer and also this MO answer, in which I mention similar ideas, reproduced in part below.
Our idea was to use asymptotic density. For any natural number
$n$, there are only finitely many Turing machine program
using $n$ states. The asymptotic density or asymptotic probability
of a set $A$ of Turing machine programs is the limit (if it
exists)


*

*$\lim_{n\to\infty} \frac{|A\cap P_n|}{|P_n|}$,


where $P_n$ is finite the set of Turing machine programs
with exactly $n$ states. Thus, the asymptotic probability
of a set $A$ of Turing machine programs is simply the limit
of the proportion of $n$-state programs in $A$. In
particular, if a set $A$ has asymptotic density $1$, then
it means that more than $99\%$, more than $99.9\%$, of
Turing machine programs are in $A$, as close to $1$ as
desired as the number of states increases. In this case, we
would seem to be justified in saying that almost every
Turing machine program is in $A$.
To give an elementary sample calculation, a Turing machine
program $p$ in finite alphabet $\Sigma$ with states $S$
(not counting the halt state) is a function
$\Sigma\times S\to \Sigma\times
(S\cup\{halt\})\times\{L,R\}$. For example, if the alphabet
has $2$ symbols and there are $n$ states, then there are
$(4(n+1))^{2n}$ many programs. The number of programs that
never transition to the halt state, however, is
$(4n)^{2n}$, which has proportion $(\frac{n}{n+1})^{2n}$,
which goes to $\frac{1}{e^2}$ as $n\to\infty$. Thus, the
density of programs that never halt at all, because they
can never transition to the halt state, is $\frac{1}{e^2}$,
or about $13.5\%$. 
This way of thinking is the foundation of the topic of
generic case
complexity.
A central concern of this topic is the fact that many
undecidable or unfeasible decision problems admit a black
hole, a very small region where the problem is difficult,
outside of which it is easy. For example, it is not good to
base a financial encryption scheme on a problem whose
difficulty is confined to a black hole---a robber is after
all satisfied to rob the bank even only $90\%$ of the time,
or even only $1\%$ of the time. Alexei Miasnikov inquired
whether the halting problem itself admits a black hole, and
it turned out that for one of the standard models of
computability, the answer is yes:
Theorem.([1]) For the Turing machine
model with one-way infinite tapes, there is a set of Turing
machine programs $A$ such that


*

*$A$ has asymptotic density $1$, so almost every program
is in $A$.

*$A$ is polynomial time decidable.

*The halting problem is polynomial time decidable for
programs in $A$.


Thus, for this model of computation, the halting problem is
decidable with probability $1$. The reason has to do with
the fact that for the one-way infinite tape Turing machine
model, it turns out that almost every Turing machine
program, like Polya's drunken man, falls off the tape
before repeating a state. And this is something that can be
detected in linear time. It follows that with asymptotic
probability one, a Turing machine program computes a finite
set. 
[1] J. D. Hamkins, A. Miasnikov, The halting problem is
decidable on a set of asymptotic probability
one, Notre Dame Journal
of Formal Logic, Notre Dame J. Formal Logic 47 (2006),
515–524.
