2
$\begingroup$

In one of my lessons about turing machines I have been taught that the function g is not computable: \begin{cases}g(n)=f_{n}(n)+1 & \text { if } f_{n}(n) \text { is defined } \\ g(n)=1 & \text { if } f_{n}(n) \text { is undefined }\end{cases}

Proof:
If $g$ is computable, then it can be computed by some Turing machine. Assume it's encoding is $k$. $$ \begin{cases}g(k)=f_{k}(k)+1 & \text { if } f_{k}(k) \text { is defined } \\ g(k)=1 & \text { if } f_{k}(k) \text { is undefined }\end{cases} $$ but both are not equal to $f_{k}(k)$ so the function g can not be computable. My teacher also made some sort of table and talked about diagonalization, but I couldn't follow the proof at all. Could someone explain this proof to me in detail?

$\endgroup$

1 Answer 1

2
$\begingroup$

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}$$

$\endgroup$
7
  • $\begingroup$ Dear John, Thank you very much for this very well explained answer! I now understand almost every detail about it, but would still like to ask a few questions about it. 1) Why do we talk here about diagonalization? I still didn’t quite get that? 2) Could we also have used another definition of f_n, or is the only possible definition of it? 3) “ However, whatever value we let 𝑔(2022) be, there is a Turing machine that outputs 𝑔(2022) given 2022” and so on, can we easily prove this statement? $\endgroup$
    – Ronald
    Aug 21, 2022 at 12:27
  • $\begingroup$ And I think something went wrong with the rendering of the text concerning the second exercise? $\endgroup$
    – Ronald
    Aug 21, 2022 at 12:30
  • $\begingroup$ Please come here to chat with me. $\endgroup$
    – John L.
    Aug 21, 2022 at 15:05
  • $\begingroup$ thank you very much! :) $\endgroup$
    – Ronald
    Aug 22, 2022 at 8:07
  • $\begingroup$ Little question: what is actually meant by f_n(n) is undefined? So if the turing machine corresponding with the encode number n gets the input n, we do not know what the output will be? And if f_n is undefined then that means that the turing machine simply doesn’t exist? $\endgroup$
    – Ronald
    Sep 1, 2022 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.