chap3_TM3.tex

\input{header}

\AtBeginSubsection[]
{
	\begin{frame}<beamer>
		\frametitle{Outline}
		\tableofcontents[current,currentsubsection]
	\end{frame}
}

\begin{document}

\begin{frame}[allowframebreaks] \frametitle{Configuration of TM:}
  \begin{itemize}
  \item The current configuration means
    \begin{center}
    current state, tape contents, head location
\end{center}
\item $uqv$: $q$: current state

\item [] $uv$: current tape content

\item [] $u$: left, $v$: right

\item [] head: first of $v$

\end{itemize}\end{frame} \begin{frame}[allowframebreaks] \frametitle{Example of configuration}
  \begin{itemize}
\item $a,b,c \in \Gamma, u,v \in \Gamma^*$ (i.e., strings from
$\Gamma$)

\item [] $q_i, q_j$: states

\item if $\delta(q_i,b) =(q_j, c, L)$
  \begin{equation*}
uaq_i bv \mbox{ yields } uq_j a cv
  \end{equation*}
\item if $\delta(q_i,b) = (q_j, c, R)$
  \begin{equation*}
    uaq_i bv \mbox{ yields } uacq_j v
  \end{equation*}
\end{itemize}\end{frame} \begin{frame}[allowframebreaks] \frametitle{More about Configurations}
  \begin{itemize}
\item start configuration: $q_0 w$
\item accepting configuration: $q_{accept}$

\item rejecting configuration: $q_{reject}$
\item A TM accepts $w$ if configurations 
$c_1 \cdots c_k$
\begin{enumerate}
\item $c_1$: start configuration
\item $c_i$ yields $c_{i+1}$
\item $c_k$ accepting configuration
\end{enumerate}
\item Language: $L(M)$: strings accepted by $M$

\end{itemize}\end{frame}


\begin{frame}[allowframebreaks] \frametitle{Turing-recognizable}
  \begin{itemize}
\item A language is Turing-recognizable if it is recognized by a TM
\item For a Turing machine, there are three possible outcomes
  \begin{center}
accept, reject, loop
\end{center}
\item If an input fails: reject or loop

\item [] This is difficult to decide
\item We prefer a TM that never loops

\item [] Deciders: only accept or reject
\item A language is Turing-decidable if some TM decides it
\item In Chapter 4 we will discuss decidable languages
  
\end{itemize}\end{frame} \begin{frame}[allowframebreaks] \frametitle{Example 3.9}
  \begin{itemize}
  \item Consider the following language
    \begin{equation*}
    \{w\# w\mid w\in \{0,1\}^*\}
  \end{equation*}

\item Fig 3.10  
 
\end{itemize}

\begin{tikzpicture}
\node[state,initial left] (q_1) {$q_1$};
\node[state] (q_2) [below left of=q_1,yshift=0.7cm,xshift=-2.5cm] {$q_2$};
\node[state] (q_8) [below of=q_1,yshift=1cm] {$q_8$};
\node[state] (q_3) [below right of=q_1,yshift=0.7cm,xshift=2.5cm] {$q_3$};
\node[state] (q_4) [below of=q_2,yshift=1.2cm] {$q_4$};
\node[state] (q_a) [below of=q_8,yshift=1.2cm] {$q_a$};
\node[state] (q_5) [below of=q_3,yshift=1.2cm] {$q_5$};
\node[state] (q_6) [below of=q_a,yshift=1.3cm] {$q_6$};
\node[state] (q_7) [left of=q_6,xshift=0cm] {$q_7$};
 \path 
 (q_1) edge[above]  node {$0 \rightarrow$ x, R} (q_2)
 (q_1) edge[right]  node {$\# \rightarrow$ R} (q_8)
 (q_1) edge[above]  node {$1 \rightarrow$ x, R} (q_3) 
 (q_2) edge[loop above]  node {0,1 $ \rightarrow $ R} (q_2)
 (q_2) edge[right]  node {$\# \rightarrow$ R} (q_4)  
 (q_8) edge[loop right]  node {x $ \rightarrow $ R} (q_8)
 (q_8) edge[right]  node { $\sqcup \rightarrow $ R} (q_a)
 (q_3) edge[loop above]  node {0,1 $ \rightarrow $ R} (q_3)
 (q_3) edge[left]  node {$\# \rightarrow$ R} (q_5)
 (q_4) edge[loop below]  node {x $\rightarrow$ R} (q_4)
 (q_4) edge[above]  node {0 $\rightarrow$ x, L} (q_6)
 (q_5) edge[loop below]  node {x $\rightarrow$ R} (q_5)
 (q_5) edge[above]  node {1 $\rightarrow$ x, L} (q_6)
 (q_6) edge[loop right]  node {0, 1,  x $\rightarrow$ L} (q_6)
 (q_6) edge[below]  node {$\# \rightarrow$ L} (q_7)
 (q_7) edge[loop left]  node {0, 1 $\rightarrow$ L} (q_7)
 (q_7) edge[bend right=15, left]  node {x $\rightarrow$ R} (q_1)    
;
\end{tikzpicture}

\begin{itemize}
\item Links to $q_r$ are not shown
\item Simulate $01\#01$

\begin{center}
\begin{tabular}{llll}
  $q_1 0 1 \# 01$ & $x q_2 1 \# 01$ & $x1 q_2 \# 01$ & $x1\# q_4 01$
  \\
  $x1 q_6 \# x 1$ & $x q_7 1 \# x 1$ & $ q_7 x 1 \# x 1$ & $x q_1 1 \# x 1$
  \\
  $xx q_3 \# x 1$ & $xx \# q_5 x 1$ & $xx \# x q_5 1$ & $xx \# q_6 xx$ \\
  $xx q_6 \# xx$ & $x q_7 x \# xx$ & $xx q_1 \# xx$ & $xx \# q_8 xx$ \\
 $xx \# xx q_8 \sqcup$ &  $xx \# xx \sqcup q_a$ &&
\end{tabular}
\end{center}
\item Idea of the diagram:
  \begin{equation*}
    q_1 \rightarrow q_2 \rightarrow q_4 \rightarrow q_6
  \end{equation*}
  check 0 at the same position of the two strings
  \begin{equation*}
    q_1 \rightarrow q_3 \rightarrow q_5 \rightarrow q_6    
  \end{equation*}
  check 1
at the same position of the two strings
\item $q_6$: move left to the beginning of the second string
\item $q_7$: move left by
  \begin{equation*}
    q_7 \xrightarrow{0, 1 \rightarrow L} q_7
  \end{equation*}
until finding the first 0, 1 not handled yet:
\begin{equation*}
  q_7 \xrightarrow{x \rightarrow R} q_1
\end{equation*}
\item Thus $q_6$ and $q_7$ cannot be combined. At $q_6$,
  \begin{equation*}
    x \rightarrow L
  \end{equation*}
but at $q_7$
\begin{equation*}
  x \rightarrow R
\end{equation*}
\end{itemize}

\end{frame}

\begin{frame}[allowframebreaks] \frametitle{Example 3.11}
  \begin{itemize}
\item $C=\{a^i b^j c^k\mid i\times j=k, i,j,k \geq 1\}$
\item Procedure
  \begin{enumerate}
  \item check if the input is $a^+ b^+ c^+$
  \item back to start
  \item fix $a$, for each $b$, cancel $c$
  \item store $b$ back, cancel one $a$, go to step 3
  \end{enumerate}
\item Too complicated to draw state diagram
\item But one may wonder if TM can really do the above procedure
\item Here are more details
\item Step 1 can be done by a DFA (as DFA is a special case of TM)
\item Step 2 can be done by using a special symbol in the beginning
\item Step 3 is similar to the procedure of handling $w\#w$
\item [] Now we see the concept of subroutines
\end{itemize}\end{frame} \begin{frame}[allowframebreaks] \frametitle{Example 3.12}
  \begin{itemize}
\item $E=\{\#x_1\# x_2 \cdots \# x_l\mid x_i \in 
\{0,1\}^*, x_i \neq x_j\}$
\item Idea: sequentially compare every pair

  \begin{equation*}
    \begin{split}
& x_1 x_2, x_1 x_3, \ldots, x_1 x_l \\
& x_2 x_3, \ldots, x_2 x_l \\
& x_{l-1} x_l
\end{split}
\end{equation*}
\item This description is rough. Let's check more details

\item [] For $x_i, x_j$ mark \#'s of both strings
by $\dot{\#}$

\item [] $\dot{\#}x_1\#x_2 \dot{\#}x_3$: $x_1$ and $x_3$
being compared
\item Compare $x_i$ and $x_j$:

\item [] Can use a TM similar to that for $w \# w$

\item We can copy $x_i, x_j$ to the end
  and do the comparison there
  
% $\dot{\#}x_1\dot{\#}x_2 \# x_3 \hat{\#}x_1
% \hat{\#}x_2$

% $\dot{\#}x\ldots x\dot{\#}x\ldots x \ldots  \# x_3 \hat{\#}x_1
% \hat{\#}x_2$


% Copy $x_1,x_2$ back

% remove $\hat{\#}x_1
% \hat{\#}x_2$

\end{itemize}\end{frame}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: