Exercise 4

Published

September 30, 2026

1 Flip

Consider the following function \(\text{flip}: \Sigma^* \to \Sigma^*\).

\(\text{flip}(x)\) is an encoding of a program that does the following:

On input \(w\):

  • Simulate \(M_x\) on \(w\).
  • If \(M_x\) accepts, reject.
  • If \(M_x\) rejects, accept.

That is, \(\text{flip}(x)\) simulates \(M_x\), and flips the result.

The fixed-point theorem says that there exists some \(e \in \Sigma^*\) such that \(M_e\) and \(M_{\text{flip}(e)}\) behave identically on all inputs.

1.1

How can this be?

Solution

A fixed point can be a string \(e\) that encodes a Turing machine that loops on every input. Since \(M_e\) loops on every input, so does \(M_{\text{flip}(e)}\).

2 Busy Beaver

Throughout this question, use deterministic single-tape Turing machines with input alphabet \(\Sigma = \{0,1\}\) and fixed tape alphabet \(\Gamma = \{0,1,\sqcup\}\), where \(\sqcup\) is the blank symbol. Count all states, including halting states, and use a fixed convention for the transition function. For each \(k\), there are only finitely many such machines up to renaming states.

Define the Busy Beaver function \(BB: \N \to \N\) as follows. \(BB(k)\) is the maximum number of steps taken by any halting TM with exactly \(k\) states when run on the empty input.

2.1

Show that \(BB\) is not computable.

Solution

Suppose, for a contradiction, that \(BB\) were computable. We could use it to decide \(\HALTe = \{\angles{M}: M \text{ halts on the empty input}\}\).

def h(M)
    k = num_states(M)
    t = BB(k)
    simulate M on the empty input for at most t steps
    accept if M has halted
    reject otherwise

The number of states is computable from the encoding of \(M\). If \(M\) halts on the empty input, it does so within \(BB(k)\) steps, so this procedure accepts. If \(M\) has not halted by then, the definition of \(BB(k)\) implies that it never halts, so the procedure correctly rejects. This would decide \(\HALTe\), a contradiction.

2.2

Show that \(BB\) has no computable upper bound. That is, any function \(f: \N \to \N\) satisfying \(BB(k) \leq f(k)\) for every \(k \in \N\) is not computable.

Solution

If such an \(f\) were computable, we could replace \(BB(k)\) with \(f(k)\) in the preceding procedure. Every halting \(k\)-state machine halts within \(BB(k) \leq f(k)\) steps, so this would again decide \(\HALTe\), a contradiction.

Define \(BB'(k)\) to be the maximum number of 1s left on the tape at the time of halting by any TM with exactly \(k\) states when run on the empty input, using the same fixed TM model. If there are no such machines, set \(BB'(k)=0\).

2.3

Show that \(BB'\) is also not computable.

Solution

Suppose, for a contradiction, that \(BB'\) were computable. We could then compute an upper bound on \(BB\) as follows.

For any TM \(M\), construct a TM \(M'\) that simulates \(M\) on the empty input and counts its steps. If \(M\) halts after \(t\) steps, \(M'\) finishes by leaving exactly \(t\) 1s on its tape and then halts. If \(M\) never halts, neither does \(M'\).

We can first describe this construction using two tapes, appending one 1 to a unary counter on the second tape for each simulated step. Then convert it to a single-tape TM.

def f(k):
    m = 0
    for each TM M with k states (using a fixed set of state names):
        construct M' and let N be its number of states
        m = max(m, BB'(N))
    return m

There are finitely many transition tables to enumerate, so \(f\) would be a computable function under our assumption that \(BB'\) is computable.

We claim that \(BB(k) \leq f(k)\) for every \(k\). Choose a halting \(k\)-state machine \(M\) that takes \(BB(k)\) steps on the empty input. Let \(S(M)\) be its running time, let \(O(M')\) be the number of 1s left on the tape when \(M'\) halts, and let \(N\) be the number of states of \(M'\). Then

\[ BB(k) = S(M) = O(M') \leq BB'(N) \leq f(k). \]

This contradicts the earlier result that \(BB\) has no computable upper bound. Therefore, \(BB'\) is not computable.

3 Infinite Subsets and Minimal Turing Machines

We know that \(\overline{\ATM}\) and \(\overline{\HALTTM}\) are not recognizable.

For each of these sets, find an infinite decidable subset.

3.1

Solution

Let \(M_{\bot}\) be a Turing machine that rejects every input. The set

\[ S_A = \{\angles{M_{\bot},w} : w \in \Sigma^*\} \]

is an infinite decidable subset of \(\overline{\ATM}\). A decider simply checks whether the first component is the fixed encoding of \(M_{\bot}\). Every pair is outside \(\ATM\) because \(M_{\bot}\) accepts no input, and \(S_A\) is infinite because \(\Sigma^*\) is infinite.

For \(\overline{\HALTTM}\), let \(M_{\infty}\) be a Turing machine that loops on every input. Then

\[ S_H = \{\angles{M_{\infty},w} : w \in \Sigma^*\} \]

is an infinite decidable subset of \(\overline{\HALTTM}\).

We will now construct a set for which every infinite subset is unrecognizable. We begin with some definitions.

Write \(y \prec x\) if \(y\) occurs before \(x\) in standard string order.

Two machines are behaviorally indistinguishable if they have the same observable behavior on every input: on each input, they both accept, both reject, or both loop. We write \(M \simeq N\) when \(M\) and \(N\) are behaviorally indistinguishable. They are distinguishable if their behavior differs on at least one input. For example, if \(x\) encodes a machine and we add unreachable states to obtain a later encoding \(x'\), then \(M_x \simeq M_{x'}\).

Define

\[ \operatorname{MIN}_{\mathrm{TM}} = \left\{ x \in \Sigma^* : \text{for every } y \prec x, M_y \not\simeq M_x \right\}. \]

Thus, \(\operatorname{MIN}_{\mathrm{TM}}\) contains the first string in standard string order that represents each possible Turing-machine behavior.

3.2

Prove that \(\operatorname{MIN}_{\mathrm{TM}}\) is not recognizable using self-reference.

First, show that \(\operatorname{MIN}_{\mathrm{TM}}\) is infinite.

Solution

We first show that \(\operatorname{MIN}_{\mathrm{TM}}\) is infinite. Let \(S_n=\{1^n\}\), and let \(M_n\) be a Turing machine that accepts \(1^n\) and rejects every other input. For \(m \neq n\), we have \(M_n \not\simeq M_m\) because they disagree on input \(1^n\). Hence, there are infinitely many distinguishable Turing-machine behaviors and therefore infinitely many strings in \(\operatorname{MIN}_{\mathrm{TM}}\).

For the sake of contradiction, assume that \(\operatorname{MIN}_{\mathrm{TM}}\) is recognizable. Then there is an enumerator \(E\) for \(\operatorname{MIN}_{\mathrm{TM}}\). Using self-reference, define the following machine \(C\):

C(x):
    c = get_source_code()
    for d in E:
        if c \prec d:
            simulate M_d on x
            return with the same outcome

Only finitely many strings occur at or before \(c\) in standard string order. Since \(\operatorname{MIN}_{\mathrm{TM}}\) is infinite, \(E\) eventually prints some \(d\) such that \(c \prec d\). The machine \(C=M_c\) then has exactly the same behavior as \(M_d\). This contradicts \(d \in \operatorname{MIN}_{\mathrm{TM}}\), because the earlier description \(c\) is behaviorally indistinguishable from \(d\). Therefore, \(\operatorname{MIN}_{\mathrm{TM}}\) is not recognizable.

3.3

Show that every infinite subset of \(\operatorname{MIN}_{\mathrm{TM}}\) is also unrecognizable.

Solution

Suppose, for the sake of contradiction, that an infinite set \(S \subseteq \operatorname{MIN}_{\mathrm{TM}}\) is recognizable, and let \(E_S\) be an enumerator for \(S\). Repeat the preceding self-referential construction, replacing \(E\) with \(E_S\).

Only finitely many strings occur at or before the constructed machine’s description \(c\). Because \(S\) is infinite, \(E_S\) eventually prints some \(d \in S\) with \(c \prec d\). The constructed machine \(M_c\) then simulates \(M_d\) on every input, so \(M_c \simeq M_d\). This contradicts \(d \in S \subseteq \operatorname{MIN}_{\mathrm{TM}}\). Therefore, no infinite subset of \(\operatorname{MIN}_{\mathrm{TM}}\) is recognizable.

4 is_formula and parser

Complete the exercises in this notebook.

Notice that your implementation of is_formula shows \(\cF\) is decidable.

5 Word Problems (for fun) (Enderton 1.2.{7, 12, 13})

5.1

You are at a fork in the road. There are two guards at the fork. One of them always tells the truth, and the other always tells falsehoods. You do not know which is which. You again have just one yes/no question to ask one of them in order to figure out which way it is to the capital. What do you ask?

Solution

Ask either guard: “Would the other guard say that the left road leads to the capital?”

If the answer is yes, take the right road; if the answer is no, take the left road.

The truthful guard accurately reports the liar’s false answer, while the liar reverses the truthful guard’s correct answer. In either case, the answer is the opposite of the truth about whether the left road leads to the capital.

5.2

You are in a land inhabited by people who either always tell the truth or always tell falsehoods. You come to a fork in the road and you need to know which fork leads to the capital. There is a local resident there, but he has time only to reply to one yes-or-no question. What one question should you ask so as to learn which fork to take? Suggestion: Make a table.

Solution

Ask: “If I asked you whether the left road leads to the capital, would you say yes?”

If the answer is yes, take the left road; if the answer is no, take the right road.

Left road leads to capital? Resident Answer to the direct question Answer to the question asked
Yes Truthful Yes Yes
No Truthful No No
Yes Liar No Yes
No Liar Yes No

The truthful resident answers both levels truthfully. The liar would lie to the direct question and then lies about that answer, so the two reversals cancel.

5.3

There are three suspects for a murder: Adams, Brown, and Clark. Adams says “I didn’t do it. The victim was an old acquaintance of Brown’s. But Clark hated him.” Brown states “I didn’t do it. I didn’t even know the guy. Besides I was out of town all that week.” Clark says “I didn’t do it. I saw both Adams and Brown downtown with the victim that day; one of them must have done it.” Assume that the two innocent men are telling the truth, but that the guilty man might not be. Who did it?

Solution

Brown did it. Adams says the victim was an acquaintance of Brown’s, while Brown says he did not know the victim. They cannot both be telling the truth, so at least one of Adams and Brown is guilty. Hence Clark is innocent and his statements are true.

Clark saw Brown downtown with the victim that day, contradicting Brown’s claim to have been out of town all week. Brown therefore cannot be innocent, so he is the guilty man. This is consistent with Adams and Clark telling the truth.

5.4

An advertisement for a tennis magazine states, “If I’m not playing tennis, I’m watching tennis. And if I’m not watching tennis, I’m reading about tennis.” We can assume that the speaker cannot do more than one of these activities at a time. What is the speaker doing? (Translate the given sentences into our formal language; consider the possible truth assignments.)

Solution

Let \(P,W,R\) mean that the speaker is playing tennis, watching tennis, and reading about tennis, respectively. The statements and the exclusivity assumption give

\[ (\neg P\to W)\land(\neg W\to R) \land\neg(P\land W)\land\neg(P\land R)\land\neg(W\land R). \]

If \(W\) were false, then \(\neg P\to W\) would force \(P\) to be true, and \(\neg W\to R\) would force \(R\) to be true. This contradicts the assumption that at most one activity occurs. Thus \(W\) is true, and exclusivity forces \(P=R=0\).

The assignment \((P,W,R)=(0,1,0)\) satisfies both implications. Therefore the speaker is watching tennis.