Class 24: Halting Problems

### Schedule

**Problem Set Omega** is due on **Sunday, 4 December** or
**Tuesday, 6 December** (see problem set for details). It is not like
the others, and counts as a “bonus” optional assignment.

The **final exam** is scheduled by the registrar for **Saturday, 10
December, 9am-noon** in our normal classroom. See the Final Exam
Preparation handout for more information on the final and
some **practice problems**.

## Links

Ali G on Science (possibly offensive, watch at your own risk!)

Numberphile on the Halting Problem (HT: John Fry)

## Turing Machine Definitions

$$
TM = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q*0 \in S, q*{Accept} \subseteq S)
$$

$S$ is a finite set (the “in-the-head” processing states)

$\Gamma$ is a finite set (symbols that can be written on the tape)

$\text{\em dir} = { \text{\bf Left}, \text{\bf Right}, \text{\bf Halt} }$ is the direction to move on the tape.

An *execution* of a Turing Machine, $TM = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q*0 \in S, q*{Accept} \subseteq S)$, is a (possibly infinite) sequence of **configurations**, $(x_0, x_1, \ldots)$ where $x_i \in \text{\em Tsil} \times S \times \text{\em List}$ (elements of the lists are in the finite set of symbols, $\Gamma$), such that:

- $x_0 = (\text{\bf null}, q_0, \text{\bf input})$
- and all transitions follow the rules (need to be specified in detail).

# Recognizing Languages

A Turing Machine, $M = (S, T \subseteq S \times \Gamma \rightarrow S
\times \Gamma \times \text{\em dir}, q*0 \in S, q*{Accept} \subseteq
S)$, **accepts** a string *x*, if there is an execution of *M* that
starts in configuration $(\text{\bf null}, q_0, x)$, and terminates in
a configuration, $(l, q_f, r)$, where $q*f \in q*{Accept}$.

A Turing Machine, $M = (S, T \subseteq S \times \Gamma \rightarrow S
\times \Gamma \times \text{\em dir}, q*0 \in S, q*{Accept} \subseteq
S)$, **recognizes** a language $\mathcal{L}$, if for all strings $s
\in \mathcal{L}$, $M$ accepts $s$, and there is no string $t \notin L$
such that $M$ accepts $t$.

A Turing Machine, $M = (S, T \subseteq S \times \Gamma \rightarrow S
\times \Gamma \times \text{\em dir}, q*0 \in S, q*{Accept} \subseteq
S)$, **decides** a language $\mathcal{L}$, if for all strings $s \in
\mathcal{L}$, $M$ accepts $s$, and for all strings $t \notin L$, $M$
*terminates* in a non-accepting state.

A language $\mathcal{L}$ is **Turing-recognizable** if there is some
Turing Machine that recognizes it. A language $\mathcal{L}$ is
**Turing-decidable** if there is some Turing Machine that decides it.

Are all Turing-decidable languages Turing-recognizable?

##

Are all Turing-recognizable languages Turing-decidable?

# Undecidable Languages

$$ \text{SelfRejecting} := { w \in \Sigma^{*} \, | \, w \notin \mathcal{L}(M(w)) } $$ where $M(w)$ is the Turing Machine described by string $w$ if $w$ describes a valid Turing Machine, otherwise, a $M(w)$ is a machine that rejects all inputs.

Is there a $M*{SR} = M(w*{SR})$ that recognizes the language $\text{SelfRejecting}$?

#

$$ A_{TM} = { (w, x) \, | \, M(w)\ \text{accepts on input}\ x } $$

Is the language $A_{TM}$ Turing-recognizable?

#

Is the language $A_{TM}$ Turing-decidable?

#

#

#

$$ Halts_{TM} = { (w, x) \, | \, M(w)\ \text{terminates on input}\ x } $$

#

```
def paradox():
if halts('paradox()'):
while True:
pass
```