(CoL)
Section 4
Interactive
machines
4.1
Interactive computability
In
traditional
game-semantical approaches, including
those of Lorenzen [Lor61],
Hintikka [Hin73],
Blass [Bla92], Abramsky [Abr94]
and
others, players’ strategies are understood as functions
--- typically as functions from interaction histories
(positions) to moves, or sometimes as functions that only look at the
latest
move of the history. This strategies-as-functions
approach, however, is generally inapplicable in the context of CoL,
whose
relaxed semantics, in striving to get rid of
“bureaucratic pollutants” and only deal with the remaining
true essence
of games, does not
impose any
regulations on which player can or should move in a given situation.
Here, in
many cases, either player may have (legal) moves, and then it is
unclear
whether the next move should be the one prescribed by 
’s strategy
function
or the one prescribed by the strategy function of 
. The
advantages of
CoL’s approach become especially appreciable when one tries to bring
complexity
theory into interactive computation: hardly (m)any really meaningful
and
interesting complexity-theoretic concepts can be defined for games
(particularly, games that may last long) with the
strategies-as-functions
approach.
In
CoL, ( ’s effective)
strategies are defined in terms of interactive machines, where
computation is
one continuous process interspersed with --- and influenced by ---
multiple
“input” (Environment’s moves) and “output” (Machine's moves) events. Of
several, seemingly rather different yet equivalent, machine models of
interactive computation studied in CoL, we will only discuss the most
basic, HPM (“Hard-Play
Machine”)
model.
An
HPM is a
Turing machine with the additional capability of making moves. The
adversary
can also move at any time, and such moves are the only nondeterministic
events
from the machine’s perspective. Along with one or more ordinary
read/write work
tapes, the machine has an additional, read-only
tape called the run
tape. The latter, serving as a dynamic input, at
any time spells the
“current position” of the play. Its role is to make the evolving run
fully
visible to the machine. In these terms, an algorithmic solution ( ’s winning
strategy)
for a given constant game A is
understood as an HPM M
such that,
no matter how the environment acts during its
interaction with M (what moves it
makes and when), the
run incrementally
spelled on the run tape is a -won run of A.
As
for ’s strategies,
there
is no need to define them: all possible behaviors by are
accounted for by the
different possible
nondeterministic updates of
the run tape
of an HPM.
In
the above
outline, we described HPMs in a relaxed fashion,
without being specific about details
such as, say, how, exactly, moves are made by the machine,
how many
moves either player can make at once, what happens if both players
attempt to
move “simultaneously”, etc. As it happens, all reasonable design
choices yield
the same class of winnable games as long as we only consider static games, the only sort
of games that we are
willing to consider.
While
design
choices are largely unimportant and
“negotiable”, we still want to agree on some technical details for
clarity.
Just like an ordinary Turing machine, an HPM has a finite set of states, one of which has the special
status of being the start state.
There are no accept, reject, or halt states, but there are specially
designated
states called move states. Each
tape
of the machine has a beginning but no end, and is divided into
infinitely many cells, arranged in
the left-to-right
order. At any time, each cell contains one symbol from a certain fixed
finite
set of tape symbols. The blank symbol
is among the tape symbols.
Each tape has its own scanning head,
at any given time looking (located) at one of the cells of the tape.
For
technical
purposes, we additionally assume the
(physical or imaginary) presence of a move
buffer. The size of the latter is
unlimited and, at any time, it contains some (possibly empty) finite
string
over the keyboard alphabet. The function of the buffer is to let the
machine
construct a move piece-by-piece before officially making such
a move.
A
transition
from one computation step (“clock
cycle”, “time”) to
another
happens according to the fixed transition
function of the machine. The
latter, depending on the current state and the symbols seen by the scanning heads on the
corresponding tapes,
deterministically prescribes: (1) the next state that the machine
should
assume; (2) the tape symbol by which the old symbol should be
overwritten in
the current cell (the
cell currently
scanned by the head),
for each work tape
individually; (3) the (finite, possibly empty) string over the keyboard
alphabet that should be appended to the content of the move buffer; and
(4) the (not
necessarily the same)
direction --- stay put, one cell to the left, or one cell to the right
--- in
which each scanning
head should move. It
is stipulated that when the head of a tape is looking at the first
(leftmost)
cell, an attempt to move to the left results in staying put. The same
happens
when the head tries to move to the right while looking at a blank cell
(a cell
containing the “blank” symbol).
When the machine
starts working, it is in its start state,
all scanning heads are looking at the leftmost cells of the
corresponding
tapes, all work tapes are blank, the run tape does not contain any
green moves
(but it may contain some red moves, signifying that Environment has
made those
moves “at the very beginning”), and the buffer is empty.
Whenever
the
machine enters a move state, the
green-colored move α written in
the
buffer by that time is automatically appended to the contents of the
run tape,
and the buffer is simultaneously emptied. Also, on every transition,
any finite
sequence β1,…,βm of red moves
may be
nondeterministically appended to the contents of the run tape. If the
above two
events happen on the same clock cycle, then both α
and β1,…,βm will be
appended to
the contents of the run tape, where α can
(nondeterministically) go before, after or anywhere in between β1,…,βm .
When
describing the work of a machine, we may use the
jargon “retire”.
What will be
meant by
retiring is going into an infinite loop that makes no moves, puts
nothing into
the buffer, and does not reposition the scanning heads.
Retiring thus achieves the same effect as
halting would achieve if this was technically allowed.
A
configuration
is a full description of the situation in the machine at some given
computation
step. It consists of records of the (“current”) contents of the work
and run
tapes, the content of the buffer, the location of each scanning head,
and the
state of the machine. A computation
branch of the machine is an infinite sequence C0,C1,C2,…
of configurations, where
C0 is an initial configuration
(as described earlier), and every Ci+1 is
a configuration that could have
legally followed (again, in
the sense
explained earlier) Ci
according to the transition function of the machine. In less formal
contexts,
we may say “play” instead of
“computation branch”. For
a computation
branch B, the
run spelled by B is
the run Γ incrementally
spelled on the run tape in the
corresponding scenario of interaction. We say that such a Γ is a run generated
by the machine.
Definition
4.1.1
Let A be a
constant game. We say that an HPM M
computes
(solves)
A --- and
write M ⊧ A --- iff
every run generated by M is a -won run of A.
We say that A
is computable
iff there is an HPM M with M ⊧ A; such an HPM
is said to be an (algorithmic) solution,
or winning
strategy, for A.
4.2 Interactive complexity
At
present,
the theory of interactive computation is
far from being well developed, and even more so is the corresponding
complexity
theory. The studies of interactive computation in the context of
complexity,
while having been going on since long ago, have been relatively
scattered and
ad hoc: more often
than not, interaction
has been used for better understanding certain complexity issues for
traditional, non-interactive problems rather than being treated as an
object of
systematic studies in its own rights (examples would be alternating
computation
[Cha81], or interactive proof
systems and Arthur-Merlin
games [Gol89]).
As if
complexity theory was not “complex” enough already, taking it to the
interactive level would most certainly generate a by an order of
magnitude
greater diversity of species from the complexity zoo.
CoL
has made
its first modest steps[Jap15]
towards elaborating some basic
complexity-theoretic concepts for game-playing strategies, which we are
going
to present in this section. It should however be pointed out that our
way of
measuring the complexity of strategies presented in this section is
merely one
out of a huge and interesting potential variety of complexity measures
meaningful and useful in the interactive context.
Definition
4.2.1 In
the
context of a given computation branch (play)
of a given HPM M:
1. By the background of a clock
cycle c we mean the greatest of the sizes of
Environment's moves made
before time c, or 0 if there are
no such moves.
2. By the timecost
of a cycle c we mean c-d,
where d is the greatest cycle with d<c
on which a move was made by Environment, or is 0 if there is no
such cycle.
3. By the spacecost
of a cycle c we mean the maximum
number of cells ever visited by any (any one)
work-tape scanning heads before time c.
Definition
4.2.2
Let M be an
HPM, and h an arithmetical
function.
Below, if h is not unary, h(b)
should be understood as h(b,…,b),
with as many occurrences of b
in “(b,…,b)” as the arity of h.
We say that:
1. M runs
in amplitude
h iff, in every play by M, whenever M
makes a move on a cycle c,
the size of that move does not exceed h(b),
where b
is the background of c;
2. M runs
in space h iff,
in every play by M,
the spacecost of any given clock cycle c
does not exceed h(b),
where b is the background of c;
3. M runs
in time h iff,
in every play by M,
whenever M makes a move on
a cycle c,
the timecost of c does not exceed h(b),
where b is the background of c.
Amplitude
complexity is to keep track of (set bound
on) the sizes of ’s moves
relative to
the sizes of ’s moves. This
nontraditional complexity measure is indispensable when it comes to
interactive
problems. Next, our time complexity concept can be seen to be in the
spirit of
what is usually called response time.
The latter generally does not and should not depend on the length of
the
preceding interaction history. On the other hand, it is not and should
not
merely be a function of the adversary’s last move, either. A similar
characterization applies to our concept of space complexity. All three
complexity measures are equally meaningful whether it be in the context
of
“short-lasting” games (such as the ones represented by the formulas of
the
later-defined logic CL12)
or the
context of games that may have “very long” and even infinitely long
legal runs.
Definition
4.2.3
Let A be a
constant game, h an arithmetical
function, and M an HPM. We say that
M computes (solves) A
in time h, or that M
is an h time solution for A, iff
M runs in time h
and M computes A. We say that A
is computable
(solvable)
in time h iff it has an h time
solution. Similarly for space and
amplitude.
When
we say polynomial time,
it is to be
understood as “time h for some
polynomial function h”. Similarly
for
polynomial space, polynomial amplitude, logarithmic space, etc. More
generally,
using the asymptotic “Big-O” notation, where g
is an arithmetical function, “time (space, amplitude) O(g)”
should be understood as “time
(space, amplitude) h for some
function h with h∈O(g)”.
We
want to
close this section with two terminological
conventions.
Convention
4.2.4 Assume
H is
a set of arithmetical functions, and M
is an HPM. By saying that M runs
(or
plays) in time H we shall mean that
M runs in time h
for some h∈H. Similarly
for “M is an H
time solution
of …”, “M
is an H time machine”,
etc. Similarly for space and amplitude.
Convention
4.2.5 Assume
h1,h2,h3
are
arithmetical functions, and M is an
HPM. By saying that M
runs (or plays) in tricomplexity
(h1,h2,h3)
we shall mean that M runs in
amplitude h1,
space h2 and
time h3. Similarly
for “M is a (h1,h2,h3)
tricomplexity solution of …”, “M is a (h1,h2,h3)
tricomplexity machine”,
etc. Similarly for (H1,H2,H3)
instead of (h1,h2,h3), where H1,H2,H3
are sets of
arithmetical functions.