\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}{11 February 2008}{8}

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

{\noindent {\bf Running times of Turing machines}}

In our definition of time complexity, we tend to ignore multiplicative
constants in the running times.  We do the same in simulation results
concerning Turing machines.  For instance, we saw that a $T(n)$-time
multi-tape Turing machine can be simulated by a single-tape Turing
machine in time $O(T(n)^2)$, if $T(n) \ge n$.  In these results, we
have used the asymptotic notation liberally to hide multiplicative
constants in the running time.  The following exercises somewhat this
practice when working with our models for the Turing machine and
running time.

Prove the following simulation results.
\begin{itemize}
\item[{\bf (a)}] For any constant $\eps > 0$, any single-tape Turing
machine running in time $T(n)$ can be simulated by a single-tape
Turing machine running in time $\eps T(n) + O(n^2)$.

\item[{\bf (b)}] For any constants $\eps > 0$ and $k > 1$, any $k$-tape Turing
machine running in time $T(n)$ can be simulated by a $k$-tape Turing
machine running in time $\eps T(n) + O(n)$.
\end{itemize}

({\em Hint:} Enlarge the state space for the simulating Turing machine
and simulate multiple steps at a time.)
\end{document}