Is the capability of every programming language the same since it is eventually translated into machine code. Python, Java etc. are all together instructions the CPU is going to process. So, you could (theoretically) do the exact same thing with ever language, don't you?

  • 1
    $\begingroup$ This is essentially the statement of the Church-Turing thesis. $\endgroup$ – dkaeae Jan 9 '19 at 16:34
  • 1
    $\begingroup$ "since it is eventually translated into machine code" -- no, that's not the reason. One can easily define less powerful languages that translate into machine code. $\endgroup$ – Raphael Jan 10 '19 at 7:39
  • $\begingroup$ What kind of "capabilities" are you thinking about? Computer science is mostly concerned with issues of computability (can I computer this mathematical function?) and efficiency (of algorithms, rarely programs). Real programming languages are measured along many more axes. $\endgroup$ – Raphael Jan 10 '19 at 7:40
  • 1
    $\begingroup$ This is not the Church-Turing thesis. $\endgroup$ – Andrej Bauer Jan 10 '19 at 15:33

Yes, that's correct.

The usual justification for the computational equivalence of two programming languages X and Y is that we can write an interpreter runX for X programs written in the Y language, and vice versa.

Therefore, any program y written in Y can be simulated in language X using something like runX("y"), and vice versa. So, the computational power of the two languages is the same.

Sometimes, we state these fact stating "all programming languages are Turing-equivalent", i.e. that they can compute anything that a Turing machine can compute (and nothing else).

Note that this does not mean that the two languages have the same features. For instance, X might feature OOP classes, while Y might be purely procedural. X might have primitives for 3D graphics, while Y has not. X might allow access to files, Y might not. X might have garbage collection, when Y has not. X might be a functional (or logic) language, while Y is imperative. X might feature higher order functions, or dependent types, etc. which Y does not have. When we say that they have the "same power", here we only mean that they can compute the same set of functions (say, mapping an input strings to an output string).

Finally, note that there do exist some computer languages which are less powerful than general purpose programming languages like Python, Java, and the like. These are not usually called programming languages, even if they might share some aspects. For instance, the Bitcoin scripting language allows some limited computation, but has no loops (e.g. while), so it drastically restricts the algorithms one can implement. The basic querying part of SQL (select) is a simple reporting language, and is not Turing powerful (unless one adds triggers / stored procedures or other more advanced features.).

  • $\begingroup$ Well, some (arguably) general-purpose programming languages, like Agda, are not Turing-complete. But yes, they are a very small minority. $\endgroup$ – xuq01 Jan 9 '19 at 18:36
  • $\begingroup$ @xuq01 Agreed. I like to call those "total programming languages", to indicate that they would be Turing complete, if only they allowed some form of unbounded looping / unconstrained recursion. For instance Agda allows to disable the termination checker, IIRC, and become Turing complete. $\endgroup$ – chi Jan 9 '19 at 18:48
  • $\begingroup$ Well, adding general recursion/iteration makes everything Turing complete... $\endgroup$ – xuq01 Jan 9 '19 at 20:07
  • $\begingroup$ This answer is misleading because it fails to address the differences in language capabiilties when it comes to higher-order functions. $\endgroup$ – Andrej Bauer Jan 10 '19 at 15:44
  • $\begingroup$ @AndrejBauer Agreed. I tried to amend it, hoping that now it is no longer misleading. I'm not completely satisfied by the result, but at least I am no longer tempted to delete it. (If you think it's still harmful, let me know). I added a link to another Q&A which should better clarify that "computational power" and "language capabilities / expressiveness" are distinct aspects of PLs, to avoid confusion. $\endgroup$ – chi Jan 12 '19 at 11:07

The answer to the question depends on what you mean by "the same".

It is a famous result of computability theory that many reasonable models of computation all calculate the same nubmber-theoretic functions. That is, all reasonable general-purpose programming languages compute the same partial functions $\mathbb{N} \to \mathbb{N}$. So in this sense the capabilities of all programming languages are "the same". By the way, this is not the Church-Turing thesis, contrary to what you may be told.

However, a programming language can do many other things in addition to computing with numbers. For instance, it may access external devices, run parallel programs etc. While these features do not allow it to compute any extra number-theoretic functions, they may make a difference when it comes to computing other functions. For instance, a famous early example is that of the language PCF. It can simulate Turing machines, but it cannot compute the "parallel or" function, while its parallel variant PCF++ can.

When we look at higher-order functions languages differ in their capabilities. A purely functional language such as Haskell cannot compute the modulus of continuity but a functional language extended with local state can.

So it really depends on what you mean by "the same".

  • $\begingroup$ Can you expand a bit on what you mean in the second to last paragraph, or have a reference where I can read more about it? $\endgroup$ – user76284 Mar 12 '20 at 15:25
  • $\begingroup$ You mean the things about PCF and parallel or? $\endgroup$ – Andrej Bauer Mar 12 '20 at 19:06
  • $\begingroup$ I meant the modulus of continuity and local state. $\endgroup$ – user76284 Mar 12 '20 at 19:08
  • 1
    $\begingroup$ Oops, sorry, can't count paragraphs. Well, I wrote a blog post about it a while ago. $\endgroup$ – Andrej Bauer Mar 12 '20 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.