What is a programming language?

Or even a better question, what makes a programming language a programming language? 

Let’s start from a formal definition.

A programming language is a formal language used to communicate instructions to a computer. It conforms to a set of rules that determine what is and is not allowed.

Sounds like HTML is a programming language too.

Not so fast.

The decisive factor in what makes something a programming language (or not) is known as Turing completeness. 

Alan Turing was a brilliant British mathematician who took a leading role in breaking Nazi ciphers during WWII. A pioneer of theoretical computer science and artificial intelligence, he formalized concepts of algorithm and computation with the Turing machine, which can be considered a first MODEL of a general-purpose computer.

Before modern-day computers, Alan Turing hypothesized that there would one day be a machine that could solve any problem. 

In 1941 German engineer Konrad Zuse constructed Z3, the first Turing complete digital computer. I didn’t find any informations on how Turing reacted to this invention, a proof of his theoretical concept, but I believe he must have been thrilled.

So when is a system considered to be Turing complete?

A system (device or language) is Turing complete if, given enough time and memory with the necessary instructions, it can solve any computational problem, no matter how complex.

So in general for a programming language to be Turing-complete it needs:

  • Conditional branching
    A way to read and write to some storage mechanism (variables)
  • Loops that execute for infinitely many iterations
  • Input and output values 

Thus most programming languages are Turing complete. C, C++, C#, Java, PHP, JavaScript, Python. They are all turing complete.

Why is HTML not turning complete?

HTML cannot actively change the state of the system. Consider the definition of Turing completeness: „given enough time and memory with the necessary instructions, it can solve any computational problem“. And see the above mentioned set of Turing complete programming language features.

A simple calculator is another example of a system which is Turing incomplete since it can only do a few types of calculations.