Interactive Turing machine

An important part is descriptions of the behaviour of individual actors. Here, the word program is used as a generalization of all types of algorithms and functions, and the two most important types of programs will be probabilistic interactive functions and interactive Turing machines. 

The complexity of an interactive Turing machine has only been defined for the case with one initial input (which would be called an interface input here). Complexity is then regarded as a function of the length of this initial input alone, and not the inputs from interaction with other entities. This is reasonable Otherwise an interactive Turing machine with the attribute polynomial-time could be forced into arbitrarily long computations by an unrestricted attacker who sends it arbitrarily long messages. 

For this reason, one must maintain the convention that an interactive Turing machine computes more than one application of an interactive function. 

What are the computational abilities of the attacker Usually, as mentioned in Section 2.3, only one distinction is made Attackers are either restricted to feasible computations, then they may use arbitrary polynomial-time interactive Turing machines or computationally unrestricted, then they may use arbitrary probabilistic interactive functions. (For more distinctions, see, e.g., the footnote about non-uniform complexity in Section 4.3.)... 

Any attacker or any group of colluding attackers is represented by an attacker strategy, which is a probabilistic interactive function or Turing machine, like a correct entity. ... 

Using the ideas in this article, we find for every Turing machine a lattice with local interactions. Thus, for every undecidable question we find that the long term dynamics of the corresponding lattice system is undecidable as well. 

---