Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 59 ยท Decidability and Computability

Computable Functions, Ackermann and the Busy Beaver

Learn total and partial computable functions, primitive recursion, the mu operator, the Ackermann function and the uncomputable busy beaver function with Python.

Up to now we asked yes/no questions: is this string in the language? Computability theory is just as much about functions: given an input number, produce an output number. A function is computable if some Turing machine, started on an encoding of x, halts with an encoding of f(x) on its tape. The arithmetic machines you built are examples: addition, subtraction and multiplication are all computable.

Two details matter. A function is total if it is defined for every input and partial if it may be undefined for some. A partial computable function has a machine that halts exactly on the inputs where f is defined, and runs forever on the others. A non-computable function is one for which no machine exists: the halting problem is the prototype, since its characteristic function (1 if the machine halts, 0 otherwise) is total yet not computable.

A ladder of computable functions

Primitive recursive Built with bounded loops only. Always total.
Total recursive Adds functions like Ackermann that outgrow every loop-bounded program.
Partial recursive Adds unbounded search, so a program may never stop.
Uncomputable Halting, busy beaver. No program at all.

Partial recursive = Turing computable.

1 / 2

Primitive recursive functions

Start with three basic functions, all obviously computable:

  • zero: Z(x) = 0
  • successor: S(x) = x + 1
  • projections: P_i(x_1, โ€ฆ, x_k) = x_i

and two ways to build new functions from old ones:

  • composition: h(x) = f(g_1(x), โ€ฆ, g_m(x))
  • primitive recursion: f(x, 0) = g(x) and f(x, n+1) = h(x, n, f(x, n))

Primitive recursion is a for loop whose number of iterations is fixed before it starts. Addition, multiplication, exponentiation, factorial, predecessor and truncated subtraction are all primitive recursive, and so are almost all functions you would write in everyday programs. Every primitive recursive function is total: its loops always end.

Unbounded search: the ฮผ operator

To get all computable functions we add one more tool, minimization: ฮผy [ p(x, y) ] is the least y for which a computable test p(x, y) is true. It is a while loop with no upper bound: y = 0; while not p(x, y): y += 1. If no such y exists, the loop runs forever and the function is undefined. This is where partiality enters.

Theorem. The partial recursive functions (primitive recursion + ฮผ) are exactly the Turing-computable partial functions.

Python Primitive recursion and the ฮผ operator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

exact_root is a genuinely partial function: on 50 the unbounded search never succeeds. The budget in our code is only there to keep the page responsive; a real machine would simply run forever. This is also why no algorithm can always tell whether a partial function is defined on a given input: that would solve the halting problem.

The Ackermann function

Are all total computable functions primitive recursive? No. The Ackermann function is a simple total, computable function that grows faster than every primitive recursive function:

TEXT
A(0, n) = n + 1
A(m + 1, 0) = A(m, 1)
A(m + 1, n + 1) = A(m, A(m + 1, n))

Its rows get quickly out of hand: A(1, n) = n + 2, A(2, n) = 2n + 3, A(3, n) = 2^(n+3) โˆ’ 3, and A(4, n) is a tower of exponentials. It needs nested recursion (the recursion is on a pair of arguments, one of which is itself a recursive call), which cannot be unrolled into loops with a fixed bound. It is computable because the rules always terminate: the pair (m, n) decreases in lexicographic order.

Python The Ackermann function

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The step count shows the effect: A(3, 5) already takes over forty thousand steps, and A(4, 1) millions. So we have a hierarchy: primitive recursive โŠ‚ total computable โŠ‚ partial computable.

Non-computable functions

A function is non-computable if no Turing machine computes it. We met one: the halting function h(M, w) = 1 if M halts on w, else 0. Others can be obtained from it. A famous one is the busy beaver.

The busy beaver

Consider all Turing machines with n states that use the tape alphabet {0, 1} and start on an empty tape (all zeros). Some of them halt, and some run forever. Define:

  • ฮฃ(n): the largest number of 1s that a halting n-state machine leaves on its tape;
  • S(n): the largest number of steps a halting n-state machine performs.

These are well defined: for each n there are only finitely many machines, so a maximum exists. But no algorithm computes ฮฃ or S. If ฮฃ were computable, we could decide the halting problem for an n-state machine by running it for S(n) steps: if it has not halted by then, it never will. The argument shows that S grows faster than every computable function, since otherwise halting could be decided.

Known values: ฮฃ(1) = 1, ฮฃ(2) = 4, ฮฃ(3) = 6, ฮฃ(4) = 13, ฮฃ(5) = 4098 (proved with computer assistance in 2024). Already for 6 states the best known machines run for more steps than the number of atoms in the universe, towers of exponentials, and the exact value is out of reach.

We can find ฮฃ(2) and S(2) by brute force. A 2-state machine has four transitions, each with 2 ร— 2 ร— 3 = 12 choices (write 0/1, move left/right, go to state A, B or the halting state H): 12โด = 20,736 machines. We run each for at most 60 steps. The machines that halt reveal the answer; the ones still running at step 60 look like non-halters, but nothing in the program can prove it.

Python Brute-forcing the 2-state busy beaver

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The result ฮฃ(2) = 4 and S(2) = 6 matches the literature. Notice that most machines (over half) were still running after 60 steps. For 2 states we know that they loop forever (the 2-state case has been completely analyzed), but the program only knows that it ran out of patience. For 5 states the best machine halts after 47,176,870 steps, and deciding the remaining candidates required years of work and a formal proof checked by a computer.

The same TM simulator can run a champion for 3 states: it leaves six 1s on the tape after 14 steps.

Python A 3-state busy beaver champion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Other non-computable things

  • Kolmogorov complexity: the length of the shortest program that prints a given string. It is well defined but not computable.
  • Does a program ever print "hello"? (Rice's theorem.)
  • The halting probability ฮฉ: the probability that a random program halts, a real number whose digits are not computable.

Computability sets a hard limit on what programs can do. Complexity theory, the next chapter's topic, assumes that the problem is computable and asks how much time and memory the best algorithm needs.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What distinguishes primitive recursive functions from general partial recursive functions?

    Unbounded ฮผ-search may fail to terminate, which creates partial functions.
  2. 2. Why is the Ackermann function not primitive recursive even though it is computable and total?

    Its growth outpaces every function built from bounded loops.
  3. 3. What is the busy beaver function ฮฃ(n)?

    It measures how much a tiny machine can write before halting.
  4. 4. Why is the busy beaver function not computable?

    Knowing a bound on halting time for all n-state machines would solve the halting problem.

Summary

  • A function is computable if a Turing machine halts with f(x) on its tape; total functions are defined everywhere, partial functions may diverge.
  • Primitive recursion (bounded loops) gives total functions; adding ฮผ (unbounded search) gives all partial computable functions.
  • Ackermann's function is total and computable but not primitive recursive.
  • The halting function and the busy beaver functions ฮฃ(n) and S(n) are not computable.
  • Computability tells us what can be solved at all; complexity tells us how efficiently.

Next: Back to the Theory of Computation overview