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$.

Leave a comment