\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newcommand{\halfnfa}{\mbox{{\sc Half-Paths-NFA}}}

\head{CSG714}{Theory of Computation}{Spring 2008}{4 February 2008}{6}

\begin{center}
\Large{\bf Problem of the Week -- 4}
\end{center}

{\noindent {\bf Turing machines that do not attempt to move head left
on the leftmost cell}}

Consider the problem of determining whether a given Turing machine $M$
on a given input $w$ ever attempts to move its head left when the head
is at the leftmost cell.

\begin{itemize}
\item[{\bf (a)}] Show that the above problem is undecidable.

\item[{\bf (b)}] In the proof of the undecidability of the Post
Correspondence Problem, we claimed that we can assume that the given
Turing Machine never attempts to move its head left when the head is
at the leftmost cell.  In particular, we claimed that we can always
alter the Turing machine, if necessary.  Reconcile this claim with
part (a); that is, argue why we can make such an assumption and why
does the assumption not contradict part (a).
\end{itemize}.
\end{document}