Turing Machine Definitions

$$ TM = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q0 \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}, q0 \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}, q0 \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 $qf \in q{Accept}$.

A Turing Machine, $M = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q0 \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}, q0 \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