Assign an integer to each Turing machine.
First, we fix an encoding scheme (or method) for all Turing machines (of some fixed kind, such as the one defined here) that encodes each Turing machine into a string of 0s and 1s. This string is interpreted as a positive integer in binary form.
Hence each Turing machine corresponds to an integer. Conversely, a positive integer may correspond to a Turing machine. For a positive integer $n$, if $n$ corresponds to a Turing machine, use $f_n$ to denote that Turing machine. Otherwise, $f_n$ is undefined.
Diagonalization
$$\text{For all }n\in\mathbb N,\ g(n)=\begin{cases}f_{n}(n)+1 & \text { if both } f_{n}\text{ and }f_n(n) \text { are defined,} \\ 1 & \text { otherwise.}\end{cases}$$
The statement above defines a function $g$ from $\mathbb N$ to $\mathbb N$.
Why is $g$ not computable?
For the sake of contradiction, suppose $g$ is computable.
Then $g$ can be computed by some Turing machine. Assume that Turing machine is encoded as positive integer $k$. That is, that Turing machine is $f_k$.
What is the value of $g$ at $k$? Since $g$ is computed by $f_k$, $g(k)=f_k(k)$.
On the other hand, replacing $n$ by $k$ in the definition of $g$, we have
$$g(k)=\begin{cases}f_{k}(k)+1 & \text { if both } f_{k}\text{ and }f_k(k) \text { are defined,} \\ 1 & \text { otherwise}\end{cases}$$
There are two possible cases.
- Both $f_{k}$ and $f_k(k)$ are defined.
Then $g(k)=f_k(k)+1$, which is not equal to $f_k(k)$.
- Otherwise, $f_k(k)$ is undefined (that is, the Turing machine that computes $g$ does not halt when the input is $k$).
Then $g(k)=1$, which is not equal to $f_k(k)$ since $f_k(k)$ is undefined.
So in all cases, $g(k)\not=f_k(k)$, which contradicts the fact that $g(k)=f_k(k)$. This contradiction shows our assumption, $g$ is computable must be wrong.
Where does the trick come from?
We want to construct/describe/define a function $g$ that is not computed by any Turing machine.
More explicitly, for each Turing machine, we want to do two things:
- find a number
- describe the value of $g$ at that number so that the value is different from the output of that Turing machine given that number as input.
A simple approach is to use the same number always, say $2022$ or $152866$. However, whatever value we let $g(2022)$ or $g(152866)$ be, there is a Turing machine that outputs $g(2022)$ given $2022$ as input (and outputs $g(152866)$ given $152866$ as input).
The idea is to find a different number for each different Turing machine.
For a Turing machine and the corresponding number, we will let $g$ at that number be any value that is different from the output of that Turing machine. For example, $g(k)=f(k) + 153595$. For example, $g(k)=f(k)^2 + 42$. If $f$ does not halt on $k$, $g(k)=91753$. The viable options are endless.
(Of course, we can also choose $g(k)=f(k)+1$ if $f$ halts on $k$ and $g(k)=1$ if $f$ does not halt on $k$.)
How can we find a different number for each different Turing machine? The encoding number of a Turing machine!
Exercises
Exercises 1. Function $h$ defined below is not computable.
$$\text{For all }n\in\mathbb N,\ h(n)=\begin{cases}2^{f_n(n)} & \text { if both } f_{n}\text{ and }f_n(n) \text { are defined,} \\ 3 & \text { otherwise.}\end{cases}$$
Exercises 2. Any function $s$ that satisfies the condition below is not computable. Note that there is no requirement of $s(n)$ when $n$ is not a square number.
$$\text{For all }n\in\mathbb N,\ s(n^2)=\begin{cases}2f_n(n^2) & \text { if both } f_{n}\text{ and }f_n(n^2) \text { are defined,} \\3n + 14043571 & \text { otherwise.}\end{cases}$$
