\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.
\paragraph {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.
{\bf An open question:} Do all exponential volume algorithms
(e.g., one solving Linear Chess) allow an equivalent {\em narrow} computation?}
\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}}}}\vspace{6pt}
{\bf Alternatively, 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 move counter limiting {\em the number of moves} to a polynomial.
The sec.~\ref{win} algorithm can be implemented in parallel P-time
for such games. Converse also holds, similarly to the Halting Game.
[Stockmeyer, Meyer 1973] solve compact games in P-space.
(With $M{\subset} \{0,1\}$ run depth-first search on the tree of all games --
sequences of moves. On exiting each node it is marked as the active player's
win if some move leads to a child so marked; else as his opponent's.
Children are then unmarked.) Conversely, compact games can simulate
any P-space algorithms. (Player A declares the result of the space-$k$,
time-$2^k$ computation. If he lies, player B asks him to declare the
memory state in the middle of that interval, and so by a k-step binary
search catches A's lie on a mismatch of states at two adjacent times.)
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.