Lab Session #7 #

Agenda #

• Turing Machine
  • Formal definition
  • Example
  • Exercices

Turing Machine #

Formal definition #

A Turing Machine (TM) with k-tapes is a tuple

where:

• \(Q\) is a finite set of states;

• \(I\) is the input language;

• \(Γ\) is the memory alphabet;

• \(δ\) is the transition function;

• \(q_0 \in Q\) is the initial state;

• \(Z_0 \in Γ\) is the initial memory symbol;

• \(F \subseteq Q\) is the set of final states.

Transition Function #

The transition function is defined as

where elements of \(\{R, L, S\}\) indicate “directions” of the head of the TM:

• \(R\) : move the head one position to the right;

• \(L\) : move the head one position to the left;

• \(S\) : stand still.

Remarks:

• the transition function can be partial;

• the transition function can be partial;

• the transition function can be partial;

Moves #

Moves are based on

• one symbol read from the input tape,

• k symbols, one for each memory tape,

• state of the control device.

Actions

• Change state.

• Write a symbol replacing the one read on each memory tape.

• Move the \(k+1\) heads.

Moves: Graphically #

• \(q \in Q − F\) and \(q′ \in Q\)

• \(i\) is the input symbol,

• \(A_j\) is the symbol read from the \(jth\) memory tape,

• \(A′_j\) is the symbol replacing \(A_j\) ,

• \(M_0\) is the direction of the head of the input tape,

• \(M_j\) is the direction of the head of the \(jth\) memory tape.where \(1 \leq j \leq k\)

Configuration #

A configuration (a snapshot) \(c\) of a TM with \(k\) memory tapes is the following \((k+2)\) -tuple:

where:

• \(q \in Q\)
• \(x \in (I \cup \{\_\})^∗, y = y'.\_\) with \(y' \in I^∗\)
• \(α_r \in (Γ \cup \{\_\})^∗\) and \( β'_r = β'_r.\_\) with \(β'_r \in Γ^∗\) and \(1 \leq r \leq k\)
• \(\uparrow \notin I \cup Γ\)

Acceptance Condition #

If \(T = ⟨Q, I, Γ, δ, q_0, Z_0, F⟩\) is a TM and \(s \in I^∗, s\) is accepted by \(T\) if \(c_0⊢∗c_F\)

where:

1. \(c_0\) is an initial configuration defined as \(c_0 = ⟨q_0, ↑s, ↑Z_0, . . . , ↑Z_0⟩ \) where

   • \(x = ϵ\)
   • \(y = s_\_\)
   • \(α_r = ϵ, β_r = Z_0\) , for any \(1 \leq r \leq k.\)

2. \(c_F\) is a final configuration defined as \(c_F = ⟨q,s′↑y, α_1↑β_1, . . . , α_k ↑β_k ⟩\) where

   • \(q \in F\)
   • \(x = s^′\)

\(L(T) = \{s \in I∗| x\) is accepted by \(T\} \)

Example #

A TM \(T\) that recognises the language \(A^nB^nC^n=\{a^nb^nc^n | n > 0\}\)

Exercices #

Build TMs that recognise the following languages:

• \(L_1 = \{wcw | w \in \{a, b\}^+\} \)
• \(L_2 = \{wcw^R | w \in \{a, b\}^+\} \) , where \(w^R\) is the reversed string \(w\) .
• \(L_3 = \{w | w \in \{a, b\}^∗\} \) , where \(w\) is a palindrome.
• \(L_4 = \{a^nb^n | n \ge 0\} \cup \{a^nb^{2n} | n \ge 0\}\)

Solutions:

Homework Exercices #

Build TMs that recognise the following languages:

• \(L_5 = \{(ab)^n, n \ge 0\}\)
• \(L_6 = \{a^nb^{2n}c{3n}, n \ge 0\}\)