Power of a Programming Language

But it is not completely clear what is meant by the power of a programming language.

Say that you want to write a program that factors integers into smaller integers. For example, the integer 82861 can be factored into 41*43*47. A C program that does this works quickly for small integers. But for very large integers the program runs for a long time. Even if it uses the best know algorithm, the program would take several months to factor a 512-bit integer.

Now say that the language Blitzen enables you to program an algorithm that cannot be written in C, and that this program running on the same Pentium can factor 512-bit integers in milliseconds. In this case you would say that the language Blitzen is more powerful than C.

But this will never happen. No matter what features a programming language has, it can not be used to write programs that have more computational power than the underlying processor that runs it. Why? Because any program, no matter what language it is written it, must ultimately be translated into the machine operations of a processor. When the program is running, it is these machine operations that are executing. What can be computed must be the same as what can be computed by that processor. Since all processors (that implement the minimum set of operations) have the same computing power, no programming language can have more power than that.

So any program that could be written in any language can be written in C (and can be written in any other Turing Complete programming language.)

Some special-purpose languages have less power than is possible. For example, HTML is a formal language for describing web pages but cannot be used as a general purpose programming language.