[OT] On the Expressive Power of Programming Languages

[H. S. Teoh]

On Sun, Nov 15, 2020 at 01:55:49AM +0000, Paul Backus via Digitalmars-d wrote:
[...]
> Expressive compared to what? I think pretty much everyone would agree
> that Rust is more expressive than, say, Brainfuck, but some would
> probably argue that it is less expressive than Lisp.
[...]

By what are you measuring expressiveness here?  Mathematically speaking,
BF has the same expressiveness as Lisp, and Lisp has the same
expressiveness as D: they are all Turing-complete.  I have not seen a
*mathematical* definition of expressiveness that would measure these
languages differently.

OTOH, if by expressiveness you mean conciseness of expressing common
computations, then you can probably argue BF is the least expressive of
them all, since you need to write a LOT of BF just to express what can
probably be expressed in a few lines of D; and Lisp is probably
somewhere up there above D.  But that would require that you define what
you mean by "common", and that's where you'll get into a tarpit because
reasonable people will disagree on what exactly constitutes a "common
computation".

Also, trying to find the "most expressive" language in terms of
conciseness is futile task, because that's equivalent to finding a
language whose constructs let you express any computation in the
shortest form possible, and this can be reduced to finding the optimal
compression algorithm. But finding the optimal compression algorithm is
equivalent to the halting problem, which is unsolvable.


T

-- 
It only takes one twig to burn down a forest.