Uncomputable Numbers

Real numbers we can never know the value of

Jørgen Veisdal
Jul 11 · 15 min read
Approximating upper and lower bounds for the value of pi using pentagons (left), hexagons (middle) and octagons (right).
First incompleteness theorem (Gödel, 1931a)
Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are statements of the language of F which can neither be proved nor disproved in F.
Second incompleteness theorem (Gödel, 1931b)
No consistent axiomatic system which includes Peano arithmetic can prove its own consistency.

Definitions

Real numbers that can be computed to within any desired precision by a finite, terminating algorithm.

Modern definition of a computable real number a given positive integers n, f(n)

History

Left: Alonzo Church. Right: Alan Turing (Photos: Princeton University)

Alonzo Church

Alan Turing

Uncomputability

Entscheidungsproblem

The Entscheidungsproblem is solved when we know a procedure that allows for any given logical expression to decide by finitely many operations its validity or satisfiability.

Church’s solution

First definition of computability (Church, 1934)
A function is effectively calculable if and only if it is λ-definable.
Second definition of computability (Church, 1936)
A function on the positive integers is effectively calculable if and only if it is recursive.

Turing’s solution

Turing's definition of computability (1936)
A function is intuitively computable (effectively computable) if and only if it is computable by a Turing machine; that is, an automatic machine (a-machine) as defined in Turing (1936)
A Turing machine (a-machine) is a mathematical model of computation that defines an abstract machine which manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed.
"But Turing has shown more. He has shown that the computable functions defined in this way are exactly those for which you can construct a machine with finite number of parts which will do the following thing. If you write down any number n₁, n₂, ..., nᵣ on a slip of paper and put the slip into the machien and turn the crank then after a finite number of turns the machine will stop and the value of the function for the argument n₁, n₂, ..., nᵣ will be printed on the paper."

Uncomputable numbers

Proof sketch of the countability of the computable numbers
By assigning a Gödel number to each Turing machine definition produces a subset S of the natural numbers corresponding to the computable numbers. A surjection from S to the computable numbers shows that the computable numbers are at most countable.

Example A: Chaitin’s constant Ω

Chaitin's Thought Experiment (Barmpalias, 2018)
Suppose we run a universal Turing machine on a random binary program. Specifically, whenever the next bit of the program is required, we flip a coin and feed the binary output to the machine. What is the probability that the Turing machine will halt?
Halting probability of Turing machine U given input σ

Example B: The Busy Beaver Problem BB(n)

What is the largest finite number of 1s that can be produced on blank tape using a Turing machine with n states?
Proof that BB(n) is not computable (Roberts, 2016)
We start by assuming that the Busy Beaver function BB(n) is computable, and that there exists a Turing machine Mᴮᴮ with β states that takes n as an input, writes BB(n) number of 1s as output and then halts. Let Clean denote a Turing machine cleaning sequence of 1s initially written on the tape. Let Double denote a Turing machine evaluating function n + n.
Given a tape with n 1s it will produce 2n 1s on the tape, then halt. Now create the routine 'Double | EvalBB | Clean' and let n₀ be the number of states of this machine. Let Create_n₀ denote a Turing machine creating n₀ 1s on an initially blank tape. Let N denote the sum n₀ + n₀.Let BadBB denote the routine 'Create_n₀ | Double | EvalBB | Clean'. This machine has N states (n₀ + n₀). Running BadBB will produce BB(N) 1s on the tape before clearing all 1s and halting. But the step of cleaning will continue at least BB(N) steps, so the computation time of BadBB must be strictly greater than BB(N), which contradicts the definition of the function BB(n).

Example C: Penrose Tiling

Penrose tiling

Epilogue

Church-Turing thesis
A function is intuitively computable if and only if it is computable by a Turing machine, or equivalently if it is specified by a recursive function

No method of computing carried out by a mechanical process can be more powerful than a Turing machine.


Cantor’s Paradise

New math essays every week!

Jørgen Veisdal

Written by

Writer. Ph.D. research fellow at NTNU.

Cantor’s Paradise

New math essays every week!