Halting program density?

We know the density of primes tends towards 1/log(n) as n get larger. Do we know anything about the density of programs which halt? For example, take your favorite universal turing machine. Generate all programs of size 1. Record the percentage of programs that halt in less than 1 millisecond (or 10,000 head movements, or some other metric). Run the remaining programs for 10 milliseconds each, record the percentage which halt. Continue for 100, 1000, etc. milliseconds. Then repeat the procedure for all programs of length 2,3,4..N. Do we know anything about the surface just described? It surely must be monotonically increasing. Can we say anything more? Can we describe any aspect of it with numbers? This seems like it might be an easier task to undertake, compared to the corresponding question of "What's the density of provable truths in arithmetic?" Thoughts?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

This is pretty far out of my

This is pretty far out of my league, but maybe this is related to Chaitin's halting probability? Here's an article, but I've only glanced at it. There's much more development in his book The Limits of Mathematics.

(And maybe this is actually totally unrelated...)

Very much related.

Thanks for the interesting link. Yes, the halting probability Ω he talks about is pretty much exactly what I was looking for. And he seems to be making a pretty strong statement about it; saying that the ratio of halting to non-halting programs is constant (unlike the case for prime numbers where the probability of choosing a prime number decreases as you go out farther). Well, at least he is claiming this for a subset of programs (the self-delimiting ones, I'll have to look into this more). So my next questions would be, "Has anyone actually calculated a specific Ω for a particular system?", and "What is the highest Ω could be for a universal machine?"

From Omega to Mu

Greg Buchholz: So my next questions would be, "Has anyone actually calculated a specific Ω for a particular system?", and "What is the highest Ω could be for a universal machine?"

Well, Ω can't be computed, right? Anyway, that's precisely the subject matter of Exploring Randomness. See especially A more general framework---Special-purpose computers C, algorithmic probability P, and the halting probability Ω.

I'm not sure I understand what "What's the highest Ω could be for a universal machine?" means. If I understand Algorithmic Information Theory correctly, the Ω for any given machine is essentially random, so there's no way to answer the question short of implementing the machine and computing bits of Ω until you're happy. But if you look at "Exploring Randomness," you'll find a universal machine in Chaitin's dialect of Lisp and you can calculate some arbitrary number of bits of Ω for the language of that universal machine. Is there an isomorphism from Ω for Chaitin's universal machine to Ω for any other universal machine? If I understand Chaitin correctly, the answer is "no," which is why I suspect that your question is not only unanswerable, but is not even well-formed.

Another try

Well, Ω can't be computed, right?

<snip>

...Ω for any given machine is essentially random, so there's no way to answer the question short of implementing the machine and computing bits of Ω until you're happy.

I'll admit to being new to this theoretical stuff, but the two quotes from above (emphasis added) seem contradictory to me.
I'm not sure I understand what "What's the highest Ω could be for a universal machine?" means.
Take your favorite representation of a UTM. Calculate a few bits of Ω for this machine. You get a number like Ω=0.7443... or something. So there's about a 74% chance that a program picked at random will halt. Now take another different representation of a UTM. Calculate Ω for this new machine. You might get a higher value for Ω say 0.8165... Some machine out there might have the highest value possible (and we know it can't have both of Ω=1.0 and still be universal). Thinking about it a little more, maybe the more interesting case is the one with the lowest value of Ω. You could maybe approach 1.0 by adding redundencies (like differing symbols which end up computing the same thing) and No-Ops. The machine with the lowest value for Ω would be the leanest, most compact universal machine possible, right? It can still compute everything that is possible to compute, but I suppose a low value of Ω implies it would be nearly impossible to program. Or writing programs for it would take just as much work as computing the answer itself. Hmm. More to ponder.

Not Contradictory

Me: Well, Ω can't be computed, right?

...Ω for any given machine is essentially random, so there's no way to answer the question short of implementing the machine and computing bits of Ω until you're happy.

The apparent contradiction is resolved by making two observations:

  1. Ω is a family of numbers that has to be instantiated for a particular machine, so of course talking about computing Ω without talking about what machine it's been "instantiated with," if you will, is meaningless. But this is a pretty vaccuous observation.
  2. "Computing bits of Ω until you're happy" should be taken literally. As Chaitin writes, not only can you not compute all of Ω, you can't even determine how many of the "last bits" are wrong when you've stopped, or how many more bits you'd have to compute to get "close enough." "Computing N bits of Ω" is tantamount to tossing a fair coin N times!

Greg: Or writing programs for it would take just as much work as computing the answer itself. Hmm. More to ponder.

That's fundamentally where you wind up with Ω: strong irreducability, programs for computing things that are (must be!) as long as the thing they compute... I'm handwaving now, but you'd be better served by reading "Exploring Randomness" than by me feebly trying to explain further with any acceptable level of rigor.

Unfortunately...

You could maybe approach 1.0 by adding redundencies (like differing symbols which end up computing the same thing) and No-Ops. The machine with the lowest value for Ω would be the leanest, most compact universal machine possible, right?

You need to think a little harder about what you wrote. You could apply the exact same technique to raise Ω to lower it. Simply add infinite looping constructs to the language.

Of course, since programmers don't produce programs by flipping coins, I'm not really sure how valuable such a metric would be.

Genetic Programming

There are various automatic-program-generation techniques including genetic program which do in fact "flip coins" to generate programs. More or less.

Short question

Well, Ω can't be computed, right?

The general disclaimer: I have little knowledge of this field. ;-)

Uhm, your thread popped the up the following questions. Why? I mean: did he prove that it is impossible to analytically derive a specific Ω, in a mathematical sense, from the description of a machine? Is it an irrational number? Does he state anything about the Kolmogorov complexity of the program which computes Ω?

Hmmm...

Isomorphism

marco: I mean: did he prove that it is impossible to analytically derive a specific Ω, in a mathematical sense, from the description of a machine?

Yes. After all, ΩC is just the probability that a randomly-chosen program for machine C will terminate. The definition alone should make clear that the number can't be computed; the trick is to prove it.

marco: Is it an irrational number?

By definition, I would think, but this is admittedly a guess.

Update: Leave it to MathWorld: "ΩU is known to be a transcendental number."

marco: Does he state anything about the Kolmogorov complexity of the program which computes Ω?

Well, "The algorithmic information or Kolmogorov complexity of a bitstring x is the length of the shortest program that computes x and halts," and one of Ω's properties is that the program to generate it can't be any shorter than itself. So we can say that Ω has maximal Kolmogorov complexity.

Update: I see that I answered the wrong question, discussing the Kolmogorov complexity of Ω, which would trivially have to be maximal, vs. the Kolmogorov complexity of a program to compute N bits of Ω. I will have to return to this later.

Part I of "Exploring Randomness" goes into great detail: "Definition of the complexity H(x) of an S-expression x". This is in terms of a universal Turing machine defined in Chaitin's own dialect of Lisp that he developed to make these investigations easier (it has an M-expression syntax, time-limited evaluation, and explicit support for reading bit-strings). He then defines relative complexity and proves his results. You can find the Lisp code from "Exploring Randomness" here, and the Java, C, and Mathematica versions of his Lisp interpreter here.

There's also some interesting stuff here:

What if we allow for nonhalting computations on nonstandard Turing machines? It turns out that some things then become much more compactly describable. This leads to generalizations of the concept of Kolmogorov complexity, and has consequences for Solomonoff's theory of algorithmic probability and universal prediction. It also leads to "Super Omegas" that are computable in the limit - generalizations of Chaitin's halting probability Omega of a Turing machine with random input.

Good show

Thanks for the answers. Somehow, I find it an annoying definition. Then again, I guess I should give it some more thought first.

For us empiricists

I'll definitely read the book, but for us empirical guys, does anyone know if there is a machine for which at least a single bit of omega has been computed? If there has been, was Ω>0.5 or less than 0.5?

For One Specific Universal Machine...

Greg Buchholz: I'll definitely read the book, but for us empirical guys, does anyone know if there is a machine for which at least a single bit of omega has been computed? If there has been, was Ω>0.5 or less than 0.5?

From AT&T's On-Line Encyclopedia of Integer Sequences, we find a few digits of Ω for some unspecified universal machine: 0.00787499699...

That is, for that universal machine, slightly less than eight out of every 1,000 randomly-chosen programs will terminate. IIRC, one of Chaitin's results is that for any universal machine, most programs won't terminate, i.e. "most things aren't computable."

While we are on such problems

While we are on such problems, I've ever wondered (and searched but without luck) whether there was any results on the relation between, for a given problem, the solutions distribution and the minimal complexity of programs which solve this problem.

Yeah

Well, solve the problem and please become very rich ;-). I still ponder about it, when time permits.

Elegant programs

Mr. Chaitin also has some insight into this question. From Elegant LISP Programs...

Call a program ``elegant'' if no smaller program has the same output. I.e., a LISP S-expression is defined to be elegant if no smaller S-expression has the same value.

and

So we've gotten an upper bound on the size of provably elegant LISP expressions. The upper bound is this: A formal axiomatic system whose LISP complexity is N cannot prove that a LISP expression is elegant if the expression's size is greater than N + 410. So at most finitely many LISP expressions can be shown to be elegant.