G12FCO -- Formal Computation

Lecture 19 -- Computable numbers and functions

Computable numbers

We've seen that some sequences of numbers cannot be computed; what about individual numbers? Well, for finite integers and decimals, there is no problem; there is clearly a TM which `calculates' any such number and writes it on its tape and then halts. Of course, no real calculation need be involved; we can simply use a new state for each digit. Analogously, we could use a pseudo-QBasic program something like

	print "3.14159"

The difficulty comes when the number has an infinite representation. We would like to write a program rather like, say,

	print "3."
	while true do print "142857" endwhile

to be the way we construct 22/7. But that program never halts. What to do? In its TM version, how would we know whether digits written on the tape were `output' or part of the calculation? How would we know that the `output' would not be overwritten by a later part of the calculation? Here are some possibilities for what it could mean to compute a real number x:

The TM never stops, but it guarantees to write out the digits one by one and never overwrites one once written. [This could be enforced, for example, by insisting on some symbol, say #, being used as punctuation; any state which reads the # must overwrite the # with a digit or decimal point, then move right and the next state must re-write the #. This is easily checked by inspection of the arrays defining the TM.] The effect is that whatever is to the left of the # constitutes the start of a number, and is inviolate. Some separate mechanism is needed to read the number.
Ditto; but the separation is enforced by writing to a second tape. States which access the second tape are only allowed to write digits and decimal points and to move right. This makes some calculations simpler, and generalises better.
The TM starts with some integer n written on its tape, and is guaranteed to halt with the nth digit of x written on its tape.
Ditto, but with x computed as far as its nth digit.
Ditto, but with some finite number y written on its tape, where |x-y|<10^-n.

With one exception, these versions are all clearly equivalent, in the sense that if we have a TM for one of them, it is routine to convert it to any of the others [think rather of using any one of them as a callable subroutine in a QBasic or C program, so that we could invoke it to return a suitable string which could then be analysed to produce one of the other versions]. The exception is the old 0.999... problem in relation to the last version. Suppose the number y that is written looks like 0.999999; then we don't know whether x should really be 0.99999... or 1.00000..., so we can't write out even its first digit. But in this case, we simply write the TM so that it tries again with a larger value of n; either the ambiguity will eventually be resolved, or else x is exactly 1. we don't know which of these will happen, but 1 is computable anyway. See also later.

This discussion might suggest that the last version should be rejected as too complicated; but for some purposes it turns out to be the most natural.

Some computable numbers

All rational numbers are computable.: See above.
If x and y are computable, so are x+y, x-y, x×y and x/y [y/=0].: Imagine first a TM with three tapes. Use the TM that calculates x to evaluate x `as far as necessary' on tape 1, then hand over to the TM that calculate y to do likewise for y on tape 2, then use the elementary `school' algorithms to compute x+y [or whichever] on tape 3. We don't necessarily know how far is necessary when the calculation starts; so we must be prepared to re-start with greater accuracy. The details get messy, but there is no difficulty of principle; except ... our old friend 0.99999... [and, of course, 6.39999..., etc.], which crops up when we work out 0.333...+0.666... or 2.4142135...×0.4142135..., and so on. But again, all such numbers are rational and thus computable anyway. As before, we may not know which TM calculates x+y, but we still know it to be computable. Converting from the 3-tape form to a normal form, including some tidying up, is then routine.
If x is computable, so is any finite polynomial in x with computable coefficients.: Extension of previous result.
If x is computable, so are sin x, cos x, arctan x [tan^-1 x], e^x, log (1+x), etc.: From the obvious power series including a remainder term. Hence, e = e¹, pi = 4 × arctan 1 and root2 = e^{log(1+1) / 2} are computable, and so are most of the other numbers that one meets in real life.
All algebraic numbers are computable.: I.e. zeroes of polynomials with integer coefficients. The processes of numerical analysis, such as Newton-Raphson, can be used for these.

Some non-computable numbers

Almost all real numbers.: For the set of all Turing machines is countable, and hence so is the class of computable numbers, which is in one-to-one correspondence with a subset of that set.
The number h whose nth digit is 1 if the nth TM [in some ordering] halts when started on a blank tape and is 0 if it doesn't halt.: [To order TMs, you could take the descriptions as supplied to a universal TM, order them by length, and then alphabetically for TMs with descriptions of the same length.] For if h were computable, then a TM that computed it could be tweaked to solve the halting problem. It mattereth not that we don't know what h is; the unsolvability of the halting problem shows that no such TM exists, though there are of course TMs that calculate h to many decimal places, and hence that could be used to solve the halting problem for as-many-as-we-please TMs [if only we knew the value of h]. But h is a perfectly good real number, and we can, if we please, calculate it to whatever accuracy we desire. We have to resort to rather artificial numbers like h, because all the `obvious' numbers were shown to be computable!
But not the number p whose nth digit is 1 if the decimal expansion of pi includes [somewhere] a sequence of n 5's and is 0 otherwise.: For p is either 0.111..11000... or [almost certainly] 0.111..., and so is computable. Again, it mattereth not that in the present state of mathematical knowledge we don't know which case applies.
Similarly not the number h_n which is 1 if the nth TM halts and is 0 otherwise.: For both 0 and 1 are computable.

Computable functions

There is no problem with the concept of a computable function whose range and domain are [subsets of] the integers. We have seen previously examples of such functions that are not computable, including BB(n) and the h_n just mentioned when viewed as a function of n. Each function value is computable, but the set of such values is not.

For functions involving real numbers, as range or domain or both, we have to adopt one of the devices used above for real numbers. We must `supply' a TM which, in some sense, calculates x, and passes its results on to a TM that then calculates f(x). In programming terms, the function is a subroutine that operates on some value(s) passed as parameter(s). We cannot expect x to be presented exactly, so the subroutine must be prepared to work with what it gets, estimate the accuracy of its result, and ask for x to be presented more accurately if necessary.

Obviously, the fine detail depends on the representations being used. Since we want to be able to compose functions [f(g(x))], the simplest conceptual representation is perhaps one using many tapes and many separate TMs communicating in controlled ways through those tapes. For example, the machine that calculates x will have an `input' tape containing n, the integer which tells it how much accuracy is needed, and an `output' tape on which it writes its result. The machine that calculates f will have an output tape on which it, from time to time, writes a desired accuracy and an input tape on which it receives an answer; this machine does not need to know whether the answer is calculated by the x-machine or by, for example, the g(x)-machine [which is in turn communing with the x-machine], from which functional composition drops out immediately. Turning all of this into a conventional TM is then tedious and messy, but clearly possible -- the sort of job we use computers for!

This model obviously encompasses all the most usual functions that we compute when modelling bits of mathematics -- polynomials, sin, cos, exp, log, roots, compositions of these, at least when applied to suitable domains. Equally, all the most standard sequences, such as squares, cubes, factorials, Fibonacci, Pascal's triangle, things to do with permutations and combinations, etc. are computable. But note one curiosity:

Discontinuous real functions are uncomputable!

For example, suppose f(x) is defined to be 1 for x>=1/3, and to be 0 for x<1/3; the sort of function we deal with all the time in both mathematics and computing. But suppose x computes as 0.333.... Until we get a digit different from 3, we cannot tell whether x is greater than 1/3 or less than or equal to it; if, in fact x = 1/3, we will never get such a digit, we can never tell, and the computation of f doesn't terminate. We can't fall back on the device that it is one or the other, so it's computable either way -- the problem isn't to compute either 1 or 0, it is now very specifically to decide which.

For a different view of this same point, note that e^x is usually irrational, but for some particular irrational values of x, such as log 2. it is rational, and even an integer. There is no difficulty in writing `exp' machines that compute e^x for all x, in the above sense, nor in writing `log' machines that do likewise for log x, for x>0. How would you contemplate altering an exp-machine so that it certainly gave the right sign for e^x-2 in the event that x happened to be close to log 2?

In real computer programmes, you write the formula however it drops out, but then, of course, you are dealing not with real numbers but with a computer approximation to real numbers, and numbers like 1/3 don't [usually] even have a representation. If you use a symbolic algebra package, like Maple, then the package can use its known simplifications to replace e^{log 2}-2 by 0 [exactly], but this will help only with `known' mathematics, and therefore not with `almost all' real numbers and functions.

top of page

G12FCO home page. border=0

Previous lecture. border=0

Next lecture. border=0

Coursework 5 .