\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.