0
$\begingroup$

We defined the diagonal language as follows in the lecture: \begin{align*} L_{\text{diag}}=\left\{w \in \left\{0, 1\right\} ^{*}\mid w=w_{i} \text{ for some }i \in \mathbb{N} \text{ and }M_{i} \text{ does not accept }w_{i}\right\} .\end{align*} Here, $w_i$ is the $i$-th word in canonical order and $M_i$ is the $i$th Turing machine, canonically ordered by their encodings in binary. No I asked myself the question whether this language could be empty, e.g. if every $M_i$ would accept the word $w_i$. Could this happen, depending on how we define the encoding of a Turing machine?

$\endgroup$
10
$\begingroup$

Here is a simple direct proof that $L_{\text{diag}}$ is not empty.

Let $N$ be a Turing machine that does not accept any word. For example, a Turing machine that just loops forever. Suppose $N$ is encoded as the $j$-th machine. Then $L_{\text{diag}}$ contains the word $w_j$. Hence $L$ is not empty.

$\endgroup$
3
$\begingroup$

Since the diagonal language is not computable but the empty language is computable, that means that those languages are different.

$\endgroup$
3
  • $\begingroup$ I know this but somehow wanted to prove this in a different way than with this contradictory argument. But I think this is the most elegant way. Thanks for the quick answer! $\endgroup$
    – Max
    Nov 13 '21 at 12:50
  • $\begingroup$ Since the order for words and Turing Machine is a bit arbitrary, it is difficult to find an example of a word in $L_d$, so I don't know if there is some kind of "direct proof". $\endgroup$
    – Nathaniel
    Nov 13 '21 at 12:52
  • $\begingroup$ exactly, if you fix a representation of the Turing machines you could show it by a particular example, but in the general case this is not possible. $\endgroup$
    – Max
    Nov 13 '21 at 12:56
2
$\begingroup$

Others have already suggested the simplest and most elegant ways to prove that the diagonal language is not empty.

Indeed, we can proceed by contradiction, and argue that if the diagonal language were empty, it would be recursive, but we know it is not. Or, more constructively, if we take any TM that recognizes the empty language, then it does not accept any word including the word that encodes the TM, hence such word is in the diagonal language.

I only want to add that (arguably) more "satisfying" examples can be crafted, at the cost of additional complexity (and reduced elegance). One way to do so is to resort to the Rogers's fixed-point theorem. Briefly put, that theorem allows to craft TMs that internally have access to their own word-encoding . For instance, we can have a TM $M$ defined as follows:

On input $w$, proceed as follows. First, compute $w_M$ as the encoding of the TM $M$ (the one which we are executing right now). Then, compare $w$ to $w_M$ and accept if and only if they are different.

It is not obvious that such an $M$ exists, since its description above refers to itself, but Rogers's fixed-point theorem ensures that's the case, so we can pretend the one above is a valid definition for $M$.

By construction, $M$ accepts any word except for its own ($w_M$), so it clearly belongs to the diagonal language.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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