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\}$