Mathematics Enters the 20^th Century

If we would obtain an idea of the probable development of mathematical knowledge in the immediate future, we must let the unsettled questions pass before our minds and look over the problems which the science of today sets and whose solution we expect from the future. – David Hilbert

In 1900, the eminent German mathematician David Hilbert set out a series of challenging problems for mathematicians in the twentieth century.
Many of those problems turned out to be relatively easy, but several remain unsolved even today.
Several of Hilbert’s 23 original problems, along with others he devised later, were resolved in a way that shook the foundations of the mathematical community.

Hilbert’s Entscheidungsproblem

Of the problems that have significance to computer science, the most important is the Entscheidungsproblem, which was posed in 1928. In informal terms, the Entscheidungsproblem can be expressed as follows:

Is it possible to find a mechanical procedure that can determine, given a specific proposition in a formal system of symbolic logic, whether that proposition is provable within that system?
Hilbert and the mathematicians of his day assumed that such a mechanical procedure was indeed possible, but a series of mathematical results in the 1930s—by Kurt Gödel, Alonzo Church, Alan Turing, and Emil Post—showed that such a mechanical procedure is a logical impossibility.

Kurt Gödel’s Incompleteness

Kurt Gödel had a set of “incompleteness theorems” that discussed formal systems with respect to consistency, completeness, decidability.
- First incompleteness theorem:
  - 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:
  - For any consistent system F within which a certain amount of elementary arithmetic can be carried out, the consistency of F cannot be proved in F itself.
Gödel’s Incompleteness theorems can be thought of as follows:
- Any set of axioms is either self-contradictory, or cannot prove some true statement about numbers. You can still prove every logical consequence of the axioms you have, but you can never get enough axioms to ensure that every true statement about numbers is a logical consequence of them.
In other words: there will always be true facts that are not a logical consequence of your axioms.

Alan Turing’s Contribution

Alan Mathison Turing, a young British mathematician just out of Cambridge, helped settle the Entscheidungsproblem by developing a model for computation by a mechanical procedure.
Turing’s model—which is now known as a Turing machine—is a central concept in theoretical computer science.
Turing is widely recognized as one of the most important figures in the history of computer science. The field’s most prestigious prize is the Turing Award, which is given in his honor.

Relevant parts for this seminar: 22:38 - 24:40, 28:30 - 34:55

Designing the Turing Machine

In his groundbreaking 1936 paper, “On computable numbers, with an application to the Entscheidungsproblem,” Turing described the process of computation in informal terms:

It may be that some of these changes necessarily involve a change of state of mind. The most general single operation must therefore be taken to be one of the following: (a) A possible change of symbol together with a possible change of state of mind. (b) A possible change of observed squares, together with a possible change of state of mind. The operation actually performed is determined, as has been suggested above, by the state of mind of the computer and the observed symbols.
These operations and the notion of a “state of mind” form the basis for the Turing machine.

Turing Machine components

For a Turing machine, a computation requires:
- Scratch paper
- An unbounded amount of space
- At least two symbols
- A read/write mechanism
- Some form of program control
We have a turing machine simulator that looks like this:

An Example Turing Machine

The way the machine works is as follows:
- Our machine primarily performs calculations on integers, though technically it is as “powerful” as any computer, in the sense that it would be possible to rewrite any program (except ones that have input, graphical output, etc.) on our machine. In other words, anything computable can be computed on a turing machine, just like it can be computed on a modern computer.
- The tape starts at a particular location, and there may be 0s or 1s already on the tape.
- With the type of machine we are using, numbers are written in unary, meaning that they are just strings of 1s, with the number of 1s representing the number. For example:
  - 1111 is the number 4
  - 1 is the number 1
  - 111111 is the number 6
- Note that it is not possible to represent 0 easily, but we won’t worry about that for our machine.
- A proper calculation leaves the head of the tape on the first digit of a number.
- The machine starts in state 1, and if it ever reaches state 0, the program stops.
- Instructions are formatted as follows:
  - Either a 0 or a 1 at the start of the instruction, meaning that the machine will immediately write a 0 or a 1.
  - An “R” or “L”, meaning that the tape head will then move either Right or Left.
  - A number for the next state to go to.
  - When the machine is run, the instruction that is read is based on the instruction number and whether the tape is over a 0 or a 1. So, for our example, because the tape head is over a 0, the instruction that is read is the one in instruction number 1 in the 0 column (highlighted above in yellow).
  - The machine will continue to process instructions forever, or until the machine goes into state 0.
Let’s take a look at the program above, “Write-4” on the turing machine simulator.
You can actually make a real turing machine simulator!

Why do we represent numbers in unary?

Even though the standard Turing machine alphabet consists of the digits 0 and 1, it is not practical to represent numbers in binary. Why?
Instead, as described above, numbers are written in unary in which each number is written as a sequence of 1s. The 0 symbol is used to indicate the start and end of a number.
An input configuration for the Turing machine is well-formed if it consists of a single number in which the tape head appears over the first 1 digit.

Exercise: Subtraction

Write a program that takes two numbers on the tape and subtracts the second from the first. Thus, if the initial tape contains

the final tape should look like this:

Assume for the moment that the first number is larger than the second. What happens to your program if that isn’t true?

Composing Machines ($M_{2x+3}$)

Suppose you wanted to compute the function $2x + 3$, given that you have the machines $M_{2x}$ and $M_{+3}$.

Start with the two machines.
Renumber the states in $M_{+3}$.
Combine the machines.
Change halt transitions in $M_{2x}$ to jump to $M_{+3}$.

The Busy Beaver Problem

Tibor Radó (1895-1965)

Although it is possible to introduce the notion of undecidable problems using Turing’s original argument involving a “universal” Turing machine, it is much easier to do so in the context of a more recent problem posed by Tibor Radó in the early 1960s:

What is the largest finite number of 1s that can be produced on blank tape using a Turing machine with $n$ states?

This problem is called the Busy Beaver Problem

The Function $BB(n)$

The Busy Beaver problem has a natural expression as a mathematical function. If $n$ represents the number of states, let $BB(n)$ represent the largest finite number of 1s that can be written on blank tape by a machine of that size.
For very small values of $n$, it is fairly easy to determine the value of the BB function:

$$BB(1) = 1$$ $$BB(2) = 4$$ $$BB(3) = 6$$

From there, the situation gets much harder. Proving that $BB(4) = 13$ was a Ph.D. thesis. $BB(5)$ was just proven, in July 2024. Any guesses as to what its value is?

$4,098$

It took 41 years to prove this.
No one is yet sure of the values for any higher number, although a conjecture exists for BB(6). However, this number is big – it is at least as big as ten raised to itself 15 times:

$$10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10}}}}}}}}}}}}}}$$

We can also think of the number of steps that this would take, and the numebrs grow very quickly:

n	Ones-maximizing Σ(n)	Step-maximizing S(n)
1	1	1
2	4	6
3	6	21
4	13	107
5	4,098	47,176,870

Here are the BB machines that we know of (and a conjecture for $BB(6)$

BB1 — 1 step, 1 one

State	0	1
1	1R0

BB2 — 6 steps, 4 ones

State	0	1
1	1R2	1L2
2	1L1	1R0

BB3 — 14 steps, 6 ones

State	0	1
1	1R2	1R0
2	0R3	1R2
3	1L3	1L1

BB4 — 107 steps, 13 ones

State	0	1
1	1R2	1L2
2	1L1	0L3
3	1R0	1L4
4	1R4	0R1

BB5 — 4098 ones with 8191 zeros interspersed in 47,176,870 steps

State	0	1
1	1R2	1L3
2	1R3	1R2
3	1R4	0L5
4	1L1	1L4
5	1R0	0L1

BB6 — (conjectured)

State	0	1
1	1R2	1L5
2	1R3	1R6
3	1L4	0R2
4	1R5	0L3
5	1L0	1R3
6	1L1	0R4

Computing $BB(n)$

Given that $BB(n)$ is a mathematical function, it makes sense to ask whether that function can be computed by a Turing machine. In other words, is there a machine $M_{BB}$ that takes a number of 1s representing n as input and writes out a number of 1s representing $BB(n)$ as output?
It turns out that the answer is no. There is no Turing machine $M_{BB}$ that computes the BB function. What’s more, we’ll be able to prove that such a function cannot be computed at all.
The BB function is an example of an uncomputable function, which is the profound new idea that Alan Turing and several of his contemporaries introduced to the mathematical world.

Observations about $BB(n)$

In order to resolve the question about whether BB(n) can be computed by a Turing machine, it helps to make two observations about the BB function:
1. $BB(n)$ is a well-defined mathematical function. It does exist. For every number of states, the number of possible Turing machines is finite. There must be some machine that writes out at least as many 1s as any other.
2. $BB(n)$ must be strictly increasing. With an extra state, it is always possible to write at least one more 1 than is possible with a Turing machine with fewer states.

Proof by Contradiction

In seeking to prove that $BB(n)$ is not computable by a Turing machine, the simplest approach is to employ a strategy called proof by contradiction. In proof by contradiction, you start by assuming the opposite of what you wish to prove, and then show—typically by constructing a specific example—that doing so leads to an absurd conclusion or that violates one of the assumptions. If the steps in your construction are correct, the only questionable part of the process is the original assumption.
Thus, to prove that $BB(n)$ is not computable by a Turing machine, we start by assuming that it is. That means that we can assume the existence of a machine $M_{BB}$ with β states that takes n as input and writes out $BB(n)$ 1s as output.
The essence of the contradiction is to construct a machine with k states that writes out more than $BB(k)$ 1s.

Steps in the Proof

So, it looks like we have created a machine that has $2\beta + 14$ steps and produces $BB(2\beta + 14) + 1$ number of 1s.
This is a contradiction, becauase if we had such a machine, it would be a better Busy Beaver than $BB(2\beta + 14)$, which is supposed to produce the largest number of 1s possible for a machine with $2\beta + 14$ states. Because we found a machine that does better, we can never produce a Busy Beaver function.

But wait…why can’t we??

Despite the proof by contradiction, the idea that $BB(n)$ is uncomputable seems wrong. After all, we can simulate a Turing machine. Why isn’t it possible to solve this problem using the following approach:
1. Generate every Turing machine with $n$ states. There is only a finite number of such machines.
2. For each machine, run the Turing machine simulator and count the number of 1s it generates.
3. Keep track of the largest value so far and report that number at the end of the run.
There is a problem here. Some of the machines go on forever, so there is no way to terminate the computation in step 2.
If it were possible to tell whether a Turing machine would halt, it would be possible to compute the $BB(n)$ function.

The Halting Problem

A famous example of an uncomputable problem is the halting problem. It says,

Given a program, and some input, determine if the program halts or runs forever.
It is possible to determine this for many programs, but it is impossible to do this in a generic way, such that we can always tell if a program will halt or not.
We can construct a surprisingly simple contradition that shows that it is impossible:
1. Assume we have an algorithm Halts(P, I) that, when given a program P and input I, prints either “halts” or “runs forever.”
2. Let’s write the following program:
```
function Contradict(Q):
    if Halts(Q, Q):
        loop forever
    else:
        halt immediately
```
3. So far, so good. But, what if we run Contradict(Contradict)? In other words, what if we feed the program text Contradict into itself?
  - If Contradict(Contradict) says it halts, Contradict will run forever (this is a contradiction – it should have halted!)
  - If it says “runs forever” Contradict will halt (also a contradiction – it should have run forever!)
What this means is that no algorithm can always decide halting for arbitrary programs. Therefore, it is an uncomputable problem – no computer program can ever solve this problem generically.
This is a very good animated video describing the halting problem:

The Church-Turing Thesis

The question of what is computable by a Turing machine is important in a search for what is generally computable mostly because no one has ever found a more powerful model.
Most computer scientists believe what has come to be known as the Church-Turing thesis:

No method of computation carried out by a mechanical process can be more powerful than a Turing machine.
This claim remains a conjecture, and it is not clear there is any way to prove it. At the same time, it has so far resisted all efforts to disprove it.

P -vs- NP

The class P consists of all decision problems that can be solved in polynomial time by a deterministic Turing machine.
The class NP consists of all decision problems that can be solved in polynomial time by a nondeterministic Turing machine.
A decision problem is one that has only a yes-or-no answer.
Polynomial time is a measure of computational complexity that is bounded by a polynomial.
A deterministic Turing machine follows only one execution path at a time.
A nondeterministic Turing machine can follow multiple paths in parallel.
The P = NP question is whether these two classes are the same.

Seminar 3

Turing Machines and Theory of Computation