Exercise 2

\[% Shared mathematical notation for CSC438. % % Keep this file limited to commands supported by both LaTeX and MathJax. % Quarto loads it through filters/shared-macros.lua; TeX preambles can use % \input{../macros} when compiled from a first-level project directory. \renewcommand{\subset}{\subseteq} \renewcommand{\iff}{\leftrightarrow} \newcommand{\N}{\mathbb{N}} \newcommand{\proves}{\vdash} \newcommand{\cA}{\mathcal{A}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cP}{\mathcal{P}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\TR}{\mathbf{TR}} \newcommand{\D}{\mathbf{D}} \newcommand{\R}{\mathbb{R}} \newcommand{\seq}{\Rightarrow} \newcommand{\RA}{\Longrightarrow} \newcommand{\LRA}{\Longleftrightarrow} \newcommand{\OI}{\{0,1\}} \renewcommand{\SS}{\Sigma^*} \newcommand{\powerset}{\mathcal{P}} \newcommand{\blank}{\sqcup} \newcommand{\angles}[1]{\left\langle #1\right\rangle} \newcommand{\enc}[1]{\left\ulcorner #1\right\urcorner} \newcommand{\Lang}{\mathcal{L}} \newcommand{\Th}{\operatorname{Th}} \newcommand{\Thm}{\operatorname{Thm}} \newcommand{\Prov}{\operatorname{Prov}} \newcommand{\Con}{\operatorname{Con}} \newcommand{\ATM}{A_{\mathrm{TM}}} \newcommand{\HALTTM}{\operatorname{HALT}_{\mathrm{TM}}} \newcommand{\HALTe}{\operatorname{HALT}_{\epsilon}} \newcommand{\AExp}{A_E} \newcommand{\AMult}{A_M} \newcommand{\green}[1]{\textcolor{green}{#1}} \newcommand{\red}[1]{\textcolor{red}{#1}} \newcommand{\st}[1]{\sout{#1}} \]

1 Defining Turing Machines

1.1

Complete the exercises here

Solution

Solutions Notebook

1.2

Reflection: How did it feel to write the Turing machines? Did it feel like programming? What similarities and differences did you notice?

2 TM Variants

Review the \(k\)-tape and nondeterministic variants of Turing machines in Section 3.2 of Sipser.

3 Enumerability and Recognizability

An enumerator is a Turing machine that prints strings one at a time. An enumerator \(E\) enumerates a set \(A\) if and only if every element of \(A\) is eventually printed by \(E\) and no element outside \(A\) is ever printed by \(E\). Note that \(E\) may print the strings in any order, and strings may be repeated.

Sets that have enumerators are called enumerable.

As an example, here is an enumerator for \(\{1^n : n \in \N\}\):

s = ""
while True:
    print(s)
    s += "1"

When \(E\) is an enumerator, we will sometimes use the following pseudocode:

for x in E:

This is simply a for loop in which \(x\) takes on the values printed by \(E\) one at a time.

3.1

Show that the following sets are enumerable by writing actual code that enumerates them.

• \(\N \times \N\)
• \(\Sigma^*\)

For example, the following Python code enumerates \(\N\).

i = 0
while True:
    print(i)
    i += 1

Provide a brief argument that all elements of the requested set are eventually printed by your program.

Solution

To enumerate \(\N \times \N\), enumerate pairs by the sum of their coordinates:

s = 0
while True:
    for i in range(s + 1):
        print(f"({i},{s-i})")
    s += 1

For any \((i,j) \in \N \times \N\), the enumerator prints \((i,j)\) when \(s=i+j\).

Suppose \(\Sigma\) is a finite alphabet. The following Python code enumerates \(\Sigma^*\) in standard string order:

def strings_n(n, c):
    if n == 0:
        print(c)
    else:
        for s in SIGMA:
            strings_n(n - 1, c + s)

n = 0
while True:
    strings_n(n, "")
    n += 1

Every string has some finite length \(n\), so every string is eventually printed.

3.2

Show that if \(A\) and \(B\) are enumerable, then so is \(A \times B = \{\angles{a, b} : a \in A, b \in B\}\).

Solution

Let \(E_A\) and \(E_B\) be enumerators for \(A\) and \(B\), respectively. Run them in parallel, storing all values that have appeared so far: Let \(G\) be an enumerator for \(\N \times \N\) as in the previous question.

for (m, n) in G:
    a_m = get the $m$th item from $E_A$.
    b_n = get the $n$th item from $E_B$.
    print(a_m, b_n)

Let \(a \in A\), and \(b \in B\). Then since \(E_A\) is an enumerator of \(A\), \(a\) eventually gets printed, let’s say it’s the \(m\)th string printed by \(E_A\). Similarly, \(b\) is the \(n\)th string printed by \(E_B\) for some \(n\).

Then since \(G\) is a enumerator for \(\N \times \N\), \((m, n)\) eventually gets printed by \(G\), and the program prints \((a, b)\).

3.3

Show that \(A\) is enumerable if and only if \(A\) is recognizable.

TipHint

For the backward direction, if a Turing machine accepts a string \(w\), it must do so within a finite number of steps!

Solution

Forward direction. Suppose \(A\) is enumerable, with enumerator \(E\). We show that \(A\) is recognizable. Define a Turing machine \(M\) as follows:

On input \(w\), run \(E\) and accept if \(E\) ever prints \(w\). If \(E\) halts without printing \(w\), reject.

If \(w \in A\), then \(E\) eventually prints \(w\), and \(M\) accepts \(w\). If \(w \notin A\), then \(E\) never prints \(w\), and \(M\) does not accept \(w\). Hence \(\cA(M) = A\), and \(A\) is recognizable.

Backward direction. Let \(M\) be a recognizer for \(A\). Following the hint, \(w \in A\) if and only if there exists a \(k \in \N\) such that \(M\) accepts \(w\) within \(k\) steps. Since \(\Sigma^*\) and \(\N\) are both enumerable, let \(G\) be an enumerator for \(\Sigma^* \times \N\), as constructed in the previous problem. Define an enumerator for \(A\) as follows:

E:
    for (w, k) in G:
        run a fresh copy of M on w for k steps
        if M accepts w within k steps:
            print(w)

Suppose \(w \in A\). Then there is some \(k\) for which \(M\) accepts \(w\) within \(k\) steps. Eventually, \(G\) prints \((w,k)\), and \(E\) prints \(w\). On the other hand, if \(w \notin A\), then the condition in the if statement is never true, so \(w\) is never printed. Hence, \(E\) enumerates exactly \(A\).

3.4

We earlier said a set \(A\) is countable if and only if there is a surjection from \(\N \to A\). We said such a surjection is an enumeration of \(A\). This is a slightly different definition of enumerability - in particular, we need a TM that prints all the elements of \(A\). By a counting argument, show that these two notions do not coincide.

Solution

There are countably many TMs, hence the number of subsets of \(\Sigma^*\) that are enumerable in the sense that there is a TM that prints the elements of the subsets is countable.

On the other hand, there are uncountably many subsets of \(\Sigma^*\), each of which is countable (and hence enumerable in the sense that there is a surjection from \(\N\))

4 Standard String Order Enumerability and Decidability

Recall that standard string order (SSO) is defined by first comparing strings by length and then comparing strings of equal length in dictionary order. That is, the first few strings in SSO over the alphabet \(\OI\) are

\[ \epsilon, 0, 1, 00, 01, 10, 11, 000, \ldots \]

4.1

Prove that \(A\) is decidable if and only if there exists an enumerator that enumerates the elements of \(A\) in standard string order.

Solution

Forward direction. Suppose \(A\) is decidable, and let \(M\) be a decider for \(A\). Define an enumerator \(E\) as follows:

E:
    for w in Sigma^*, in standard string order:
        run M on w
        if M accepts w:
            print(w)

Because \(M\) halts on every input, the enumerator eventually considers every string. It prints exactly the strings in \(A\), and it prints them in standard string order.

Backward direction. Suppose an enumerator \(E\) prints the elements of \(A\) in standard string order. We consider two cases.

If \(A\) is finite, then \(A\) is decidable: a decider can store all of its elements and accept exactly those strings.

If \(A\) is infinite, define a decider \(M\) as follows. On input \(w\), run \(E\) until it prints either \(w\) or a string that comes after \(w\) in standard string order. In the first case, accept; in the second case, reject. There are only finitely many strings at or before \(w\) in standard string order. Because \(A\) is infinite and \(E\) enumerates all of \(A\), \(E\) must eventually print a string that is at least as late as \(w\). Thus, \(M\) always halts. Since \(E\) prints strings in order, once it prints a string after \(w\), we know that it will never print \(w\). Therefore, \(M\) decides \(A\).