6
$\begingroup$

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:

  1. The size of the randomly chosen Program (P) is 'at most' (Pk) bits.
  2. 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.

$\endgroup$

2 Answers 2

11
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thanks a lot for your reply. But I have few doubts/issues regarding the explanation(paper) and it would be great if you could clarify. $\endgroup$
    – user13550
    Mar 10, 2011 at 19:08
  • $\begingroup$ "Lemma 1.2 The collection of programs having no transition reaching the halt state has asymptotic probability 1/e2, which is about 13.5%." Q1. Is the model proposed in the proof a Universal Turing Machine i.e. we consider all the programs that are possible (with both repeating and non-repeating states) and all possible inputs ? Q2. A randomly chosen program might have a transition to the halt state, but as in original Query we have a random <Program, Input> Pair. But the current input might not lead to a halt state. Thus, input also effects the probability.? $\endgroup$
    – user13550
    Mar 10, 2011 at 19:09
  • $\begingroup$ "Proof of Main Theorem: We now prove the Main Theorem. Let B be the set of programs that on input 0 either halt before repeating a state or fall off the tape before repeating a state." Q3. This method will not work assuming we have a Two way infinite tape Universal Turing Machine. Thus, by definition of halting problem one should be able to comment on all UTM models. Is there any general method using which we can comment on the halting Probability of a Random <Program, Input> Pair ? $\endgroup$
    – user13550
    Mar 10, 2011 at 19:11
  • $\begingroup$ Q1. Yes, the model is universal; it is one of the completely standard models. Q2. The theorem in the paper is only for fixed input, but works with arbitrary input (even infinite input). For (program,input) pairs, the theorem is not as nice, and the full question is open. $\endgroup$ Mar 10, 2011 at 20:43
  • 1
    $\begingroup$ Q3. In the two-way infinite tape model, the current best theorem is not much better than the 13.5% from the no-transitions-to-halt-state argument. However, in the model where any state can be decreed halting, then you get the full theorem, because it is extremely likely to halt quickly, as you are likely to encounter a halting state quickly. So that model can handle the (program,input) situation. $\endgroup$ Mar 10, 2011 at 20:44
2
$\begingroup$

"

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.

$\endgroup$
1
  • $\begingroup$ I am confused with your thank to Prof. Scott Aaronson. Is this his work? $\endgroup$ Jul 20, 2017 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.