# Course 2 : Beavers, Multi-Tapes Machines, I/O Machines, Recursive/Recursively enumerable languages

- [Closures](#closures) - [Variants of TM](#variants-of-tm)
- [Beavers](#beavers)
- [Multi-Tapes Machines](#multi-tapes-machines)
- [I/O Machines](#io-machines)

• Recursively enumerable language $L$ : iff there exists a TM such that ${\cal L}(M) = L$
${\cal L}(M) ≝ \{w \text{ such that the computation of M on w stops in "accept"}\}$
• Recursive langage : a recursively enumerable language such that $M$ halts on every word $w$.

Theorem : There are non-recursively enumerable languages.

Proof :

1. The set of recursively enumerable langu. is countable

2. $\{w_i \vert i ∈ ℕ\} = 𝛴^* \\ \{M_i \vert i ∈ ℕ\} = \text{set of TM}$
$M_0$ $M_1$ $M_2 ….$
$w_0$
$w_1$
$w_2$

$L ≝ {w_i \vert w_i \not∈ {\cal L}(M_i) }$

ABS : By Contradiction : if $L$ is recursively en., then $∃ j ; L = {\cal L}(M_j)$

• if $w_j ∈ L(M_j) ⟹ w_j \not∈ L = {\cal L}(M_j)$
• if $w_j \not ∈ L(M_j) ⟹ w_j ∈ L = {\cal L}(M_j)$

Co-recursively enumerable : $𝛴^*\backslash L$ is r.en.

### Closures

Proposition : $f: (𝛴\backslash {B,$})^* ⟶ (𝛴\backslash {B, $})^*$ computable.

1. If $g$ is computable, then $g \circ f$ is computable
2. If $L$ is recursive, then $f^{-1}(L)$ is recursive
3. If $L$ is r.e, then $f^{-1}(L)$ is r.e

Proof : 1. $M_f, M_g$ : Design $M_{g\circ f}$

• $M_f ≝ (Q_f, q_0^f, 𝛴’, 𝛿_f)$
• $M_g ≝ (Q_g, q_0^g, 𝛴’, 𝛿_g)$

⟹ NB: if we’re in $(w_1, accept\vert \vert reject, w_2)$ after $f$

• $Q_{g\circ f} = Q_g \bigoplus Q_f \sqcup {q_t}$
• $q_0^{g\circ f} = q_0^f$
• $𝛿_{g \circ f} = 𝛿_f[accept\vert \vert reject \mapsto q_t] \sqcup \begin{cases} q_t, 𝛼 \vdash q_t, 𝛼, ⟵ (a \neq \) \\ q_t, \ \vdash q_0^g, \, \downarrow \end{cases} \sqcup 𝛿_g$

if $(𝜀, q_0,$w) \vdash^*{M{g\circ f}} ($w_1, q_t, w_2)$ then $w_1 w_2 = f(w)$

1. $f^{-1}(L) ≝ {w \vert f(w) ∈ L}$ $M_{f^{-1}(L)} \text{ , given } M_f, M_L$

Lemma : $𝜒_L ≝ 1_L$ is computable iff $L$ is recursive

Then : apply the previous point to $𝜒_L \circ f$

1. Same construction. $M_{𝜒_L \circ f} : (𝜀, q_0, \w) \vdash^*_{M_{𝜒_L \circ f}} (\w, q_t, w_2) ⟺ w_1 w_2 = f(w)$

Then : $(𝜀, q_0^L, f(w)) \vdash^*_{M_{𝜒_L \circ f}} 𝛾$ $w ∈ {\cal L}(M_{𝜒_L \circ f}) ⟺ f(w) ∈ L ⟺ \vdash^*_{M_{𝜒_L}} 𝛾$

## Variants of TM

### Beavers

Theorem : for every TM $M$, we can construct a TM $M’$ with only 2 states s.t ${\cal L}(M’) = {\cal L}(M)$

idem : for alphabet : but not both simplifications at the same time.

Heuristics :

• Write the states on the tape ?

$M : a_1 ⋯ a_n, q, b_1 ⋯ b_n$

$M’ : a_1 ⋯ a_n, Q_0 \vert \vert Q_1 , q, b_1 ⋯ b_n$ ⟶ would it work ? NO because we can’t remember that we have read $q$ (even if there’s a gap filler between $q$ and $b_1$)

• Other idea :

$M’ : a_1 ⋯ a_n, Q_0 \vert \vert Q_1 , (b_1, q) ⋯ (b_n, )$

• Real idea : We move the state bit by bit : lots of supplementary transitions.

### Multi-Tapes Machines

We’re enabled to use multi-tapes whenever needed.

$M ≝ (Q, q_0, 𝛴, \, B, 𝛿)$

Main difference : $𝛿$

cf. drawing

$𝛿 : Q \times 𝛴^k ⟶ Q \times 𝛴^k \times \{⟶, \downarrow, ⟵\}$

Configuration :

$q, (w_1, v_1), ⋯, (w_k, v_k)$

let $a_i = first(v_i)$

$q, (w_1, v_1), ⋯, (w_k, v_k) \vdash q’, (w’_1, v’_1), ⋯, (w’_k, v’_k)$

if $∀i ∈ {1, ⋯, k}$ :

$(q, w_i, v_i) \vdash_i q’, (w’_i, v’_i)$

• Example : Addition of two nbs in base 2 :

NB : not very interesting because automata could do it (so no need for TM memory) $w_1, w_2 ∈ {0,1}^*$

\begin{cases} $w_1 \$ w_1 \

$\end{cases} ⟶ \begin{cases}$ w_1 \

$w_1 \$ (w_1 + w_2) \end{cases}

### I/O Machines

3 tapes Machines

• 1st tape : “read only”
• 3rd tape : “write only”
• 2nd one : whatever you want (to have the computation power of a TM)

What’s the point ? ⟶ Measuring complexity

• Computation time of $M$ on $w$ : nb of transitions of M on $w$
• $M$ computes in time $f(n)$ if $f(n) = max_{\vert w\vert =n} \text{comp. time of M on w}$

• $L$ has time complexity $O(f(n))$ if $∃$ machine $M$ computing in time $f(n)$ that accepts $L$.

• Comp. space of $M$ on $w$ : maximal size of the second tape (non blank) along the comp. of $M$ on $($w, $,$)$• Space complexity of$M$is $f(n) = max_{\vert w\vert =n} \text{space comp. time of the computation of M on w}$ Ex: Addition of two nbs in base 2 : space complexity ? 1st$$n_1 # n_2$
2nd
3rd

NB: in CS : streaming need short space, but time not so important.

2nd tape : we’ve got to store the localization of the pointer (which is on the 1st tape) ⟶ logarithmic space.

Theorem : $M$ is a $k$-tape TM computing $f$ in time $g(n) \geq n$, then there’s a single tape machine $M’$ computing $f$ in time $O(g(n)^2)$

NB: $O(g(n)^2)$ is not optimal !

Sketch of proof :

Configuration of multi-tape machine : $(w_1, v_1), ⋯, (w_n, v_n)$

$\downarrow$

$q \hspace{2em} w_1#v_1 D w2 # v_2 ⋯ D w_n # v_n D F$

1. Add blanks $B$ : $q \hspace{2em} w_1\#v_1 BD w2 \# v_2 ⋯ BD w_n \# v_n BD F$
2. Collect the first letter of $(v_1, B)$ ⋯ first letter $(v_n, B)$

⟶ $[q, (a_1, ⋯, a_n)]$

1. $[q’, (d_1, ⋯, d_n), (b_1, ⋯, b_n)]$ if $𝛿_M(q, a_1 ⋯ a_n) = (q’, (d_1, ⋯, d_n), (b_1, ⋯, b_n))$

2. Update all the tapes : For instance : $[q', (⟶, d_{i+1}, ⋯, d_n), (b_i, ⋯, b_n)]$ with $#$ : $# 𝛼 ⟹ b_i #$

Next time :

• Universal TM
• How to prove indecidability ⟶ reductions

1. $q, (w_1, x_1), ⋯, (w_k, x_k) \vdash q', (w'_1, x'_1), ⋯, (w'_k, x'_k)$ config de $M$

2. Chercher une “invariance”.

⟶ $[q, ⋯], (𝜀,$w_1#x_1D⋯w_k#x_kDF)$1. Pour s’assurer que les$x_i$sont non vides : Se faire de la place, en rejoutant un blanc$B$avant chaque$D$: repousser les “D”, pour pouvoir écrire à droite de$x_i$(en actualisant un petit buffer de$k$symboles au plus (on ajoute au plus$k$blancs)) ⟶$[q, ⋯], (𝜀, $w_1#x_1B^D⋯w_k#x_k B^DF)$

Comment gérer le buffer ? : c’est une file d’attente de longeur $\leq k$

Puis : quand on arrive à $F$, on vide le buffer.

**Complexité en temps ** : $C = \sum_n nk$ (à chaque étape, on rajoute k blancs)

1. On récupère les premières lettres des $x_i ≝ a_i y_i$ : on collecte les $a_1, ⋯, a_k$

2. Simulation de la transition : on passe dans $[q’,(a’_1, a’_k), (d_1, ⋯, d_k)]$ (où les $d_i$ sont les déplacements à effectuer)

Ex :

$a’_i, d_i = ←$

⟹ $⋯ c_i # a_i$ → $⋯ # c_i a’_i$

MAIS : Pour faire ça, on doit mémoriser $c_i$ temporairement ! ⟶ à ajouter dans l’état de contrôle.

• En plus, Dans l’état de contrôle : on ajoute un nombre pour mémoriser le numéro de l’étape courante.

Idée générale : à chaque qu’on manque d’une information (qui appartient à un ensemble fini), on l’ajoute dans l’“état de contrôle”.

NB : Si la MT est à un nombre variable de rubans, on a un problème avec cette solution : le buffer ne doit plus être de taille fixe.

Théorème : Un langage $L$ est récursif ssi il est récursivement énumérable et co-récursivement énumérable.

Rappel :

• Récursif : il existe un MT qui s’arrête sur toute donnée tq $w∈L$ ssi M accepte $w$.

• Récursivement énumérable : il existe un MT tq $w∈L$ ssi M accepte $w$.

• Co-récursivement énumérable : $L^c$ est réc. én.

Dém :

⟹ :

Récursif ⟹ Réc. én + L’ensemble des langages récursifs est clos par passage au complémentaire.

⟸ :

$M_1$ accepte $L$

$M_2$ accepte $L^c$

On considère une machine $M$ à deux rubans

• on copie la donnée sur le ruban 2
• on simule en “parallèle” $M_1$ sur le ruban 1, $M_2$ sur le ruban 2.
• Puis : si $M_1$ accepte, $M$ accepte / si $M_2$ accepte, $M$ rejette.

Ok, car : $∀ x ∈ 𝛴^*$ : $M_1$ OU $M_2$ s’arrête en acceptant $x$.

Tags:

Updated: