\newpage\subsection {Reductions; Non-Deterministic and Alternating TM;
Time and Space.\label{gm-reduce}}

To {\em reduce} (see definition in sec.~\ref{rec}) Halting game to
Linear Chess we introduce a few concepts.

A {\em non-deterministic} Turing Machine (NTM) is a TM that sometimes
offers a (restricted) transition choice, made by a {\em driver}, a
function (of the TM configuration) of unrestricted complexity. A
deterministic (ordinary) TM $M$ accepts a string $x$ if $M(x)$ = yes; a
non-deterministic TM $M$ does if there exists a driver $d$ s.t.\
$M_d(x)=$ yes. NTM represent single player games, puzzles, e.g.\ Rubik's
Cube with a simple transition rule. We can compute the winning strategy
in exponential time (exhausting all positions).

Home Work: Is there a P-time winning strategy for every such game?
Nobody knows. Alternatively, show it requires exponential time. Grade A
for the course and, probably, a senior faculty position at the
university of your choice will be awarded for a solution.

The {\em alternating} TM (ATM) is a variation of the NTM driven by two
alternating drivers (players) $l$ and $r$. A string is accepted if there
is $l$ such that for any $r: M_{l,r}(x) =$ yes. Our games could be
viewed as ATM using a small space but up to an exponential time and
returning the result of the game. It prompts $l$ and $r$ alternatingly
to choose their moves (in several steps if the move is specified by
several bits) and computes the resulting position, until a winner
emerges. Accepted strings describe winning positions.

\paragraph {Linear Chess Simulation of TM-Game.}

We first simulate our Halting Game by {\em L-Chess}, a variant of Linear
Chess. It has the same board: \fbox {Weak {\tt|||||
\raisebox{1pt}[0pt][0pt] {\rule[-6pt]{3pt}{15pt}} |||||} Shy} and, like
regular chess, 6 ranks. Unlike Linear Chess, where only the vanquished
piece is replaced, in L-chess the winning piece may also be replaced by
(``promoted to'') a piece of the same side; the gender bit is set to the
side bit of the previous step, and an arbitrary table rather than the
simple ``Gender Rule'' determines the winning piece.

The simulation is achieved simply by representing the Halting Game as an
ATM computation simulated by the universal TM (using ``='' commands for
players' input). The UTM is viewed as an array of 1-pointer cellular
automata: Weak cells as rightward, Shy leftward. The TM head is set to
move upon termination to the end of the tape, so that no loser pieces
are left. To transform L-Chess to Linear Chess it is left (as an
exercise) to modify genders, extend ranks, and replace each transition
by several, so that the winning piece is determined by the Gender Rule
and is not replaced. So, any fast algorithm to solve Linear Chess, could
be used to solve any game. Since Halting Game requires exponential time,
so does the Linear Chess.

\subsubsection* {A Question Still Open: Space-Time Trade-off.}

{\em Deterministic} linear space computations are games where any
position has at most one (and easily computable) move. We know no
general superlinear lower bound or subexponential upper bound for time to
determine their outcome. This is the space-time trade-off problem. You
met with such trade-offs using techniques like dynamic programming:
saving time at the expense of space.

\noindent\parbox{296pt}{Recall that on a parallel machine: {\em time} is
the number of steps until the last processor halts; {\em space} is the
amount of memory used; {\em volume} is the combined number of steps of
all processors. ``{\em Small}'' will refer to values bounded by a
polynomial of the input length; ``{\em large}'' to exponential. Let us
call computations {\em narrow} if {\em either} time {\em or} space are
polynomial, and {\em compact} if both (and, thus, volume too) are.
Sec.~\ref{paral} reduces the computations with {\em large} time and {\em
small} space to (parallel) ones with {\em large} space and {\em small}
time, and vice versa.}\hspace{1pc} \parbox{157pt} {\vector(1,0){130}
space\\\mbox {\raisebox{75pt}
{\vector(0,-1){70}}\hspace{-9pt}\raisebox{-4pt} {time} \fbox
{\rule{0pt}{6pc}\parbox[b]{2pc}
{large\\time,\\small\\space}}\hspace{3pt} \raisebox{43pt}
{\parbox{106pt} {\fbox {\rule{0pt}{18pt}small time, large
space}\vspace{2pc} narrow computations}}}}

\paragraph{Can every {\em narrow} computation be converted into a compact one?}
This is equivalent to the existence of a P-time algorithm for solving
any {\em fast} game, i.e.\ a game with a P-time transition rule and a
counter decremented at each move, limiting {\em the number of moves} to
a polynomial. The sec.~\ref{win} algorithm can be implemented in
parallel P-time for such games. Conversely, any narrowly computable
predicate may be expressed as one determining the winning side of a fast
game (similar to the Halting Game). Thus, fast games (i.e. compact
alternating computations) correspond to narrow deterministic
computations; general games (i.e. narrow alternating computations)
correspond to large deterministic ones.

{\bf A Related Question:} Do all exponential volume algorithms (e.g.,
one solving Linear Chess) allow an equivalent {\em narrow} computation?
The two conjectures are mutually exclusive: otherwise we could solve the
exponential-time Bounded Halting Problem in polynomial volume.