(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

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 *C*_{0},*C*_{1},*C*_{2},…
of configurations, where
*C*_{0} is an *initial configuration*
(as described earlier), and every *C _{i}*

**Definition
4.1.1**
Let *A* be a
constant game. We say that an HPM *M*
** computes
**(

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

2. By the ** timecost**
of a cycle

3. By the ** spacecost**
of a cycle

**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 **(

When
we say ** polynomial time**,
it is to be
understood as “time

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
*h*_{1},*h*_{2},*h*_{3}
are
arithmetical functions, and *M* is an
HPM. By saying that *M*
runs (or plays) in ** tricomplexity**
(