Computer Science › Section M · Theory of computation › Topic M.3

Universal programming languages

Python offers lists, functions, objects and dozens of other features, but how many does it actually need? Surprisingly few: a language with one kind of variable, three simple statements and one loop can compute everything any language can.

What does a language really need?

The languages in section G differ in data types, control structures and paradigms. Which of those features add genuine power, and which only add convenience? A programming language is universal, or Turing complete, if its programs can compute every Turing-computable function. By the Church–Turing thesis from "Turing machines", that means every function any algorithm can compute. If a problem cannot be solved in a universal language, the language is not to blame: the problem has no algorithmic solution at all. The surprise is how little a universal language must contain.

Tally: a language with four statements

Consider a tiny language we will call Tally. Every variable holds a non-negative whole number, which loses nothing, since all data can be read as whole numbers, and a name can be used without being declared. There are three assignments: X = 0 sets X to zero; inc X adds 1 to X; dec X subtracts 1, except that it leaves 0 unchanged. The only control structure is a loop, while X != 0:, followed by an indented body. Its variable is tested before every pass: if it is zero the body is skipped, otherwise the body runs and the test is made again. The textbook's version, called Bare Bones, spells these statements differently.

Programs as functions

A Tally program computes a function. The inputs are the starting values of some variables, and the outputs are the values of others when the program halts. The one-line program inc X computes the successor function, n + 1. Tally gives the programmer full responsibility for loops: the body must eventually make the tested variable zero, or the loop never ends. In the loop while Y != 0: inc X, for example, nothing changes Y, so the loop runs forever whenever Y starts above zero. Unlike Python, Tally offers no if, no for, no lists and no functions.

Worked example: tripling a number

This program sets Z to three times X.

\begin{array}{l} \texttt{Z = 0} \\ \texttt{while X != 0:} \\ \quad \texttt{inc Z} \\ \quad \texttt{inc Z} \\ \quad \texttt{inc Z} \\ \quad \texttt{dec X} \end{array}

Trace it with X = 2. 1. Z = 0. 2. X is 2, not zero, so the body runs: Z = 3 and X = 1. 3. X is 1, so the body runs again: Z = 6 and X = 0. 4. X is now zero, so the loop ends and the program halts with Z = 6. Check: 3 × 2 = 6. Each pass adds 3 to Z and removes 1 from X, so Z = 3X for every X; with X = 0 the body never runs and Z stays 0. Note the side effect: X itself ends at zero.

Building blocks: setting and copying

Any value can be set by clearing and counting up: X = 0 followed by inc X twice sets X to 2. Copying is harder, because moving X into Y by counting X down destroys X. The fix is a helper variable T, which takes X's value and then rebuilds both X and Y:

\begin{array}{l} \texttt{T = 0} \\ \texttt{Y = 0} \\ \texttt{while X != 0:} \\ \quad \texttt{inc T} \\ \quad \texttt{dec X} \\ \texttt{while T != 0:} \\ \quad \texttt{inc X} \\ \quad \texttt{inc Y} \\ \quad \texttt{dec T} \end{array}

Starting from X = 4, it ends with X = 4, Y = 4 and T = 0. We may now write copy X to Y as shorthand, provided each use gets a helper name not used elsewhere.

Worked example: an if from a loop

Tally has no if statement, but if X != 0: inc Y can be built.

\begin{array}{l} \texttt{copy X to T} \\ \texttt{while T != 0:} \\ \quad \texttt{inc Y} \\ \quad \texttt{T = 0} \end{array}

1. The copy keeps X safe, since the loop will wipe out T. 2. If X = 0, then T = 0, the body is skipped and Y is unchanged. 3. If X = 5, then T = 5, the body runs once, adding 1 to Y, and then sets T = 0, so the test fails and the loop ends after one pass. 4. Either way the body ran once or not at all, exactly as an if should. Check with Y = 10: X = 0 leaves Y = 10, and X = 5 gives Y = 11.

Why Tally is universal

Researchers have shown that languages like Tally can imitate any Turing machine. The outline: keep the machine's current state as a number in one variable, encode the tape contents on each side of the head as numbers in others, and turn each rule of the transition table into a section of program that updates those numbers. Since every Turing machine can be imitated, Tally computes every Turing-computable function, and by the Church–Turing thesis every computable function. So if an algorithm exists for a problem, some Tally program solves it, however long and awkward that program might be.

Every general-purpose language contains Tally

Python, Java and C can each set a variable to zero, add 1, subtract 1 and loop while a value is not zero. Each therefore contains Tally at its core and is universal too, apart from the practical limit of finite memory. Everything else they offer, such as if and else, for loops, functions, lists, recursion and objects, adds convenience and clarity, not computing power. That convenience matters enormously for writing programs people can read and trust, but it does not change what can be computed in principle.

The ingredient that matters

The essential ingredient is a loop whose number of passes need not be known in advance. Suppose while were replaced by repeat X times:, with the count fixed when the loop starts. Every program would then halt, which sounds attractive, but such languages are proved to miss some computable functions: the Ackermann function, for instance, grows too fast for any of them. Basic regular expressions are not universal either: they can repeat a pattern without limit but have no variables to count with. The price of universality is that some programs never halt, which is where "A noncomputable function: the halting problem" begins.

Common mistakes to avoid

First, thinking a language with more features can compute more: Python and Tally compute exactly the same functions. Second, forgetting that dec stops at 0, so dec X leaves 0 unchanged and never gives a negative number. Third, writing a loop whose body never changes the tested variable. Fourth, copying with a single loop, which empties the original. Fifth, reusing a helper variable that the program already uses elsewhere. Sixth, expecting a universal language to guarantee that its programs halt: universality makes endless loops possible.

Key takeaways

A universal, or Turing-complete, language can compute every Turing-computable function, so by the Church–Turing thesis every computable function. Tally, with whole-number variables, X = 0, inc X, dec X and while X != 0:, is universal: it can imitate any Turing machine. Copying, setting values and if statements can all be built from its statements. Python, Java and C contain the same core, so their extra features add convenience, not power. Universality needs loops of unlimited length, and with them comes the possibility of programs that never halt.

Flashcards

Flashcard

Universal language

Can compute every Turing-computable function

Also called Turing complete.

Test your understanding

Question 1 of 5

In Tally, the program Z = 0; while X != 0: (inc Z; inc Z; dec X); inc Z runs with X = 3 at the start. What is Z when it halts?

Question 2 of 5

In Tally, X starts at 1 and the statements dec X; dec X; inc X run. What is X at the end?

Question 3 of 5

What makes a programming language universal?

Question 4 of 5

Suppose Tally's while loop were replaced by repeat X times:, with the count fixed when the loop starts. What would happen?

Question 5 of 5

In the if-from-a-loop program, why does the loop body end with T = 0?

← Previous topicNext topic →