I am very interested in the expressiveness of different languages. Everyone who has programmed in multiple languages knows that sometimes a language allows you to express concepts which you can't express in other languages. You can have all kinds of subjective discussion about this, but naturally it would be better to have an objective measure.
There do actually exist objective measures. One is Turing-Completeness, which means that a language is capable of generating any output that could be generated by following a sequential set of steps. There are also other lesser levels of expressiveness such as Finite State Automata.
Now, except for domain specific languages, pretty much all modern languages are Turing complete. It is therefore natural to ask the following question:
Can we can define any other formal measures of
expressiveness which are greater than Turing
completeness?
Now of course we can't define this by considering the output that a program can generate, as Turing machines can already produce the same output that any other program can. But there are definitely different levels in what concepts can be expressed - surely no-one would argue that assembly language is as powerful as a modern object oriented language like Python. You could use your assembly to write a Python interpreter, so clearly any accurate objective measure would have to exclude this possibility. This also causes a problem with trying to define the expressiveness using the minimum number of symbols.
How exactly to do so is not clear and indeed appears extremely difficult, but we can't assume that just because we don't know how to solve a problem, that nobody know how to. It is also doesn't really make sense to demand a definition of expressiveness before answering the question - after all the whole point of this question is to obtain such a definition.
I think that my explanation will be clear enough for anyone with a strong theoretical background in computer science to understand what I am looking for. If you do have such a background and you disagree, please comment why, but if you don't thats probably why you don't understand the question.
