How can we compare expressive power between two Turing-complete languages?

Is this possible?

Is there an accepted (and unambiguous) notion of "expressive power" that could differ between two different Turing-complete languages?

It seems like, for example, Python is intuitively much more "expressive" (in some sense) than an assembly language since Python's high-level constructs (like classes, functions and even for loops) often make it much easier to organize and think about code compared with assembly languages.

On the other hand, any program you can write in Python you can also write in an assembly language since both languages are Turing-complete (ignoring library availability, etc).

But do you really want to implement complex algorithms in FRACTRAN or as a Magic: the Gathering deck? Why not?

Is there a way to give a real, unambiguous definition to this intuitive notion of "expressiveness?"

• Too vague for an answer, but: a kind of reverse-Kolmogorov complexity would make sense. When you have a program that solves a problem, you can measure its time complexity, space complexity, but also its length (in bytes), its readability/maintainability, etc. Use all these measures to attribute a score to each program. Then if you have a list of standard problems in order of difficulty, you could "grade" a language by the minimum scores of programs that solves these problems.
– Stef
Commented Jul 5, 2023 at 7:43
• For instance, compare a Turing-machine's tape with C's allocation of memory. In C you can use pointers to quickly access any memory you've allocated. On a Turing-machine, you need to move the data head one cell at a time to access memory. Although both are Turing-complete, solving a problem that requires large amounts of memory is going to be slower with a Turing-machine, because you need time to move the data head back and forth - you wouldn't need that time if you had pointers like in C. So, "pointers" are a feature that noticeably reduces the time-complexity of programs.
– Stef
Commented Jul 5, 2023 at 7:52
• Good idea but you have to be very careful of your costs. Do you include library functions and system calls? What about machine level instructions like microcode? You might argue the measurement should be relative. So you do include those if you are comparing with a turing machine but you might not if comparing two languages that both assume an x86 architecture. Commented Jul 5, 2023 at 8:56
• stackoverflow.com/q/2427496/781723
– D.W.
Commented Jul 5, 2023 at 16:49

Surprisingly yes, this is possible!

This is actually pretty important for people that work on optimizing compilers. If I add this new feature, will it break any existing optimization pass? I will show why this is a concern later in the answer.

And this is good since all of us are interested in programming languages. Surely we should have at least one clear-cut way to distinguish between them, beyond the names of keywords, etc! Most people would rather write a large system in [insert your favorite language here] than, say, Befunge or INTERCAL. But those languages are Turing-complete.

So, what's going on here?

Not only that, the concept we need here has significance in formal semantics beyond this question. I'll briefly mention this at the end of the answer.

Can you ever distinguish between 2 * 3 and 3 + 3 in a programming language? Are you sure? Are there any "reasonable" languages in which you can distinguish between these? What, exactly, would it mean to be able to distinguish between them and how can we give a definition for "this language distinguishes between these things?" Read on to find out more!

The concept we need is called "observational equivalence."

• First I'll give an intuitive description of how you could understand the statement "feature X adds expressive power to language L".
• Next, I'll need to talk about programs that have a hole in them. These are called "one-hole contexts". Sometimes this is abbreviated to just "context."
• Then I'll use one-hole contexts to define "observational equivalence." This is one way to talk about certain programs being "equivalent."
• Finally, we will see that we can say adding feature X to language L makes the language more expressive if, by adding feature X, we end up with fewer observational equivalences in the resulting language L+X. That might sound backward. I'll get to this, though.

The key idea is this: Consider taking a Turing-complete language L and adding feature X. Now think about how we could translate code written in L+X back into into L. If feature X makes the language "more expressive," then this transformation will require you to apply a large-scale, "global" transformation. On the other hand, if language L and L+X are "equally expressive," then L+X can be transformed into L using only a "local" transformation.

Inspiration

I will state upfront that this answer (and the way I framed the original question) is inspired by Shriram Krishnamurthi's excellent and approachable 2019 talk about Matthias Felleisen's paper "On the Expressive Power of Programming Languages." Anyone who is interested in this question should absolutely watch it. The corresponding paper is here.

I actually think that talk would be interesting to everyone here, in fact. There are many questions that have variations on "... what if I add feature X to a language ..." and this talk gives a way to understand one aspect of that kind of question!

Incidentally, I will be giving spoilers for the talk in this answer!

Intuition

Let's say we start with a language that only has functions, conditionals, integer literals, addition, subtraction, and multiplication. This is Turing-complete if we allow recursion. Let's also say that functions are first-class. This won't come up right now, though.

If we add, say, a unary negation operator to our language, this does not intuitively "increase expressive power." However, if we add exceptions to the language, well, that does seem to intuitively "increase expressive power."

Why? Well, for the first feature, whenever we see a unary negation -x we can just translate it, right then and there, into 0 - x. However, for the second feature, when we see an exception being thrown or a try-catch block, then we actually have to do a large scale transformation of the program.

I chose exceptions since they are of greater interest, but let's consider a simpler example of a feature that "adds expressiveness." How about a keyword halt that immediately terminates the program? You certainly cannot implement this as a local transformation to our language! You actually have to apply a transformation that starts at the beginning of the program!

With the negation feature, we only had to transform the exact part of the code where the unary negation is used. For the halt feature, we had to transform the code far beyond where that keyword is used.

This distinction between "feature only requiring local transformation" and "feature requiring global transformation" is what we want to formalize.

We can get closer to a formal statement by saying: a feature does not "add expressive power" if we can implement it as a macro that turns it into something in the original language. Even if the language doesn't have macros, you could imagine using some kind of preprocessor to implement a local transformation as a kind of macro.

This is not quite a formal description yet, but we're getting there! For one thing, how do we prove that a macro cannot exist for some feature? To do this, we still need a formal description of the problem.

What's tricky about equality of programs?

First, we need a way to compare programs for equality.

You might wonder: why not just use the equality built in to the language? Well, there are a few reasons:

• The equality operation might not cover everything. For example, it's actually impossible to compare arbitrary functions for equality in a Turing-complete programming language (in a way that is always correct and always halts).
• The language might not even have an equality operation, even though it's Turing-complete. This is the case for many esoteric languages, like FRACTRAN.

So we really want something that's somehow "more fundamental" than that and more broadly applicable. We actually do want something that's inside the language that can distinguish between two things, though. But how do we do this?

What it really boils down to is this: given two things in our language x and y, is there any way to write a program in our language that behaves differently if you used x vs if you used y?

A specific question: Is it possible to distinguish between 2 * 3 and 3 + 3? I will return to this particular question in the Expressiveness section.

Formalizing all this is where we get observational equivalence.

But first, we need to talk about what happens when you take a program and cut a hole out of it.

Programs with a hole

Imagine you take a valid program in your language and print it out. Then you physically cut out exactly one subterm and throw it away. What you have left is a "program with a hole in it," or a printout of a "one-hole context" (sometimes just called "a context").

If you take a slip of paper, write a term on it, and tape it into the hole you now have a program again (as long as the result of this process is well-typed). This is the primary thing you can do with a one-hole context: You can obtain a program by combining it with a term that can fill in the hole.

If we call our context C and the new term we're taping into it t then the complete program we obtain when we tape t into C is called C[t].

Note that this definition actually always makes sense no matter what programming language we are looking at! I've made no assumptions about the language.

Our definition of observational equivalence will center around these contexts (that is, programs with exactly one hole in them).

Observational equivalence

One way to define what it means for two programs to be "equivalent" is that every observation you can make about them is the same. There is actually a decent amount of nuance to "what counts as an observation?" but that's outside the scope of this answer.

We will define observational equivalence like this (first attempt):

• Two expressions e1 and e2 are called "observationally equivalent" if, for every context C, we have C[e1] = C[e2]

This is the same as saying, given those two expressions, does the language provide you a way to tell them apart! It's asking "Are the two expressions identical when plugged into any context?"

"Uh, wait a minute..." I hear you say. "But there's still an equals sign! What does that mean? The whole point was to avoid using an existing notion of equality!"

That is very true! We need to improve our definition. We need to be a bit more clever (this new definition is due to James Morris's 1969 PhD thesis):

Two expressions e1 and e2 are called "observationally equivalent" if, for every context C, we have: C[e1] halts if and only if C[e2] halts

This might seem a bit weird. Think about this for a minute. Does this seem, somehow, wrong?

Take a moment to consider this question: "Are we saying that 1 and 2 are 'observationally equivalent'? Both 1 and 2 very straightforwardly terminate!" (I've taken this from this part of Shriram's talk. Spoilers for the talk ahead!)

I am not saying they are observationally equivalent! An example: Can you write a Python program with one hole in it that will halt if the hole is filled with 1 but will loop forever if it is filled with 2 (you could just write <hole> for the hole and fill it in as appropriate)? If so, you've proven that 1 and 2 are observationally distinct in Python! To show that they are distinct, all you have to do is find one context C where C[1] halts but C[2] does not (or visa-versa). If they were the same then every context would behave the same (with regard to halting) regardless of whether you plugged in 1 or 2.

What if we only have a isZero(x) builtin function, but no builtin equality operation? Can we still tell 1 apart from 2? Well, how about the context while (isZero(1 - <hole>)) { }? This is why the definition works well: we need to consider all possible contexts!

Okay, but what if there is actually no way to tell 1 and 2 apart? Then we would actually say that are observationally equivalent! Observational equivalence captures the idea of what it means for two things to be indistinguishable inside a programming language.

Expressiveness

Now how does all of this relate to expressiveness? I'm going to start by way of example. I'll return to the question: Is it possible to distinguish between 2 * 3 and 3 + 3?

My answer: It depends on the features of the language! It certainly is not possible in the language which only has basic arithmetic, functions and recursion. Can you think of a feature we could add where it is possible to distinguish them?

Operator overloading! Say we have operator overloading and the ability to redefine existing function. If we overload * to do something weird, like return the first argument but we don't overload +. We can now distinguish between those two expressions!

By adding that feature, we broke an observational equivalence. The expressions 2 * 3 and 3 + 3 used to be observationally equivalent. Then we added operator overloading and now they are observationally distinct.

Now we need to address how to tell if a feature requires a "local" transformation vs "global" transformation.

The key theorem

If feature X can be implemented for language L as a local transformation to obtain the language L+X, then for any two expressions e1 and e2 that are observationally equivalent in L, it is also the case that they are observationally equivalent in L+X

The theorem is proven in the paper.

This is saying that if feature X only required a local transformation to implement, then it did not "break" any observational equivalences. All of the observational equivalences from L are still true in L+X.

Note that this was not the case for operator overloading. Adding operator overloading did break some observational equivalences. On the other hand, when we added unary negation we did not break any observational equivalences.

Now we can say that when we add expressiveness to a language, we break some observational equivalences.

One practical implication of this is that some optimization passes might be broken when you add a new feature. This is because optimizations assume that certain things are identical. But when you add a new "expressive" feature, you will break some of those equivalences!

Exercise for the reader: I mentioned adding halt to a simple language and I said that this is an expressive new feature for that language. Can you give an example of an observational equivalence that holds in the original language, but not the new language with halt?

Bonus: Connecting a denotational semantics to an operational semantics

Even though this is just a small part of the answer that is only tangentially relevant to my question, this is what motivated me to write the question and this answer. Particularly, to partially clear up some confusion about denotational semantics from the comments of my previous question and answer. This is only one component of that, but it is an important one.

Up until now, we see one useful application of observation equivalence. This allowed me to define it and motivate it. Now we can see, briefly, another application of observational equivalence that is relevant to defining a denotational semantics. It would really be a different answer to a different question to address this in more detail, however, so I will gloss over some things.

There are two very crucial properties you want from your denotation function when you create a denotational semantics. One is called "compositionality" and the other is called "adequacy." "Adequacy" is defined using observational equivalence. Observational equivalence is derived from an operational semantics.

• "Adequacy": If two programs are observationally distinct, then they must have distinct denotations.

Consider what it would be like if our denotation function was not "adequate." We would have two programs that we can observe are different, but they would be mapped to the same mathematical object. That's not very useful way to denote programs!

Books

• This is awesome, but seems to interact weirdly with some specific features. For instance, consider having a quote macro that would take its operand and return it as a string. For a language with that and string comparison, any two different expressions are observationally distinct. Does it make this language the pinnacle of expressiveness? Commented Jul 5, 2023 at 7:53
• a=a*[hole] a=a*2*3 vs a=a*3+3 maybe I misunderstand? Commented Jul 5, 2023 at 10:14
• Trying the exercise: hole = while(True){ f(0) } versus hole = while(True){ f(1) }. And as context: define f(x): if x == 0: halt; [hole] did i understand this correctly? Commented Jul 5, 2023 at 10:52
• @ArrayBolt3 You can observe what I'm talking about in Racket, for example. Consider the two expressions (+ 2 2) and 4. Now, consider this context: (eq? (quote <hole>) 4). If you fill the hole with (+ 2 2) you will get back #f. However, if you fill the hole with 4 then you get back #t. Commented Jul 5, 2023 at 21:14
• Follow on question - langdev.stackexchange.com/questions/2082/… Commented Jul 6, 2023 at 8:54

I don’t believe that’s generally possible. Expressive power depends on what specifically is being expressed.

Your python versus assembly example is obviously more expressive when you write general-purpose scalar code, manipulating strings or XML or JSON, access files or network.

However, for other programs the expressiveness can be opposite because processors are implementing interesting instructions hard to express in Python. For modern AMD64 processors, bit manipulation like popcnt, pext, pdep, vector math like psadbw, pshufb, psignd, dpps, saturated integer stuff like paddusb, checksum and cryptography support like crc32, aesenc, aesdec, sha1rnds4 are easy to express in assembly (and even easier in C++ with intrinsics because the compiler takes care about register allocation and scalar parts of the code), but harder to express in Python.

The observation is not specific to AMD64, other instruction sets also contain instructions hard to express in higher level languages. An example is ARM’s rbit instruction which reverses order of bits in an integer. That single instruction requires rather complicated code to express in higher level languages. Other ARM examples are saturating arithmetic, and bfi.

• There is the most highly upvoted answer on this site, by a high-rep user, that directly contradicts your first sentence @Soonts Commented Jul 6, 2023 at 15:35
• @Starship-OnStrike I think it's reasonable to say that David's answer (while very interesting) doesn't necessarily give us tools to answer questions like "which is more expressive, Python or assembly". It's a neat result, but it doesn't mean this response isn't also useful.
– Kaia
Commented Jul 7, 2023 at 21:25
• It sounds like the main disagreement is with the first sentence of the answer. I see two different readings of that sentence, depending on how you interpret the scope of the word "generally": (1) "There is no technique that will compare any notion of expressiveness between two Turing complete languages" (2) "No technique for measuring expressiveness works for _every_ form of expressiveness". I don't agree with (1), but I do agree with (2). I suspect (2) is intended for this answer, though. Commented Jul 7, 2023 at 23:21

Matthias Felleisen's paper is a little hard to follow. It gives an expansion-based notion of expressive power.

In the concluding paragraph, Felleisen expresses the belief that this is a superior way of exploring expressive power to the approach based on interpretation. I think that is referring to the general idea that a language A is more expressive than B, if the only way to get B to express programs in the same way as A is to write an A interpreter in B and then just run the A programs.

Turing showed us the concept of a Universal Turing Machine, which is programmable. What that means that for any given Turing Machine (input tape plus symbol manipulating rules), the Universal Turing Machine can be programmed to run that Turing Machine by an extended tape: a tape which contains instructions for the Universal Turing Machine, followed by the to-be-simulated/emulated Turing Machine's tape. The UTM concept tells us that (if resources are no object), we can directly run the programs of one language in any other language, by interpreting it.

Thus, Turing equivalence speaks to expressiveness because we know not only that any universal machine can calculate all the same recursive functions as any other, but that an universal machine can interpret a calculation written in any expressive form. If a language A, however, can translate a program in language B into language A, such that no interpretation is involved; B programs thus translated are at no performance disadvantage compared to A programs, and interoperate easily with A programs, that that somehow gives us a more satisfying sense that B has the expressive power of A.

Felleisen's basic idea seems to be this. We would like to compare the expressive power of two languages L0 and L1, using the concept of translation. Firstly, we need some common ground. We assume that there is a common language L, from which L0 and L1 are derived.

Informally, we can identify L as a common virtual machine for L0 and L1. Languages L0 and L1 expose some subset of L. We make a simplifying assumption. Whenever L0 or L1 feature something from L, that feature "looks like" the L feature; it is not weirdly disguised, twisted or damaged in some way.

We allow L0 and L1 to have macros.

Then, we can say that L1 is strictly more expressive than L0 if L1 can use macros to express every L0 program, but the reverse isn't the case. For any construct in L0, an identical or similar macro is defined in the L1 program, if necessary, and then the L0 construct is simply transliterated, but in the reverse direction, there are L1 constructs that aren't in L0, and cannot be provided by L0 macros.

Now, according to Turing, we could have some L1-interpret macro in L0 such that (L1-interpret '(... quoted L1 program ...)). But the quoted L1 program is being (partially or entirely) interpreted and not actually translated into L0 primitives.

We rule out this Turing interpretation trick as not providing a true expressiveness bridge for the follwoing reasons. If L0 can only express L1 programs by interpreting them, then those interpreted L1 programs are not directly using the required L features, which are used by the real L1 implementation.

We can justify that with an example. Suppose that the underlying L has, say, dynamic non-local transfers (for implementing exceptions and such), with unwind protection. Suppose that feature is exposed in L1, but is not found in L0: L0 has no dynamic control transfers, no unwind-protect. Then it will be impossible for L0 to translate and execute an L1 program, other than by L0 providing its own implementation of dynamic non-local control transfers, which are not based on the ones in L. L1 programs execute in L0, but in with a severe limitation: they cannot initiate a dynamic control transfer which jumps out of L0 entirely and terminates in an exit point in a genuine L1 program running directly on the L machine. More importantly, the interpreted L1 programs also cannot catch exceptions emanating from L itself, like from the L I/O library or what have you. L0 has no access to that; it has no way of catching exceptions and forwarding them into the interpreted L1 code. Thus L1 programs themselves lose expressiveness with respect to the L environment if they are interpreted by L0.

The generalization is that if L0 exposes only a subset of the L features than L1 exposes, in a way that some L1 programs cannot be converted to L0 programs while remaining fully-fledged L programs, but L0 programs can so be converted to L1 programs, then L1 has more expressive power.

Expressive power is related in some way to succinctness but not defined by it. If both L0 and L1 have macros, they can both condense code. The above notion of expressiveness strikes at the idea that there are situations in which L0 cannot express some semantics in L1 in spite of having macros for expressing the syntax. You can write the interface part of the macro which matches the syntactic pattern of the L1 construct, and all its conciseness, but have no way to actually write the transformation: the macro's target language doesn't have the constructs for expressing the macro's meaning.

If we have a L0 and L1 which both have all the features of L, but L1 has macros whereas L0 doesn't, then conciseness becomes utterly relevant to expressiveness, because L1 macros can express new kinds of constructs that are not replicable in L0. If we take the fully macro-expanded L1 program, we can express that in L0, because all the constructs it's using are available in L0. Expressing the macro-expanded program is not the same thing as expressing the original program.

• This seems to require that both L0 and L1 share a common subset of feature L which I suppose must be vacuuously true given that both are turing complete. But doesn't the answer actually depend heavily on L? Also how can we be sure this ordering relation is total or partial? If you compare two languages you might find they both have features that can't be expressed in the other. E.g. L0 has exceptions but L1 has continuations. L0!>L1 && L1!>L0 && L0 != L1 Commented Jul 6, 2023 at 22:25
• Third point. I would argue that a macro system makes a language more expressive. So if L1 is L0 but with a macro system an ideal metric should say L1>L0 Commented Jul 6, 2023 at 22:25
• @BruceAdams Turing machines don't have to share any common L. E.g. we can have a tape with a read/write head, versus lambda calculus. Now suppose we are talking about real languages. We can identify multiple L's. They all run on my PC, so L could be x86-64. No wait, both languages are on the JVM, so that's the L. Perhaps L should typically be something like the highest level substrate that the two have in common.
– Kaz
Commented Jul 6, 2023 at 23:11
• In reality, we often deal with differently expressive languages. Say we have some language with macros, but is missing something relative to another language. Neither is strictly more expressive than another, but for some task where that missing something is critical, the language which has that feature is expressive, whereas the other one isn't. Where that missing feature is not relevant, the language with macros is more expressive. Tasks often just require a subset of a language, and so expressiveness can be evaluated over subsets.
– Kaz
Commented Jul 6, 2023 at 23:14
• @BruceAdams Regarding your point, yes, I hoped to convey that that would be true. If L1 is L0 with macros, it is more expressive, because the macro expressions in L1 have no equivalent in L0. In this answer, to express means to present in the same way, expression by expression. If L1 uses a with-open-file macro, but L0 handles all errors and manually cleans up, L0 is not expressing what L1 is expressing.
– Kaz
Commented Jul 7, 2023 at 3:12

A straightforward approach is to write the same program in multiple languages, minify the source code (so that you're counting only “real” code rather than indentation or variable name length), and score “expressiveness” as inversely related to the number of bytes of minified code.

However, this fails to meet your criterion of being “unambiguous”, because it depends on the choice of benchmark program(s). Different languages have different standard libraries and different domain-specific features, making some languages better specialized for specific tasks than others. For example, if your assignment is to write a simple cat-style program that copies data from stdin to stdout, it's hard to beat the 5-character program Brainfuck program ,[.,]. But the language is unwieldy for pretty much anything else.

• Two languages can both be given "minifying power" via structural macros. Yet it may be that programs in one still cannot be expressed in the other, no matter how you try to write the macros. E.g. Common Lisp doesn't have continuations. You can't get them via macros. You can create a macro-based sublanguage in which there are continuations, but those continuations are restricted to staying within that language. You've not introduced continuations into the underlying Common Lisp; you cannot capture the computing future of arbitrary Lisp code as a continuation.
– Kaz
Commented Jul 6, 2023 at 17:57
• If I were to take Python and add in INTERCAL’s requirement that some percentage of statements begin with PLEASE, the resultant language would score less favorably by this metric, but would not be any less expressive. Similarly, deriving a language that substitutes APL-style special characters for keywords from Python would score more favorably by this metric, even though it is no more expressive than Python. At minimum, you need to be looking at token counts, not character counts. Commented Jul 6, 2023 at 21:04

Expressive power is absolutely not about the lines of code required to achieve the needed functionality. If we would count so, the most expressive language is Bash. Feel the power:

firefox


A complex browser, with rendering engine, security, scripting and lots of other stuff is implemented with just a single line of code. One may say, best language ever. No firefox on the system?

firefox || sudo apt-get install -y firefox && firefox


We are still able to provide the firefox anyway with just one line of code, this will work nice also if it is already present. But if there is no existing program available, building brand new functionality with Bash is less fun, even if possible.

Now feel the Python expressive power for the following real world example (source):

numpy.where(arr<0,arr,0).sum(0)


Assuming you are not an expert of the large numpy API yet, it may actually take the comparable time to understand the same in Assembler (source):

  xor  edx, edx
mov  esi, [arr]
mov  ecx, [arr_rows]
imul ecx, [arr_cols]
more:
mov  eax, [esi]
test eax, eax         ; TEST is efficient to inspect the sign
jns  skip
add  edx, eax         ; Only adding negative values
skip:
dec  ecx
jnz  more


and while the old C++ version may not look very cool, I still suspect that for many it would take less time to understand it than that numpy twist:

   int sum = 0;
for (int v: arr) {
if (v > 0) sum += v;
}


Bash (source) ?

sum=0
for file in $* do for number in grep -wo "[0-9]*"$file
do
if [[ $number -gt 0 ]]; then sum=$(($sum+$number))
fi
done
done
echo "Sum: $sum"  Not that easy, even if we tried to play on Bash stronger side a little bit by accessing the existing program, grep. Similar problems as with Python: to understand this code, you need to know that the grep is and which switches does it take.$* is also not for mundane ones, further illustrating the fact that "two characters only" does not necessary mean a lot of readability. Something more along all_args would probably be understandable without googling this answer.

Python looks somewhat similar to Bash (and some administrators actually use it that way). When there is a complex functionality available, it is great in accessing it. Especially when that complex functionality does not actually take or return any complex data structures to deal with, just does its magic when called by name. But when implementing some complex algorithm from the mathematical article, Python may still not be the best tool for the purpose.

I am not sure what the "expressive power" means exactly, but the language I would pick for implementing or developing some complex algorithm should:

• Make it very easy to implement the huge number of the known software design patterns I expect to use.
• Provide reasonable amount of context. A structure with named and typed fields provides more context than a map that could contain almost anything, and may take long time to figure out what exactly. Python is proud of demanding very little context, but I really had big problems in understanding complex undocumented structures as returned by some third party libraries. In C++, this would at least not compile.
• Make it easy to split a complex step into multiple simpler steps.
• Due reason above, it must run loops at usable speed, because a single iteration of the loop is often much easier to understand than the complete action on the whole array, expressed in the terms of matrix algebra or the like.

From the other side, a language that is explicitly designed for the group of tasks where our current task also belongs may be very expressive and efficient there, easy to write and read. I would probably put the winner on SQL here, at least against Python, even it it is not Turing complete:

select sum(x) from array where x > 0


I am convinced that likely any non programming teenager would understand.

• “One may say, best language ever. But it may be something wrong with this view.” I share that view, and I don’t think there’s anything wrong with it. For this particular problem, and for many other programs which only need to run other programs (no matter how complicated), and pipe these input/output/error streams forwarding them into yet another programs, Bash is incredibly expressive. People are using Bash and similar languages all the time, precisely because these are probably the most expressive languages for that particular class of problems. Commented Jul 6, 2023 at 17:15

In many cases, it's useful for a programmer to be able to specify "don't care" aspects of program behavior, and allow an implementation to choose in Unspecified fashion from among them. While all Turing Complete languages may be equally capable of handling all situations where, for any particular input, a program would be required to produce some particular exact ouptut, there can be substantial differences in their ability to specify "don't care" aspects. From a purely theoretical standpoint, there's never any need for a programmer to characterize any aspects of behavior as "don't care", but from a practical standpoint it can nonetheless be useful.

Consider, for example, the design of a circuit which accepts 32 inputs and produces one output, subject to the each of the following set of requirements:

Set #1:

1. If more than half of the inputs are high, the output must be high.
2. If less than two inputs are low, the output must be low.
3. In all other cases, the output may be arbitrarily high or low.

Set #2:

1. If more than half of the inputs are high, the output must be high.
2. In all other cases, the output must be low.

Any design that satisfies the first specification would also satisfy the second, but a minimal circuit which upholds the first specification could be realized much more cheaply than one which must satisfy the second. If application requirements would be satisfied by either circuit, the first circuit would be a cheaper way of satisfying such requirements than the second would be.

The second requirement could be satisfied by using eight circuits which each accept four inputs, and have four outputs indicating whether at least one, at least two, at least three, or at least four inputs are high. Those could then be paired to yield four sets of outputs indicating whether at least one, etc. up to at least eight inputs from each group of 8 are high, and those can then be paired to yield two sets of 16 outputs. From there, one can report that the condition is satisfied if at least one input from the first group is high and all sixteen from the second group is high, or at least two from the first group and at least fifteen from the second group, or at least three from the first group and at least fourteen from the second group, etc. Possible, but expensive.

The first requirement could be satisfied by having 16 circuits each examine a pair of inputs and reporting whether both inputs of each pair are set, and then checking if any of those circuits reported true. Much simpler.

In this case, a human writing the specs migh recognize that a specification making the output high if any pair inputs had both inputs high would be cheaper to process than one which outputs low unless at least half of the inputs are high, but in many cases it would be useful for a compiler to be able to automatically identify which acceptable combination of behaviors could be realized most efficiently. Languages vary considerably in their ability to express such concepts.

Most people would consider "expressiveness" as the time it takes them to get a certain task done without bugs. As such, there won't be an accepted way to compare two languages. It would require an infinite set of expensive tests and people would argue if the the submissions are really comparable or if the subset of actual tests is a good one.

If there were such a notion, people could simply optimize on it. But this does not happen. In fact, the Python vs. assembly example is already wrong, because programming a micro controller with Python would not lead anywhere. Or if you want to make use of a certain processor instruction. What I'm trying to say here is that actual expressiveness depends on the domain you are operating in. In such a domain, certain concepts can help you that might even be considered a reduction of expressiveness in other domains. Ada has a lot of concepts that work well for programming rockets but are in your way when building common desktop software.

Nonetheless, if you really need such a notion for some sort of comparison you made, I'd try to go time to write a program for a predefined set of tasks. The issue with such comparisons is that they overrate languages that are good for trivial tasks and bad for implementing large software projects.

What you could also do is compare expressiveness of type systems. However, you'll end up in a similar situation as with Turing completeness, because a lot of them can express arbitrary proofs and computations and there is no really good way to say "in a sane piece of code".

• I think its not so much that it can't be done rationally and objectively but that it is hard. Not just AI hard but a hard multi-variable optimisation problem for humans too. By attempting to formalise it we try to remove the human biases. Commented Jul 8, 2023 at 10:40
• While I appreciate the idea, I doubt that the formalization will result in something that reflects the subjective understanding of "expressiveness" of most people. At least if it is provably a partial order on formal semantics of programming languages. The thing with these approaches is that marginal changes in the formalization can have massive impacts on the outcomes of such orders. Commented Jul 8, 2023 at 12:44