20
$\begingroup$

Consider decision problems stated in some “reasonable” formal language. Let's say formulae in higher-order Peano arithmetic with one free variable as a frame of reference, but I'm equally interested in other models of computation: Diophantine equations, word problems from rewriting rules using Turing machines, etc. An answer expressed in any classical formalization would be fine, though if you know how much the choice of formalization influences the answer, that would also be interesting.

Given the length $N$ of the statement of a decision problem, we can define the number $D(N)$ of decidable statements of length $N$ and the number $U(N)$ of undecidable statements of length $N$.

What is known about the relative growth of $U(N)$ and $D(N)$? In other words, if I take a well-formed decision problem at random, what is the probability of its being decidable for a given statement length?

Inspired by this question which asks whether “most problems and algorithms [are] decidable”. Well, if you don't filter by interest, are they?

$\endgroup$
  • 4
    $\begingroup$ So, you are essentially asking how big a fraction of describable languages are decidable? If we consider all languages, then this fraction is obviously 0 as there are uncountably many languages. $\endgroup$ – Alex ten Brink Mar 9 '12 at 12:58
  • $\begingroup$ @AlextenBrink More precisely, I'm asking how big a fraction of language descriptions are decidable languages. It might make a difference the number of equivalent descriptions of a language is correllated with its decidability. P.S. Feel free to edit my question if you don't think it's expressed clearly. $\endgroup$ – Gilles 'SO- stop being evil' Mar 9 '12 at 13:04
  • 5
    $\begingroup$ This seems somehow related to (and more complicated that) the Chaitin's constant but I am yet to find a way to say $D(N)$ is not computable. en.wikipedia.org/wiki/Chaitin's_constant $\endgroup$ – jmad Mar 9 '12 at 16:19
  • 1
    $\begingroup$ a related question: what is the probability that a random n-state Turing machine is decidable? $\endgroup$ – Kaveh Mar 10 '12 at 15:15
  • 2
    $\begingroup$ Here is a similar question on Mathematics: Density of halting Turing machines $\endgroup$ – Kaveh Jul 24 '12 at 22:46
2
$\begingroup$

See Chaitin's research into Omega that shows, as I understand it, that undecidable problems are [paraphrasing] quite numerous, rampant or dense among statements chosen at random. However you have to be careful how you define $U(N)$ and $D(N)$ because they may be actually uncomputable functions. There is also some connections to busy beaver research. Identifying decidable and undecidable statements seems quite analogous to proving that busy beavers halt or do not halt. (e.g. some of all statements are in the form, “busy beaver [x] halts”).

$\endgroup$
  • 1
    $\begingroup$ Both functions are, of course uncomputable in general. However it is not excluded to find explicit bounds on their asymptotic ratio, just as one may find bounds on the number of uncompressible strings of size n. $\endgroup$ – cody Jul 24 '12 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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