Computability Logic


Section 4

Interactive machines 

  4.1   Interactive computability

  4.2   Interactive complexity

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 hO(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 hH.  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.