% This work is licensed under the Creative Commons Attribution 3.0 Unported License.
% To view a copy of this license, visit http://creativecommons.org/licenses/by/3.0/
% or send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco,
% California, 94105, USA.
%
% Author: Alejandro Diaz-Caro
% Date: October 2010
\documentclass[12pt,a4paper]{article}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage[top=1.5cm,right=1.5cm,bottom=1.5cm,left=1.5cm]{geometry}
\usepackage{vaucanson-g}
\makeindex
\title{Exercise sheet 2: Turing machines}
\author{Alejandro D\'iaz-Caro}
\date{2010}
\begin{document}
\begin{center}
\textbf{\begin{large}Exercise sheet 2: Turing machines\end{large}}
\end{center}
\begin{enumerate}
\item\label{ex01} Write out the configurations the machine in example 7 goes through when started with input strings $11101$ and $11110$.
\item\label{ex02} Write out the configurations the machine in example 10 goes through when started with input strings $11101$ and $1011$.
\item\label{ex03} Is the function $f(n)=n+(n-1)$ Turing-computable? Justify your answer.
\item\label{ex04} Define Turing machines such that
\begin{enumerate}
\item Erase all the symbols appearing over the tape. The initial configuration is several successions of $0$'s and $1$'s separated each other by one $\square$. The alphabet of the tape is $\{0,1,\square\}$.
\item Leave the tape in blank if the number of $|$ is even and halts leaving only one $|$ if that number is odd. The initial configuration will be one succession of $|$ and the r/w head will be over the first one at left.
\item Have an alphabet $\{0,1,|,\square\}$ and do not stop in any case.
\item When the tape contains only one succession of $|$, then the machine halts after duplicate it. The initial configuration will be an arbitrary number of successions of $|$ separated each other by exactly one $\square$.
\item Have a tape alphabet $\{0, 1,\triangle\}$ and when it is given a string in $\{0, 1\}^∗$ as input, it replaces all $0$'s on the tape with $1$'s, otherwise leaves the input unchanged.
\item Accepts the regular language $L=\{w\in\{a,b\}^*~|~w$ contains equal number of $a$'s and $b$'s$\}$. Please notice, $a$'s and $b$'s can appear in any order. E.g. $abab$ and $bbaaba$ belong to the language. The input is only one word.
\item Accepts the language $L=\{ww^R~|~w\in\{a,b\}^*\}$ where $w^R$ is the string $w$ inverted.
\item Transforms the string $w$ into the string $ww^R$ ($w\in\{a,b\}^*$).
\end{enumerate}
\item\label{ex05} Give a high-level definition of a TM that recognizes the set $\{a^n b^{2n} : n \geq 0\}$.
\item\label{ex06} In the following exercises, the tape will contain an arbitrary number of successions of $|$, separated each other by exactly one $\square$. The r/w head starts at the left of the first $|$ (over a $\square$). Define TM over the alphabet $\{\square,|\}$ such that
\begin{enumerate}
\item Erase the first sequence of $|$ and halts at left of the following.
\item Erase the last sequence of $|$ and halts at the initial position.
\item Adds a $|$ to the right of the first sequence, maintaining a separation of one $\square$ with the following. The TM must halt at the left of the first sequence.
\item Adds a $|$ to the right of the first sequence and halts at the starting position.
\item Adds a new sequence, composed by only one $|$, at the left of the first one. The TM must halt at the left of the new sequence.
\item Adds a new sequence, composed by only one $|$, at the right of the last sequence. The TM must halt at the starting position.
\item Halts at the starting position of the size of the first sequence is the same as the size of the last one. Otherwise, it must halt at the left of the last sequence.
\end{enumerate}
\end{enumerate}
\end{document}