Notes - Models of Computation MT23, Decidability

Created: December 19, 2023
Updated: October 31, 2024

Flashcards

What does it mean for a Turing machine to be total (or a “decider”)?

It halts on all inputs.

What does it mean for a language to be decidable?

It is recognised by some total Turing machine.

Quickly justify that there are languages over $\Sigma$ that are not recursively enumerable.
  • There are countably many Turing machines
  • There are uncountably many languages over $\Sigma$, i.e. $\mathcal P(\Sigma)$

How do we convert decision problems, e.g.

Given a DFA $B$ and an input $w$, does $B$ accept $w$?

into a problem that can be handled by Turing machines? Do it for this example in particular.

Create languages where strings are encodings of what we want, e.g.

\[A_{\text{DFA}\\,} = \\{\langle B, w\rangle \mid B \text{ is a DFA that accepts input string }w\\}\]

What does the notation $\langle A \rangle$ where $A$ is some object of interest, e.g. a Turing machine?

The encoding of the object $A$ in our alphabet.

Describe whether the following problems individually are decidable, recursively enumerable but not decidable, or non-recursively enumerable:

  • $A _ {\text{DFA}\,}$
  • $E _ {\text{DFA}\,}$
  • $EQ _ {\text{DFA}\,}$
  • $A _ {\text{CFG}\,}$
  • $E _ {\text{CFG}\,}$
  • $EQ _ {\text{CFG}\,}$
  • $A _ {\text{TM}\,}$
  • $E _ {\text{TM}\,}$
  • $EQ _ {\text{TM}\,}$

Where $A _ {\text{blah}\,}$ denotes the acceptance problem, $E _ {\text{blah}\,}$ the emptiness problem and $EQ _ {\text{blah}\,}$ the equality problem.
  • $A _ {\text{DFA}\,}$: decidable
  • $E _ {\text{DFA}\,}$: decidable
  • $EQ _ {\text{DFA}\,}$: decidable
  • $A _ {\text{CFG}\,}$: decidable
  • $E _ {\text{CFG}\,}$: decidable
  • $EQ _ {\text{CFG}\,}$: not recursively enumerable (so in particular not decidable) (I am not 100% sure here)
  • $A _ {\text{TM}\,}$: recursively enumerable, not decidable
  • $E _ {\text{TM}\,}$: not recursively enumerable (so in particular not decidable)
  • $EQ _ {\text{TM}\,}$: not recursively enumerable, (so in particular not decidable)

Suppose $A$ and $B$ are DFAs. How can you convert an instance of the equality problem into an instance of the emptiness problem?

Construct $C = \left(A \cap \overline B\right) \cup \left(B \cap \overline A\right)$ and check if it’s empty.

What’s the basic idea behind showing that the emptiness problem for CFGs is decidable?

Mark all terminal symbols, then mark every variable which generates a marked symbols, and repeat until no new symbols are marked. Then if start symbol is marked, the CFG is not empty.

Quickly prove that $A _ {\text{TM}\,}$, the acceptance problem for Turing machines, is undecidable by assuming that there is a decider $H$

\[H(\langle M, w\rangle) = \begin{cases} \text{accept} &\text{if }M \text{ accepts } w \\\\ \text{reject} &\text{if }M \text{ does not accept } w \end{cases}\]

Draw a pretty picture at the same time showing that this is in fact a diagonalisation argument.

Construct $D$, which takes input $\langle M \rangle$ and:

  • Runs $H$ on $\langle M, \langle M \rangle \rangle$
  • Outputs the opposite of $H$
  • Run $D$ on input $\langle D \rangle$.

The pretty picture is two axis, one with “input string”, one with with “encoding of $\langle M \rangle$” and a diagonal line representing $H$’s output. Then note that $D$ outputs the opposite of the value on the diagonal, so putting $\langle D \rangle$ causes a problem.

What theorem lets you relate the decideability of a language $L$ to whether it is $\text{RE}$ or $\text{co-RE}$?
  • $L$ is decidable

if and only if

  • $L$ is $\text{RE}$
  • $L$ is $\text{co-RE}$

What’s the technique for showing that both the halting problem $HALT _ {\text{TM}\,}$ and the equality problem $EQ _ {\text{TM}\,}$ are undecidable?

Reduce them to the acceptance problem by showing that they could be used to determine whether a Turing machine accepts a given string.

What reductions do we use to prove that the language

\[\text{TOTAL} = \\{\langle M \rangle \mid M \text{ halts on all inputs}\\}\]

is neither $\text{RE}$ or $\text{co-RE}$? Justify why this is okay.

$\overline{\text{HALT} _ {\text{TM}\,}\,}$ is not $\text{RE}$. Hence it suffices to:

  • Reduce $\overline{\text{HALT} _ {\text{TM}\,}\,}$ to $\text{TOTAL}$, since this implies $\text{TOTAL}$ is not RE.
  • Reduce $\overline{\text{HALT} _ {\text{TM}\,}\,}$ to $\overline{\text{TOTAL}\,}$, since this implies $\overline{\text{TOTAL}\,}$ is not RE, which implies $\text{TOTAL}$ is not co-RE.

What’s is a common reduction used to show that some language $L$ is not $\text{RE}$?

Reducing $\overline{\text{HALT}\,}$ to $L$.

Can you justify why $\overline{\text{HALT}\,}$ is not $\text{RE}$?
  • $\text{HALT}$ is not decidable.
  • This implies $\text{HALT}$ is not $\text{RE}$ or $\text{HALT}$ is not $\text{co-RE}$ (using result that decidable $\text{RE}$ and $\text{co-RE}$).
  • But $\text{HALT}$ is $\text{RE}$, so it follows $\text{HALT}$ is not $\text{co-RE}$.
  • Then $\overline{\text{HALT}\,}$ is not $\text{RE}$.

Prove that $\overline{\text{HALT}\,}$ reduces to $\text{TOTAL}$, which is used in the proof that $\text{TOTAL}$ is neither $\text{RE}$ or $\text{co-RE}$ (since $\overline{\text{HALT}\,}$ is not $\text{RE}$, so $\text{TOTAL}$ is not $\text{RE}$ either).

Reminder:

  • $\overline{\text{HALT}\,}$ is the set of $\langle M, x \rangle$ such that $M$ does not halt on $x$.
  • $\text{TOTAL}$ is the set of $\langle M \rangle$ such that $M$ halts on all inputs.

Given $\langle M, x \rangle$, construct a new Turing machine $N _ {M, x}$ that does the following: On input $y$

  • Run $M$ on $x$ for $ \vert y \vert $ steps
  • If $M$ halts within $ \vert y \vert $ steps, loop endlessly
  • Otherwise accept

Then

  • $\langle M, x \rangle \in \overline{\text{HALT}\,}$ if and only if
  • $N _ {M, x}$ halts on all inputs, if and only if
  • $\langle N _ {M, x} \rangle \in \text{TOTAL}$

Quickly prove that $\overline{\text{HALT}\,}$ reduces to $\overline{\text{TOTAL}\,}$, which is used in the proof that $\text{TOTAL}$ is neither $\text{RE}$ or $\text{co-RE}$ (since $\overline{\text{HALT}\,}$ is not $\text{RE}$, so $\overline{\text{TOTAL}\,}$ is not $\text{RE}$, so $\text{TOTAL}$ is not $\text{co-RE}$).

Reminder:

  • $\overline{\text{HALT}\,}$ is the set of $\langle M, x \rangle$ such that $M$ does not halt on $x$.
  • $\overline{\text{TOTAL}\,}$ is the set of $\langle M \rangle$ such that $M$ does not halt on all inputs.

Given $\langle M, x \rangle$, construct a new Turing machine $N _ {M, x}$ that does the following: On input $y$

  • Ignore $y$
  • Run $M$ on $x$

Then

  • $\langle M, x \rangle \in \overline{\text{HALT}\,}$ if and only if
  • $N _ {M, x}$ does not halt on all inputs, if and only if
  • $\langle N _ {M, x} \rangle \in \overline{\text{TOTAL}\,}$

What is the idea of a Turing reduction for proving that a language $L$ is undecidable (or even not $\text{RE}$)?

Create an algorithm for a known undecidable problem using a decider for $L$ as a subroutine.

What is a computable function $f : A \to B$?

A function where there exists a total Turing machine such that on input $\langle a \rangle$, the Turing machine halts with just $\langle f(a) \rangle$ on the tape.

Suppose $A$ is a decision problem over $\Sigma _ A^\star$ and $B$ is a decision problem over $\Sigma _ B^\star$. What is a many-one reduction, and what notation is used to describe the relationship between $A$ and B?

A computable function $f : \Sigma^\star _ A \to \Sigma^\star _ B$ such that $\forall w \in \Sigma^\star _ A$,

\[w \in A \iff f(w) \in B\]

This means $A$ is mapping reducible to $B$, written

\[A \le_m B\]


Related posts