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

The answer given is thorough, but somewhat abstract. As a more concrete response, go to projecteuler.net, solve a problem, and go to the discussion board for it.<p>For most problems:<p>There will be a ~80 line C solution.<p>There will be a ~120 line Java solution.<p>There will be a ~50 line Javascript solution.<p>There will be a ~40 line Visual Basic solution.<p>There will be a ~30 line PHP solution.<p>There will be a ~25 line raw Python solution.<p>There will be a ~20 line typical Lisp solution.<p>There will be a ~15 line Python solution using some obscure library.<p>There will be a ~10 line Lisp solution using some clever hack.<p>There will be a 1 line J solution.<p>(other languages omitted, and line estimates are pulled out of my ass)<p>Whether due to unfamiliarity or genuine opacity, some of the shorter solutions will be incomprehensible to some (most?) people. So while <i>technically</i> more expressive, what good is that if you can&#x27;t read the solution, let alone write it?<p>But yeah -- typical line count proxies (inversely) for expressiveness.

I don&#x27;t think this formalization does a great job of what we intuitively mean by expressive power.<p>For one thing, there is no real way to use this definition to compare different languages, only the same language with one extra feature.<p>For another, even for individual features, it is too coarse. The very fact that it doesn&#x27;t consider syntactic sugar expressive is wrong - most people would agree that a language with more syntax sugar is more expressive, since it allows you to avoid writing boilerplate. By this definition, list comprehensions and switch expressions for example don&#x27;t add expressive power to a language.<p>Even if we ignore syntax sugar, the comments point out another counterintuitive property of this definiton: any language which includes a facility to convert expressions to ASTs is maximally expressive, since that facility can be used to distinguish any two expressions. This includes things like Lisp&#x27;s `quote&#x27; special form or C&#x27;s # macro, but also built-in code parsers. So, C++ for example added no expressive power to C by this definition, since C was already maximally expressive:<p><pre><code> #define quote(x) #x if (strcmp(&quot;3 + 3&quot;, quote(3 + 3)) {return 1;}</code></pre>

Glad to see Matthias Felleisen&#x27;s paper &quot;On the Expressive Power of Programming Languages” mentioned right off the bat.<p>Shriram’s talk on the same is mentioned too—Shriram is a great guy and I’ve enjoyed all my interactions with him. He’s working on improving CS education. There’s a neat program called “Bootstrap” that he’s helped found that aims at teaching algebra with programming. The idea is that functional programming helps students grok important algebraic concepts. (Sorry if I slaughter the description.)<p>Anyway, I appreciate these people and their work. Cool stuff.<p>(Disclaimer: my advisor has had both Shriram and Matthias as advisors. I thought they were cool before starting my PhD though, so it’s genuine. :)

The answer is great, but I&#x27;m questioning its underlying assumption of what &quot;expressiveness&quot; really means, upon which the remainder of the explanation rests.<p>&gt;&gt; We can get closer to a formal statement by saying: a feature does not &quot;add expressive power&quot; if we can implement it as a macro that turns it into something in the original language<p>If adding features that could be implemented as macros doesn&#x27;t make the language more &quot;expressive&quot;, then the inverse should be true: Removing features that could be implemented as macros would not make a language less &quot;expressive&quot;.<p>This seems to favor c++, in which basically anything imaginable can be done with macros, and any other language can be implemented. There&#x27;s no global-level total <i>thing</i> that&#x27;s missing which can&#x27;t be cleverly built at an inline level. Yet all of c++&#x27;s granularity in memory management requires a huge amount of verbosity, which is to say it <i>isn&#x27;t</i> as expressive (to me) as something that just runs garbage collection out of the box and makes assumptions about weak vs. strong references and lets you tinker with them if or when you like.<p>&quot;Expressive&quot; to me implies being able to get a lot of meaning across in a few choice words, whilst having a broad vocabulary to choose from.<p>Does adding .reduce() add no expressiveness to Javascript, just because it&#x27;s easily implemented with a macro? I&#x27;d argue it adds a lot, because it adds a new color to the palette; it gives rise to styles of programming that allow one to distinguish intentionally between normal loops and functional recursion, and choose, i.e. <i>express</i>, the music according to their own intent.

In my humble opinion the SO question and some of the comments here conflate &quot;expressive&quot; as it&#x27;s used when talking about the theory of computation and &quot;expressive&quot; as it&#x27;s used when comparing various high-level programming languages. The former has a very precise (but also quite narrow) formal meaning and the later is just the normal English work &quot;expressive&quot;. They mean very different things so I think it&#x27;s a bit unfortunate that we use the same word for both because some people get the idea that they&#x27;re somehow related when they&#x27;re really not. I mean, in a way regular expressions are more expressive than turing machines but turing machine are more expressive than regular expressions.

Even though that&#x27;s a reaction on the title rather than the (interesting) content, I would like to add that Turing-completeness isn&#x27;t the gold-standard of languages. Some very interesting languages like Agda or Idris focus on the benefits of abandoning it.

Strongly recommend the talk on which this answer is based: <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=43XaZEn2aLc">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=43XaZEn2aLc</a>

David Young&#x27;s answer seems to give a precise mathematical criterion for deciding whether a language feature is mere syntactic sugar or more fundamental. Neat!

What are some practical examples of expressive features that distinguish popular languages?<p>The link mentions exceptions and operator overloading.<p>I won’t embarrass myself by speculating here :)

I like the phrase &quot;pacman-complete&quot;, that Brady coined for Idris, to express more practical concerns besides pure algorithmic computation. Personally I would argue that for example brainfuck is not pacman-complete despite being turing complete. But then interestingly enough I don&#x27;t think pacman completeness necessary implies turing completeness either.

Regarding the definition of “observational equivalence”: I would love to see an example of two non-trivial statements that aren’t equal but are observationally equivalent. It seems impossible in almost any programming language.

I don&#x27;t even think that Turing completeness and expressive power are linked at all. You could easily imagine a language like haskell without general recursion or inductive date types. It&#x27;s still much, much more expressive then C, but without the Turing completeness.<p>Expressive power to me is something akin to &quot;how easy is it to express a problem as close as possible to it&#x27;s natural state in a PL&quot;.

I&#x27;m interested in the more general problem; how can you compare expressive power between completely different models of computation?<p>Are neural networks more or less expressive than other forms of computation like register machines? What makes them so? And what can we do to make them more expressive while still being trainable?

In CS 61A we weren&#x27;t taught about Turing complete, we simply learned that expressive power is the ability to represent the abstractions you use to solve or model a computational problem correctly and efficiently.

Have language X implement language Y and vice-versa?

Understand curry howard and you&#x27;re on your way to answering this question<p>Every person i&#x27;ve met who uses turing equivalence as a real argument about PLs has been a deficiency clown

I feel like these kind of questions will be explored more in the future when LLMs are more powerful. You could get some equivalent corpuses of different languages and train an LLM on each one and then see how capable is the resulting LLM of the respective language. Presumably if everything else is equal the language with more capable resulting LLM would be better in some sense, maybe this sense would be called &#x27;expressive power&#x27; or maybe called another thing.