
{\bf 1. Complexity measures}

What is a reasonable complexity measure?  In class, we have discussed
time and space as two reasonable complexity measures, when using
Turing machines as our computational models.  In a 1967 JACM paper,
Manuel Blum considered this question and defined a {\em complexity
measure} $\Phi$ to be a function that maps Turing machine-input pairs
to nonnegative integers and is decidable.  Formally, $\Phi$ is a
complexity measure if $\Phi(M,x)$ is defined whenever $x$ is a valid
input to $M$ and it is decidable given $M$, $x$, and $k$, whether
$\Phi(M,x) = k$.  By this definition, which of these are complexity
measures?

\begin{itemize}
\item
Time, the number of steps during a computation.
\item
Space, the number of cells used on the worktape of a 2-tape Turing
machine (assuming that the first input tape is read-only).
\item
Reversals, the number of times during a computation that the head must
change direction of motion.
\item
Copy
\item
Ink
\end{itemize}

{\bf 2.} If there exists a fixed bound k on the length of the crossing
sequence, then language is regular. 

{\bf 3.} k-tape T(n) to 2-tape T(n)log(T(n)).

{\bf 4.} 
