The completeness proof for the distributional halting problem (version 1),
was first given
by Gurevich [Gur91]. An easier and more comprehensible proof
was given in [WB95] (see also [Wan96]), which will
be presented here.
Denote by 
the set of all positive instances of the
halting problem and
the probability distribution on (positive and negative)
instances 
. Recall that the size of this instance
is 
.
Proof.
be an arbitrary problem in DistNP.
Then there is a nondeterministic
Turing machine 
which accepts 
in polynomial time.
By the Distribution Controlling Lemma, there is a total, one-one,
p-time computable and p-time
invertible function 
such that 
.
Define a Turing machine 
as follows. On input 
,
if 
is defined, then
simulates on 
and rejects otherwise.
Clearly for all 
,
accepts iff accepts 
.
It is easy to see that on input 
is bounded in time
for some polynomial 
.
Let 
be an index such that 
. Let
.
Then 
is one-one and p-time computable.
By construction, 
iff 
.
Moreover, 
for some polynomial 
,
which dominates 
. It follows from Lemma 2.1
that 
.
