Lambda the Ultimate

...are you sure that this exact concept is something that Chaitin cares about? My understanding is that Chaitin is more interested in the complexity of computation without regard to any specific language (at least that's how he defines omega...its value depends on the choice of language, but the choice itself is uninteresting). My point was to measure not complexity in any absolute sense, but to compare the efficiency with which different languages can express solutions with respect to each other.

...you're emphatically NOT interested in random Turing machines.

The programs people actually write are very, very structured, and belong to a tiny subset of the set of possible programs -- almost all of them run in time bounded by some very low-degree polynomial, and operate in very regular over the structure of the data. That's the reason that fold, map and related recursion operators are so useful -- they encompass almost all uses of recursion that occur in real programs. An "expressive" programming language is one that's optimized for the sorts of programs that people are apt to actually write.

...is that there is no formal way to enumerate the types of programs that people actually write. If there were, I would be more than happy to use that in place of TMs in my definition. But I invite anyone to offer such an ordering.

Why not use some simple but high-level language? Like Scheme? (or Forth, for other audience :-) )

...and Kolmogorov and Solomonoff. We can't have Chaitin take all the credit here.

My original post was a bit hasty because I just wanted to stimulate discussion, and it looks like I succeeded at least to a small degree. However, I realize now that there is no need to include TMs as a middleman (or middleperson, depending on how PC you are).

Of course, the problem was not to look at the problem space, but at the program spaces. So instead of enumerating over TMs, let us enumerate over programs, and make the measure entirely relative. Thus, let Lr be the reference language, and Lc be the comparison language. Now we define P as the set of programs in Lr that are of length N or less, R as some program in P, and M(R, Lc) as the length of the shortest program in Lc that is equivalent to the given program R. This should eliminate many of those boring TMs that we really don't care about, and at least get to some programs that we can recognize. So now we have E(Lr, Lc, N), which is the expressivity of Lc with respect to Lr for programs in Lr up to length N. Perhaps this is a more palatable metric.

As far as compressing the source, I wanted to avoid penalizing "verbose" languages that just happen to use wordy keywords instead of, say, symbols. That would give unfair advantage to many of the FP langs over langs like Ada and COBOL. Also, I think that compressing the source would not eliminate all the redundancy in inefficient or low-level languages, because it's not true redundancy...it's simply unoptimized complexity, and compression can't really change the complexity measure of the data...or can it?

For instance, if you compared an assembly program to a Haskell program, you would find that most of the assembler mnemonics could be reduced to just a few bits. But even doing so would still result in those bits occurring many many times, because the entire instructions themselves would tend to be unique (due to memory references, manifest constants, etc.). I'm fairly confident that the assembly code would be considerably larger than the Haskell code for any compression scheme that just looks at the data statistically (and doesn't do something tricky like encode knowledge of assembler or Haskell).

I realize that in real life, compressed source tends to be much larger than the resulting executables, but that just says that machine code is the most expressive code in existence (which is another good argument for expressivity != usability). Also, real programs tend to contain things like comments and abstractions that make the code more maintainable, but not necessarily more expressive.

Was not to claim that expressivity == usability. That would be reaching way too far. It was merely to argue that expressivity itself is not a completely subjective measure. I would go farther and argue that usability isn't completely subjective either, but I'm afraid that argument would require an intricate knowledge of human psychology that isn't generally available yet.

Expressivity is not subjective, but at the same time I have to agree with the previous poster. It's quite useless to attempt to measure such a thing. And the only reason for measurement would be comparison.

You simply can't compare languages in terms of expressivity, no matter how close the languages are to each other or how distant they are. Let me throw this example out there. Scheme has call/cc and dynamic-wind. Common Lisp has a condition system and unwind-protect. While similar in many respects, they are subtly different. So subtle that at certain times it looks as if they "say the same thing" (express), yet they clearly say, or express different things. And it's not possible to claim that either language could express *both* concepts, either. They are diametrically opposed.

One set of expressions says "we give you a guarantee." The other says "we place few restrictions on you." To cross the chasm you need to alter the expressivity. This does not mean one is less expressive than the other. It just means you can't have your cake and eat it too.

Now you can get both at once, but then you need a mediator. Something that says "we grant you permission." Then you're entering the realm of LanguagesAreOperatingSystems and turing tar pits.

I think a more beneficial discussion might be *how* expressivity relates to meaning and problem solving (and not the degree thereof) and ways to match problems to a suitable model of expression. Such as McCarthy's AMB, logic and constraint-based models are better suited for certain types of problems than a strict imperative/functional/OO model.

The only thing I see measuring expressivity will tell you is if you are using the wrong model for the problem at hand. And measuring this is equally flawed. You can have the most concise matrix multiplication routine in Scheme, yet it won't capture the efficiency requirement that your application might demand. Yes, it solves the problem in fewer words. But what if the requirements demand more detail? There might only be one language that can capture this requirement, such as assembly. Then it won't really matter how "expressive" Scheme is... it just isn't suitable. The language can't solve the fully defined problem.

And I think what you will find is that as you provide more details to the problem at hand, most languages simply disappear in any measurement because they can't express enough of the detail. And that's the real key, isn't it? Figuring out all the requirements of any non-trivial problem.

That seems to nail this thread on the head. However, it seems to be the convention here to use HTML to make links live, like this. ;>

Not that repeating good stuff is a bad thing, just curious, how many links are missed this way.

Thought I followed that whole thread, and didn't see a single mention of that paper. Maybe I missed something.

There's a huge sub-thread on it. When I saw this come up as a forum topic, I thought it was an attempt to factor the whole the expressivity thing out.

That was the point. But I never saw that paper mentioned in that sub-thread.