Complexity & Computation (Session 9)

I guess... Thank you.

Thank you. Thank you.

Thank you. . . Now the thing, so the weak type of a small step algorithm and a strong form of a small

step algorithms can be understood as two types of SINs, those that accept the intervention environment, the stream of input from the environment, between the steps or throughout the steps. Between the step is when still you are closer to the classical Turing machine. Shuts out the environment throughout the process and only accepts between the steps of input throughout during the step of computation, that's a strong a small step algorithm. It's basically a more refined SIN, more refined sequential interactive machine

that is more refined from the one that simply accepted the streams of input between steps rather than throughout the steps. I will talk about this and how it gives kind of like an internet example of server protocol and algorithm and environment and try to formalize this more properly. Go on, Adam. ADAM KOCHSKY- Well, you're about to go through an example, right? But if it's a sequential machine, then you must have an ordering of instructions at some level of granularity. That's why I'm not. So even if the event happens asynchronously, It has to be imposed into a timeline of observation

by the executing machine at some point, it seems to me. That's all. JOHN MUELLER asynchronous concurrency are completely intractable for classical models of computation. Leads to combinatorial explosion. Once you try, this is in fact kind of a very familiar problem. The translation of P3 nets to Boolean gates leads to combinatorial explosion.

of these kinds of well-defined orderness, you can reinvent it at that level of the Boolean gates with a kind of computer science, the way that we can only call it talk about it. But then nevertheless, there are computational, basically, phenomena. We just need to find a way of how to capture these algorithmically in a kind of a robust sense. But nevertheless, as I said, the whole idea of computation is a semantic of information processing. And they are, in asynchronicity, is a fundamental aspect of transfer of information. So at least the first thing to do

is to talk about them mathematically. First of all, talk about where these problems are. Then try to mathematically at least formalize them. then develop, and that's what I'm going to do, talk about the logic that can capture these. Then that would be not my task, the task of computer scientists, to think about once we have all of these models and a series of mathematical formal presentation, logical systems that can capture this phenomenon, then how can we translate them to the kind of applied computer science and functional programming or programming that basically we can work with? Obviously, many of these problems

in computer science are not of any interest to programming computer science, applied programming computer science. Because they're theoretical. Nevertheless, they are important precisely because they capture phenomena that really the canonical programming domain of computer science is unable to define them or understand them well enough. But also, it encounters problem precisely because it does not have a good model of capturing this phenomenon. And this was, we talked about the rise of actual real physical computers gave to so many problems in computer science for those

classical programming languages and stuff. Precisely because you have massive amount of scheduling between physical systems, concurrency, several protocol, errors, run time, so on and so forth. These are all basically problems. are computational at the most fundamental level. And nevertheless, they need to be incorporated. JOHN MUELLER Right, we're using one right now.

So I'm sure that that's a very important sort of fertile space for theory, right, in that situation. But it's an interesting reversal to what happened earlier in the history of computer science. Yes, yes. Okay. OK, another thing that I just forgot to talk about is the idea that you see this idea of interaction as computation is extremely important for understanding complexity. Complexity involves interaction, as we talked about. Complexity involves resource sensitivity.

We talked about this again. And the kind of a classical model of computation does not have any account for that kind of physical complexity that we talked about. Precisely because computational complexity in the kind of, for example, time and space complexity of, for example, the Turing machines are not really resource sensitive in that fine-grained sense. They are not interactive in that fine-grained sense. They are approximations. For example, a model checking. For example, you go between model and your physical system, your target systems. You go back and forth. This was one of the fundamental problems of what we talked about in complexity, and how model checking itself increases complexity,

increases divergences, nonlinear interaction. And this can itself be computationally understood by way of an interactive model of computation. Your model interacting with the target system and how the model checking is a computational problem in the sense of computation as interaction. So there are so many indexes. Thank you.

Thank you. Thank you.

Thank you. Thank you.

Thank you. Thank you.

Thank you. Thank you.

Thank you. Thank you.

Thank you. So, as I said, I'm going to focus on those algorithms which are behaviorally equivalent to abstract state machines.

And these are the strongest, smallest algorithms. First, it should be noted that when we are using the word environment, we are using it in a very broad meaning. It basically covers everything that is relevant to the algorithm's work, except for what it is internal to the algorithm, and completely as specified by the algorithm's program. For example, in a modern computer, a typical algorithm's environment will include as much as the operating system as might affect the algorithm's operation. In a distributed system, we can consider any one agent as an algorithm and all other agents

as parts of its environment. That was what we talked about multi-agent system. The interaction between two agents, one agent becomes the environment of the other agent. And we have defined these agents quite minimally, simply as algorithms. Even if we think of a more broad sense of agent as having a sensor effector's internal model, And still, we can reduce this to a core base where the rest of the agent becomes the environment of that core base of that algorithm that we have tried to talk about. It will be useful to record some typical examples

of how an algorithm can interact with its environment during a step. Hence, defining more fine-grainedly a strong, a small step algorithm. Because ultimately, the goal is to outline a fairly uniform description of these interactions and the complex computational phenomena that happens once you suspend, once you put the bias on the environment, once you admit and accept complex intervention of the environment during this step.

But before that, first we should look at the diverse possibilities to see what needs to be uniformized. So I'm going to make a few examples of diverse possibilities of how this interaction works between algorithm and the environment, between agents. And again, you can think of these examples and imagine them in your mind as different situations underlying interaction in different scenarios in our civilization game, in our or player opponents, asymmetric warfare, and so on and so forth. But the ones, obviously, the examples

are more of a computer science that I'm presenting here. Example one, the algorithm needs a character strings to be provided by the user. Prompted by an implementation of the algorithm, The user types in a string. We can pretend that the string has been prepared ahead of time and placed it into an input file before this step of the algorithm, and that the algorithm just reads the strings from the file. In this way, we can pretend that the environment, in this case, the user, acted between the algorithm's steps. But this is only a pretense. In reality, the interaction occurs during the algorithm's step.

And the pretense becomes more difficult to maintain if the algorithm could issue any of several prompts requiring different sorts of responses, or if the algorithm interacts with several users who may respond at different times. Example 2. An agent in a distributed computation receives, during one of its steps, a message from another agent. In principle, such a message is similar to the user input in the preceding example, except that no prompt was issued. Example 3. During a step, the algorithm prints a string and continues,

possibly with additional computation and interaction to complete the step. We can pretend that the string is sorted somewhere in the algorithm's state and that it is discreetly removed and printed by the environment after the step is complete. That is, we can pretend that the interaction occurred between the steps. But again, as above, the reality is that the interaction occurring during the step. Example four, an agent in a distributed computation sends a message to another agent. In principle, this is quite analogous to the printing example in example three.

Example five, non-deterministic choices are decisions of the environment. Decisions of the environment. This is what we said the game has the opponent to start by us. The first move, first intervention, always done from the opponent. These are non-deterministic choices, are decisions of the environment. Algorithms are by nature deterministic. What is sometimes called non-deterministic algorithm is really an algorithm that sometimes asks the environment

to make a non-deterministic choice for it. That request and the environment's response can happen within a single step of the algorithm. Example six, an algorithm may need to enlarge its state. For example, a graph algorithm may need to add a new vertex to the graph it is working on. Or a Turing machine with a finite tape might have reached the end of its tape and want to attach a new cell in order to continue its computation. A state of an algorithm is assumed to contain, in addition to its active part, an infinite supply of reserved elements

available to be imported as new elements of the active part of the state when needed. This importing, or at least the choosing of the element to be imported, though requested by the algorithm, is actually done by the environment, since it can be non-deterministic. Example 7. Abstract state machines can have so-called external functions. These are similar to any other basic functions in the abstract state machine's state, except that their values are not controlled by the algorithm, but rather by the environment. The values of an external function cannot change during a single step of the algorithm. For example, an important use of external functions

is in modeling distributed systems. A value that is written by one agent and read by another is represented as an external function value of the reading agent. since agents operate asynchronously, the value of this external function can change in the middle of the reading agent's step. In such a situation, if an abstracted state machine's program refers several times to the same external function with the same argument tuple within a single step, the values may nevertheless be different. Indeed, if a writing agent works faster than the reading agent, then the latter may see an external function value change several times during one of its

steps. So this idea that we talk about work once you restrict the amount of work done, in terms of the speed, even the speed of, if we think of these processes, the system and environment, in terms of the speed of computation, the speed of computation also leads to different interactive behaviors, precisely because, as we said, if we can think of the system environment as a writing agent and a reading agent. And in our example, if the writing agent

works faster than our reading agent, then the latter, meaning our reading agent, may see an external function value change several times during one of its steps. And hence, new adjustments need to be made. And what is basically the significance about this is that interaction is not only about this back and forth between query and reply, but also it has something to do with the properties of the processes by themselves that are interacting.

If one agent, in terms of processes, is quite asymmetric to the other, that, again, leads to different complex interactive phenomena, and hence need to be accounted for within, for example, the steps of our algorithms, the steps of our agents inside the mechanisms of the system. Adjustments needs to be made, so on and so forth. It is possible to model the picture with varying external functions within this framework. This involves replacing different occurrences of the same external function symbol by different symbols, for example, by attaching subscripts to the function symbols in f1, f2, n.

With these examples in mind, we can now discuss, in general terms, the view of algorithms, environments, and their interaction in that sense of strong and small algorithms, namely refined, interactive, sequential, interactive machines in order to capture various complex interactive phenomena. And if there is a time, which I don't think is, at the end, I will try to give a kind of formal definition of the general terms. Nevertheless, the preliminary generalities

are important because they provide the intuitive basis of the formal presentation. that if there's time, I will give it. The algorithms that I'm going to discuss concern the interaction with the environment. This is the first thing. In other words, our focus are those algorithms are corresponding to sequential interactive missions. Are those algorithms that proceed in discrete sequence of steps, sequential time algorithms. Initially, and again at the end of each step that doesn't fail, the algorithm is in some state which incorporates all the currently available information that will be relevant

to the future progress of the algorithm. That was the IOS stream that we talked about. It takes an input stream, it yields an output, and that output stream affects the input of the next state and the state and the step that it's making. For example, if the algorithm is a Turing machine, then the state in this sense includes not only the state of the finite control, but also what is written on the tape and which cell is scanned. That is, it includes what is often called in computer science the instantaneous configuration or instantaneous description.

The state changes only at the end of a step. During a step, the algorithm can do a scratch work. But unless this work is recorded in the state at the end of the step, it will not be available in subsequent steps. These are all basic properties of I-O streams. We are concerned here with the changes that the algorithm makes to its state in any step. The environment can also intervene between steps to change the state, but such changes are outside the scope of our discussion. The role of the environment plays in our discussion is to provide information during a step of

algorithm, thereby affecting the state at the end of that step, that diagram, if you remember. Therefore, we are studying interactions between the algorithm and its environment taking place entirely within single steps. As I mentioned, interactions that take place between the algorithm steps, so we do not need to reconsider them here. That was the weak type of a small step algorithm. If an interaction appears to expand several steps, then it should be regarded as separate interactions within single steps, with appropriate information being recorded in the state so

so that the algorithm remembers the earlier interaction when the later one occurs. This basically corresponds to that persistent Turing machine that we talked about. Not only are there interactive sequential algorithms, but also there are history-dependent. These are the several steps, the smallest of algorithms. For example, if the algorithm prompts the user for an input during one step and receives input during a later step, then the prompt should be treated as an outgoing message. The user's input should be regarded as an incoming message.

And the state should, between these two steps, record that a prompt was issued and how the resulting input should be used. In this way, we maintain the principle that the state must contain all the information from the preceding step that is used at any later step. History dependency. It's convenient to assume that the interaction between the algorithm and its environment takes the form of queries from the algorithm and replies from the environment.

That's as I said, reply and query, assertion and questionings are two key concepts of interaction. At first sight, these assumptions to exclude example two that I gave. And what was the example two? The example two was an agent in distributed computation receives during one of its steps a message from another agent. In principle, such a message is similar to a user input in the preceding example, except that no prompt was issued. As I said at first sight, this assumption seems to exclude example two where the environment

supplies information without being asked. And example three and four where the algorithm exports information without expecting a reply. These and similar examples can however be brought into a query reply form rather easily as I'm going to outline. Consider first a situation where the environment supplies information without being asked for it. Think of this in our civilization game, just playing, and certain client stuff. Such information cannot have any effect until the algorithm pays attention to it. We regard the algorithm's act of paying attention as an implicit query, and we regard the unsolicited

information as a reply to that query. These considerations are intended for environment actions within a step. If the environment provides information within the steps, then it should be viewed as changing the algorithm's state to incorporate this information. This view applies in particular if the algorithm is written, for example, in object-oriented style programming, and the incoming information is a method call to one of the objects. Those of you who are familiar with this stuff. The call is regarded as the answer to an implicit query of the form I'm looking for a method call. It may seem that this lowers the abstraction level, but it doesn't.

But there is no need to know in detail how the algorithm inquires about incoming calls. Any implementation of the algorithm will do it in some particular way, but there will always be a query. Now consider, for example, a situation where the algorithm emits information without expecting a reply. For example, by sending a message or by printing a string, we could also regard them as queries to which no reply is expected. But that approach would require exceptions in the clause of the definition of ordinary algorithm, requiring that they complete a step only when all queries have been answered. That wasn't constraints that we put in our defining

as strong as smallest algorithms. And basically, it filters out so many, that kind of waiting for all the processing has been done, that filters out so many complex interactive phenomena and intervention of the environment. The OK convention means that these queries are automatically answered, so they have no effect on whether a step can be completed. The choice between the two conventions is a matter of convenience. With these understandings, we can safely regard every interaction between an algorithm and its environment as being initiated by the algorithm

with a query to which the environment supplies a reply. In accordance with our earlier discussion, the reply will arrive during the same step in which the query was issued. If it is arrived later, we'd have two interactions, one in each of the relevant steps, not a single query and reply. The query then would be considered an output, i.e., a query that gets an automatic reply okay during the same step. The reply at the later step would be considered an unsolicited input, i.e. a reply to a query in that same later step that consists of just paying attention to this input.

Now, it is entirely possible for several such query reply pairs to occur during a single step, and the later queries may depend on the earlier replies. We can have this in kind of like a multi-agent dialogue conversation. However, for a small step algorithm, the number of queries issued in any step must be bounded by a number that depends only on the algorithm, not on the state or on the replies to queries. After all, issuing a query is work, and the total work done during one step is bounded. A query gets at most one reply. If it appears that several replies are given and are used by the algorithm, then much as

in our discussion of unsolicited input, we regard the algorithm as paying attention to subsequent answers as constituting additional implicit queries. It is, in this sense, imaginable that the query gets no reply. For example, the algorithm may request a non-deterministic choice of an element from some set. the set may be empty. In such a case, the environment may simply fail to respond. This is basically when, because in interaction, it's not that they are always actively in track, but we have failure to response. And computationally, in interaction, we should be able to capture failure to response. For example, the algorithm may request

an undeterministic choice of an element from some set, and the set may be empty. In such a case, the environment may simply fail to respond, though it would be more reasonable to expect a reply in the form of an error message. Perhaps of the form, cannot choose from empty set. For another example, the algorithm may prompt the user for some input, and the user may fail to respond. Here, as I said, we only discuss ordinary algorithms, which means in particular algorithms never complete a step until all queries issued during that step have been answered to. If the environment refuses to answer, then the algorithm simply hangs.

The step is never finished, and there is no next estate. A great many practical algorithms are of this sort. For example, the algorithm may incorporate a timeout mechanism whereby if no answer is received within a certain time, then this fact is itself regarded as a reply. So that the algorithm can proceed, perhaps by withdrawing the query, perhaps by just making a step with no change to its estate, perhaps by doing something more intelligent, or perhaps by doing something disastrous. Notice that the timeout information, that is the information that so and so much time has elapsed

since the query is itself provided by the environment, though probably by a different part of the environment than the part that should be answering the query. This is in keeping with the principle that what the algorithm does during a step depends only on its program, its estate, and information supplied by the environment. A clock that keeps time independently of the progress of the algorithm's execution is not part of the program and not part of the state. So then it must be part of its environment. Now we should ask why the emphasis on the study of intra. So these basically were some of the problems

of this various dynamics of query and reply, and how query and reply can be formulated in different scenarios, time-off scenarios, error messages, failure to respond, asynchronicities, and so forth. Now, in defining sequential, refined sequential interactive machines, or sequential algorithms, in their strong form, in their more interactive form, which was basically intra-step algorithms, we need to pose a question that we should ask why the emphasis on the study of intra-step interaction with the environment?

Second, why restrict attention to ordinary algorithms? First, to answer the first question, the intra-step one, it is natural to ask whether intra-step interaction is needed at all. can't we just consider every interaction with the environment as ending the current step and starting a new one? By subdividing the sequence of steps, decomposing the sequence of steps sufficiently finely, can't we reduce all interaction to the inter-step case, the kind of Turing machine approximation? There are several reasons for not wanting to subdivide or decompose a step so finely. First, the subdivision would make some aspects of the situation

unpleasantly complicated. For example, the situation of interaction. For example, the evaluation of a single expression, say as part of an assignment command, could span several steps if the expression involved nested occurrences of a function that is evaluated by calling an external library or another agent's method. Modeling and reasoning about computation is facilitated by using reasonably large steps rather than subdividing or decomposing so finely. Second, this subdivision would be incompatible with any parallelism within a step. Therefore, for example, one could not evaluate un-nested occurrences of a library function

in parallel. The reason is that any query to the environment by one of the subprocesses would end the current step. And it is unclear what should then happen to the other parallel subprocesses computations. Although the restriction in the present discussion to a smaller step algorithm means that there will not be massive parallelism within a step, a bounded amount of parallelism, such as evaluating several expressions in parallel is permitted and very desirable for modeling and specification. In practice, an algorithm often interacts with this environment in two ways.

There is a local environment, often on the same computer or closely connected machines, and there is also a global environment, often out, for example, on the internet if we think of the model of interactions in terms of our computers and internet environment. Within the local environment, the algorithm has conversations between machines, like method calls and callbacks. They are best viewed as just fulfilling a single request. While this is going on, the algorithm should maintain a fixed state as far as its long distance interactions of concerns in terms of global environment.

Then the conversations within the local environment, within machines, are mostly considered to be intrastep interactions. So the reason of this, why is it this decomposition to this fine-grained step is not really optimal, because when we have this kind of massive complexity of interaction in our environment, we usually have local environment and global environment. Short distance interaction and long distance interaction. And the idea of this intras step and avoiding fine-grained decomposition is precisely because

this allows us to see interaction from, in terms of long-distance interaction, in terms of global environment, from Internet as opposed to just conversation between machines on a network. This issue is connected with the notion of transactions in database theory. The idea here is that many updates are collected and performed all at once. A familiar example is a, I think, I talked to Adam about this in one of the previous sessions about concurrency and ATM. Another familiar example of this is the transfer of money from one bank account to another. The subtraction from the first account and the addition to the second must occur together.

If one fails for any reason, then the other should not be executed either. And this happened quite frequently back in old days in ATM machines where you have a Why can a husband withdraw money from ATMs? Precisely because there is no long distance from the perspective of global environment. Interaction or capturing interaction, how these things work, the ATM goes to negative. Whereas basically when you have a genuine concurrency, not only you have local scheduling,

you have global scheduling, you have global concurrences, you have global interaction. That allows, for example, an ATM machine to introduce, to stop the transaction so it doesn't go to negative. So the state must persist until all the updates are ready, which is likely to be longer than merely from one interaction to the next. Within that our, you see, so for example, as we talked about, you know, again in terms of our ATM machine, you can think of the ATM machine, one of the ATM machines itself as,

know, interaction between different parts of the machine, which is considered to be a machine, and the conversation that allows for the ATMs to process a request. And then this would be the conversation within the one single ATM, the conversation between machines. It's conversation with another ATM, or probably a bank database as another place that, for example, your friend tries to get money from it. That would be the long distance one. And as I said, the state must persist

until all the updates are ready, until that update from that ATM and this update are both ready, which is likely to be longer than merely from interaction to the next. In the example that I just mentioned, the crucial property of the transaction is that it can be rolled back. If anything goes wrong during the transaction, the state remains as it was initially, not as the already computed updates would have it. Notice, though, that not everything can be rolled back in this sense. The state of the database reversed to the beginning of the step. But any prompts and other messages issued the user cannot be unissued. Of course, the user can and should be informed

that the transaction failed, but nothing can alter the fact that he has seen the previously issued messages. The situation is similar in the computation model we are discussing here. If a step fails, the state remains unchanged, but any queries already issued cannot be retracted. Now, to give an idea of the aspects of computation modeling that make a step interaction desirable, we describe a small example reflecting real world experience. For example, consider the task of painting, assigning colors to the parts of some picture. Suppose an algorithm wants to paint two pictures with these

jobs being done in parallel. The actual painting is done by another agent, the operating system, in response to a method call from our algorithm. But the picture isn't directly available to our algorithm, so it can't send complete instructions for the painting when it issues the method call. Instead, the painting agent to whom the picture is available produces callbacks to our algorithm, saying such and such is in the picture, what color should it be? And by replying to these, our algorithms gradually specifies how the picture is to be painted. After each reply, the painting agent paints the item in question with the specified color. The entire process of painting a picture should be viewed as a single transaction.

If any part of the conversation fails, then all colors should be reverted to what they were before the conversation began. When our algorithm issues two parallel calls to paint two pictures, the resulting conversations should not interrupt each other. For example, by ending this step. The best way to model the process is as a single step, with interaction during this step. In order for this to be a smallest step algorithm, it is of course necessary that the amount of interaction in a step be bounded.

Therefore, it must be required that only a bounded number of callbacks occur during any one step. If the number of callbacks were unbounded, the algorithm would still make sense, but it would not be a small step algorithm in the sense that we defined it. Another use of inter-step interaction is to model non-determinism. As I mentioned in example five, if I remember correctly, what is sometimes called a non-deterministic action by an algorithm is really a choice made for the algorithm made by the environment. Because the deterministic Turing machine is that it's all the bias is on the player,

is all the bias on the algorithm, on the system processing information. But there are also times that the opponent, in fact, as I will talk about this, in fact, When the player first makes the move, when it's determinism of the algorithm, these are special cases of general computational phenomena. Because the general, you know, and Abramsky formulates this formally, that the general computational phenomena are by nature non-deterministic. It's the opponent that makes the first move. the environment that makes the choice of the value. So the interaction here, in a kind of a non-deterministic framework, the interaction involves here, namely the algorithm is a request

for a choice and the environment's reply is most naturally viewed as occurring within a step of the algorithm. This applies in particular to the creation or importation from the reserve of new objects. Finally, it should be pointed out there is also a connection with the issue of abstraction levels. And the whole resulting conversation constitutes just the evaluation of a single expression. Modeling at that level of abstractions requires interest of interaction with the environment. to subdivide the steps in order to call this inter-step interaction, as opposed to inter-step interaction, would be to descend to a lower level of abstraction.

So this was why we talked about intrastep and the idea of ordinary algorithms, algorithms that must wait until all process is done. So this is one reason. The second reason is why we are putting the emphasis on ordinary algorithms in the sense that we defined then, is that when an ordinary algorithm issues a query, it cannot complete the step until it receives a reply. Certainly not all algorithms are like this. Why then is it reasonable to restrict attention to ordinary algorithms in this sense of ordinariness?

The answer is relevance to practice. Although one can design algorithms that don't wait for replies for all their queries, such situations are uncommon. In particular, programs in abstract, say, machine language always wait for replies. Referring what I briefly mentioned about local and global environment, we recall that interest of interaction is needed, in fact, for modeling the algorithm's conversation with its local environment. In those conversations, if the environment failed to provide an answer, the computationally normally would hang. An algorithm that sends a message to the global environment may well continue its computation

without waiting for an answer, especially since it may expect some delay before the answer arrives. But this is not usually the case for messages to the local environment, such as, for example, remote procedure calls. The third reason is ignoring timing. The information from the environment that an ordinary algorithm uses is only the replies to its queries, not, for example, the timing of those replies or how hard the user, for example, punches the keyboard when typing the input. Why is it reasonable to impose this restriction? Again, there is the justification from practice. Second, some sort of additional information

could, if one wanted to consider them, be included as part of the replies to the query. For example, nothing prevents replies from including timestamps. A more technical justification is that it is difficult to simultaneously permit bounded parallelism within its steps and dependence of the algorithm on the timing of replies. Consider for example two parallel sub-processes, each of which asks a query and receives their reply from the environment. The relative timing of the two replies, which came first, is information available to the algorithm, but to neither of its two sub-processes. So if this information

affects the computation, then it is not clear in what sense the two sub-processes are independent, in what sense there is a genuine parallel. So far in our discussion, we have taken for granted that there are clear notions of query and reply as the two basic concepts of interaction, assertion, question. There are, however, some real difficulties with these concepts at technical level, defining what a query is, what a reply is. because these are especially the two key concepts of interaction in computer science. To address this, I'm going to briefly

talk about these difficulties. The central problem is first the discrepancy between what looks reasonable when we concentrate on algorithm and what looks reasonable when we concentrate on environment. At this point, our primary focus is analyzing algorithms. So we can, in the end, understand an algorithm-centered view of queries and replies, basically sequential interactive machines, sequential algorithms. But before settling on that view, we must compare it with an environment-centered view to ensure that what we discussed here will be applicable in the context where the environment plays a more central role. which was basically the strong version of interaction

computation. An important example of such a context is the study of distributed algorithms, where every agent is part of every other agent's environment, compared to this with the definition of multi agent systems that we gave. Let's begin with some basic comments on the queries issued by an algorithm. As the examples that I mentioned, There can be many different sorts of queries, prompts, print, prints, commands, requests, for non-deterministic choice, paying attention to an input, et cetera. So it's reasonable to think of a query, a question, as containing a label indicating what type of query it is.

Additional labels may also be involved, for example, to indicate which part of the algorithms program issued the query. These labels can be taken from a fixed finite set that depends only on algorithm, not on its states. But a query can also have ingredients. Let me share the screen. One second, sorry.

Can you see the screen? Yeah, that's it. So but a query can also have ingredients that depend on the state. For example, to request the value of a of an external function f at an argument a, the algorithm should issue a query that contains at least the function symbol f or some other label that specifies f and the argument a.

The F part is a label, as in the previous paragraph. It comes from a finite set fixed by the algorithm. But the A part is different. It comes from the base set of the algorithm states, which is by no means fixed by the algorithm. The picture emerging from these considerations is that a query can be represented by a finite tuple whose components are either labels or elements of the same. The labels come from a finite set lambda determined by the algorithm. Since we are talking about the smallest of algorithms,

there will be a finite bound, depending only on the algorithm, for the lengths of the tuples that represent queries. The intuition here is that assembling the components of query is work. So a small step algorithm can only do a bound amount of it in any step. For the same reason, the number of queries issued during any step will be bounded. Now, two technical points arise here. And that's why I'm going to share this screen, because of the notations. One is a matter of normalization, in the sense that we understand normalization. We could, for example, insist that in the tuples representing queries, labels precede state elements.

We could also modify our set of labels to include tuples of the original labels, and thereby arrange that each query involves only one label. The second technical point concerned the possibility that labels given with the algorithm might also be elements of some states. In fact, if we adopt the abstractness idea, namely that every isomorphic copy of the state is also a state, then such an overlap between the states and the set lambda can really occur. This situation about isomorphic copies could be restricted to copies that use certain permissible entities as elements of the state. Members of set delta would not be permissible alternatively.

We could take the components of queries to be elements of the disjoint union of x and lambda, where x is the state. Disjoint union means that the two sets are replaced by the disjoint copies. For notational convenience, we can adopt a second approach, but we can suppress all mention of the copies. In effect, we write as though x and lambda are always disjoint. How should replies to queries be represented? The simplest answer then that a reply is represented

by an element of the algorithm state. The intuition behind this is that the reply must be something that makes sense to the algorithm. And such things ought to be included in this state. One might argue that for the sake of symmetry, replies should have the same form as queries, namely tuples. But that situation can easily be accommodated in this picture by one, adding to the vocabulary names of the labels so that labels can be represented by state elements, and two, splitting any query that asks for a tuple into several queries, each asking for one component of the tuple. Part two wouldn't be needed if the state of the algorithm

are closed under formation of tuples. Such closure is common for realistic algorithms, since programming languages generally provide for tuples. But also, you can think of this, the importance of this complexity of stuff that arises when you are trying to define queries and replies is that precisely because we said queries can initiate from different parts of the algorithm, different states. They might have different types. And the thing is that in an actual interaction, when we are, for example, again, think

of more of intuitive examples. Usually, interaction is like kind of a complex framework. civilization game, or any other example that you can think of, are not quite symmetric really in terms of type of processes and a small step interactions that are executed. They might be issued from different parts of one process and others are issued from another part of another process. And this lack of symmetry between types,

between components responsible for issuing replies and query, in fact, again, can lead to more problems in defining and capturing the idea of interaction computation. In view of these considerations, we can generally adopt this convention that queries for a state X are two poles of elements of this joint union between X and lambda, and replies are elements of X, where lambda is a finite set of labels fixed by the algorithm. This convention describes queries and replies as seen by the algorithm.

must so this was from the point of algorithm but we said that in terms of when the choice is done sorry not a choice when you know in terms of the global environment or from perspective of the environment general the issue of abstractness arises in capturing the idea of defining, not capturing the idea, defining the concept of query and reply. In computer science, both theory of abstract state machines Both theory of abstract state machines and iso-matic description of algorithms have among

their basic principles the abstractness of states, hence terminology in abstract state machine. Abstractness means that all the important information about the state must be explicit in its interpretation of function symbols. A specific identity of the elements must never make a difference. In particular, an isomorphic copy of a state x is again a state, and for computational purpose it does not differ from x. In our present situation, to formally talk about this, in our present situation, replacing a state x by another state, say x prime with an isomorphism, x isomorphic to x prime,

would change the queries and replies. Suppose, for example, that the algorithm requests the value of some external function f as an argument given some term t involving no additional external function for simplicity. Then x will issue a query that looks like a tuple f a, where a is the value of t in x and where we have ignored possible additional labels while x prime issues fa where a prime equals to ia it is the value of t in x prime from the environment's points of view this you know seems quite reasonable the environment then would have to look into the

state x and x prime to find out what those elements a and a prime represent and would have to formulate its reply as an element of x or x prime worse yet the very the very same tuple could be issued as a query by two isomorphic estates but with entirely different meanings for example a component of such tuple could be the element serving as a number zero in one state as the number 17 in another how is the environment to react when presented with such a query and in an omniscience environment knowing what the states are could handle the problem

but this never uh works if for example the environment consists simply of the other agents in a distributed system. Now the solution to this difficulty is two parts, of which the first one is sufficient for setting up suitable postulate to describe ordinary interactive small step algorithms and formally present them. The second part will however be important for making contact with what usually happens in practice. The first part involves a closer examination of the idea of abstractness that led to the requirement that a state be replaceable by any isomorphic copy. The idea makes good sense when we consider it an algorithm in isolation, basically in

a classical Turing machine sense. But as we discussed, it must be modified in the presence of interaction. The modification, fortunately, is quite simple and natural. What is abstract? can be replaced by an isomorphic copy is not the state of the algorithm alone but the entire system a state plus the environment therefore when we replace a state by an isomorphic copy we must correspondingly replace the environment in such a way that the entire system is isomorphic to what it was before the replacement in a kind of intuitive sense we can think the difference of this in terms of the difference between what we mean usually but by simulation and

what we mean by reenactment you see simulation is supposed to basically replicate a function behavior is exactly works like in the kind of when basically copy the estates and reconstruct them precisely because we take the algorithm in isolation in the kind of a classical Turing machine sense. But if every state of the algorithm basically is interacting with its environment, then how can we really copy this in that classical sense? The isomorphism doesn't hold in the

course of reconstruction we need the function plus the environment it and simulation simply tries to replicate you know a given observable behavior reenactment however tries to reconstruct this behavior by replicating not the system but also reconstructing the environment to which the system with which this system is interacting so the this idea you know that I just mentioned can be intuitively thought in terms of the difference between simulation in a technical sense reconstruction

of observable behavior precisely because of this isomorphic assumption and the difference of the different stimulation from the procedure of reenactment in the sense, for example, talk about it in extended theories of mind or inactive theories of cognition. That simply how we, for example, you try to recreate something like called human mind or intelligence, we can't look into it as taken in isolation, as simply a function, that kind of algorithm

taken in isolation but we need to replicate not only the system, not only the brain but also its environment. And this is really what mind is. It can't be simulated. Mind can be reenacted but cannot be simulated precisely because of, we have the kind of similar situation here that I just talked about. moving forward any discussion anything before I I'm going to just talk for 10 minutes and or maybe we should just stop here because there is still a lot going on and I won't be able to finish this part today before I you know give it

finish the sequential algorithms and try to give a kind of a formal definition sequential algorithms and then so we can go to our notion of interaction where we can kind of call here why interaction computation is really important and kind of glue all of these minute details that happens in the interactive frameworks and in our examples in terms of query and replies between which abstract machines or our network systems can

be basically can be seen as general computational problems yeah I'm not sure if I can really finish this today so why not just stop here and make some questions and having some discussion stuff I think we should maybe postpone the discussion to the next session, to the beginning of the next session, because I'm really tired. Yes. Okay. Okay. What about you, Adam?

Yeah, I'm hitting a bit of a wall, actually. And there's a lot to digest as well. So yeah, I'm happy to roll it over to the next. Is there any parts that you want me to? I will talk about these more generally. So the reason that I get these kinds of like a more abstract version or kind of like a more computer science definition of interaction. So to make this kind of violate your intuitive idea of interaction, because when we are talking about interaction, we usually have this kind of like, oh, communication and stuff.

Well, interaction, the way the computer science understands it, it involves all of these really minute details about timeouts, errors, asynchronicity, asymmetry, symmetry, you know, isomorphism, copying strategies, so on and so forth, which are basically what interaction is. So first I wanted to make this to get rid of the intuitive idea of interaction and then really talk about general idea of interaction and starts to build on it with regard to these.

Yes. I think it worked. I mean, we got it, basically. We got your, you know. deconstruction of our intuition. Yes, yes.

Your problem, your exercise for this week, install civilization game, play civilization game, think about this in several asynchronous games. Cool. No. Thank you.

Thank you. Thank you.

Thank you. Thank you.

Thank you. Thank you.

Thank you. Thank you.

Thank you. Thank you.

Thank you.