9
$\begingroup$

This is a sort of Chaitin/Omega constant type question, and so I do not expect this probability to be computable to arbitrary precision. However, it is also a very practical thing to know from the perspective of inductive learning. The motivation to ask this question comes from reading some of Solomonoff's papers on algorithmic probability and resource bounded probability.

In Solomonoff's algorithmic probability, one studies induction / machine learning under the assumption that all observed data is the output of a universal Turing machine with random input. With this prior, expectation maximization via Bayesian methods leads to the natural notion that the best model for a particular observed sequence of data is the one generated by the shortest program (aka minimum description length / Kolmogorov complexity).

One cute thing about this prior is that it beats the so-called "no free lunch theorems" as best as possible. Because Kolmogorov complexity is unique up to an additive constant across Turing machines, as long as the underlying sequence is non-uniformly random it can at least theoretically be learned given a finite number of samples.

The bad thing of course is that Kolmogorov complexity is uncomputable, so this is really more of a theoretical curiosity than an actual tool for machine learning. To get around this, Solomonoff proposed the notion of resource bounded probability, where the resources for the Turing machine are ultimately limited (ie bounded compute time/space). In the case of a space bound, this limitation ultimately transforms the Turing machines into DFAs, which leads to my question:

Given the algorithmic prior (ie observed data is generated by some universal Turing machine fed uniform random inputs), what is the probability that the data observed is the output of a DFA?

Of course if it is a DFA, life is really great since there are a bunch of tricks out there for estimating such a DFA. Also it might be interesting to maybe look at other classes of automata as means to get other variants of resource limited types of results.

$\endgroup$
3
  • 1
    $\begingroup$ Could you make the question more precise? Since any finite observation data is of course the language accepted by a DFA, I'm confused about what you are asking. $\endgroup$ Aug 18, 2010 at 0:09
  • $\begingroup$ Do you know if the probability is non-zero? $\endgroup$ Aug 18, 2010 at 4:21
  • $\begingroup$ @Joel: I suppose we are not looking at finite observation data, but rather observing what has transpired at time $\omega$ (infinity). @Robin: It should be non-zero because there is at least one DFA. $\endgroup$ Aug 18, 2010 at 19:16

2 Answers 2

6
$\begingroup$

The set of possible answers to this question is a countable dense subset of (0,1), because it depends on your choice of universal Turing machine.

$\endgroup$
3
  • $\begingroup$ Can you expand on that? Kolmogorov complexity also depends on the choice of UTM, but in an inessential way. Couldn't it be the case here too? $\endgroup$ Aug 18, 2010 at 11:49
  • 1
    $\begingroup$ That sounds about right. In fact, now that I think about it is sort of obvious that this should be the case since you can always construct a universal Turing machine such that the probability it is a DFA is within any interval [p0, p1]. (Just make prefix codes on the space of all input strings.) $\endgroup$
    – Mikola
    Aug 18, 2010 at 14:55
  • $\begingroup$ @Jacques: one could say that the size of a number in (0,1) is inessential, whereas asymptotic properties of the sequence of binary digits in the number are essential. Chaitin's Omega can also be anywhere in (0,1), but it is always a Martin-Löf random number. $\endgroup$ Aug 18, 2010 at 19:14
16
$\begingroup$

Let me focus on the question of your title, and mention that there is another quite robust way to understand what it means to say that a random Turing machine has such-and-such property.

Specifically, we use the concept of asymptotic density as the size of the program increases. 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$.

One can interpret your title question this way as inquiring: what is the asymptotic density of the set of Turing machine programs that decide sets that are equivalent to a DFA?

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\%$. Of course, all such programs decide the empty language, which is also decided by a DFA, so this is a lower bound on the title question.

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.(Hamkins+Miasnikov) 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. Since all finite sets are DFA computable, we conclude:

Corollary. For the standard one-way infinite tape model of Turing machines, with asymptotic probability one, a random Turing machine computes a set that is DFA decidable.

See 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.

See also this MO answer, which mentions similar ideas.

$\endgroup$
2
  • $\begingroup$ Wow! Great answer! Thank you for taking the time to type all of this out. I am curious though, does the asymptotic density only make sense with respect to some fixed model for computation? For example if you pick a different encoding scheme (such as lambda expressions, C programs, etc.) would you still compute the same asymptotic probabilities? Intuitively, I would expect that this is not the case since you could always create some silly prefix which would reweight probabilities. $\endgroup$
    – Mikola
    Aug 24, 2010 at 14:40
  • 2
    $\begingroup$ Thanks, I'm glad that you appreciate the answer. Unfortunately, these measures are sensitive to the computational model. To see this issue plainly, consider how the notion of a random C++ program changes, depending on whether you allow ill-formed programs with syntax errors. If you allow them, then almost every program is junk, since there are far more junk strings than well-formed programs. Similar issues surround almost every particular notion of computation. $\endgroup$ Aug 24, 2010 at 15:12

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.