The last one is not up yet, at least it wasn't yesterday. OK, OK, OK, OK, so it's OK. I will, well, I mean, because the reason I asked, because, you know, it got into some technical details and stuff, so that's why I wanted to make sure so you could follow the continuity. But it's OK, I will try to kind of make some minor change this session and probably skip the end of that until it's uploaded, and then so we can resume and finish that topic, which wasn't that much left of it. Anyway, so any questions, discussions before starting?
Did you guys install Civilization playing it? Not yet. Got plans to do that. So I finally got through the first computation, I guess like session six or whatever we're calling session six. SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 SPEAKER 2 you know the abstract machine that is contained in the symbol or set of
symbols and I was just wondering like what you meant by computational variations or actual computational variations in that context I don't really remember can you elaborate it by having a really bad memory so you need to tell me what exactly I said I just like note to myself to ask about it yesterday and now I've got a kind of like... Okay, so... The... It was an issue of the causal force of the schema of the abstract machine, and that there are already a determination of what the outcomes of the operations of actual physical machines were going to be within the abstract machine
that drives them or that they implement. And it was like... Are you talking about a strong interpretation of church-turing thesis? Possibly. There's like a missing 20 minutes in the middle of that session. And so where in the flow of topics it is, is slightly disrupted or hard to figure out, but it was definitely within the discussion of the formal... Sorry. It's okay. As a condition of reasoning about computation, or how it falls into...
Let's see. It was shortly before discussing how formalisms are like cognitive prostheses and part of the extended theory of mind. Maybe I might have to just go back to the video and try to copy down the exact quotes. Okay, I will look at my notes, too. But, I mean, I remember, well, the cognitive, you know, basically, prosthesis idea was just basically quite as straightforward, this idea that, you know, formal systems, and especially the notion of formalism as computability, generally speaking, has been
shown to be quite good at what we are weak at, and especially in the areas that involve intuitive judgments, perceptual judgments. The case of, for example, famous Israeli people who in AI talk about Linda's case is kind of like a classic intuitive bias. For example, Linda is working at a bank. is liberal in her lifestyle and she's gay, is she Republican or Democrat? Obviously, because of our intuitive bias, the epistemic accumulation of our prior knowledge
bearing on our hypotheses and conclusions, we might say she's a Democrat. But this is absolutely an intuitive judgment, which is biased judgment. And computational formalism, formal judgment, and computation in that sense also, they do not have these kinds of biased judgments. But also, when it comes to the neuroscientific aspect of cognition, and this is something that Katarina Lutlino-Weiss talks really in detail. that elaborates it really in an astonishing way, showing that, for example, the parts of the brain
or the kind of synoptic connections are being activated during manipulation of formal systems and the kind of tight chain of deductions that you have there. It's completely different from the kind of regular sensory motor activations of basic heuristic judgments. Right. And is that true? I mean, I don't know, I might have to just like swap this up myself, but whether you are mentally going through a chain of deductions or actually using a written formalism at the time, like, you know, like writing out a proof or like you going through like a written proof versus thinking in my head like, okay, major premise is true, therefore minor premise.
Do those activate the same things, whether I'm using a hypognetic, a physical artifact, or a physical prosthesis, or just mirroring what I learned to do using it in my head, but not actually using the stick in the sand? Reasonably, so what happens in the menno, right? Would you see different brain activation patterns if it's the slave boy literally the first time sketching out the triangles in the sand versus later when you asked him a new question and he didn't have to do it physically in order to think of what the answer was? Well, I think they can be said to be similar, but ultimately this whole idea of writing, you know, in a technical understanding of writing and reading in a brandonian or even in computer science sense,
that you write on a piece of paper, meaningless signs, whose logical connectives are the ones that give them semantic import. And then you follow the chain to this inscriptions of how you put them together. That's completely different from the kind of, for example, lived experience of invention of mathematics. For example, you see it in the Archimedean experiments, in the tub, kind of, as you say, drawing in the sand, a triangle. But this triangle, the way that it's invented, for example, in mathematics, again, connected to our basically heuristic intuitive inventiveness.
They are similar. But what I'm proposing, what she's proposing, is that once you really deepen the understanding of each one of them, the formalism, the pure formalism, the one that you write on a piece of paper, inscriptions, meaningless inscriptions, and then you follow through logical connectives, the chain, the tight chain of deduction is fundamentally different in terms activating patterns in the brain from the one that has a link to heuristic inventiveness, to ingenuity. So it's kind of like, it's where we externalize the heuristics or go through a process of
externalization that develops or invents these formalisms or mathematics and then re-internalize that as a completely different kind of thinking, which is the tight deductive chain. so you've got like a one, two, and then back. I'm kind of thinking of, I don't know if you're familiar with Bernard Stiegler. That's kind of what I'm trying to link. Sorry, with who? Stiegler, Bernard Stiegler. Bernard Stiegler. I have read some of his stuff, but now I'm not that much familiar with his work. Okay, okay, that's fine. Maybe I'll incorporate it into the paper or something. Yeah, no, that's definitely helpful, and I'll look for the specific quote that I was confused about or the specific line or something. Maybe .
I think she's not sure if I'm spelling her name correctly, but put it in Google and you get the right spelling right. Katarina Dottil-Noviis. Hi. I mean, the whole thing is that formalism in the sense of, you know, computability or decoupling from semantic content, manipulation of meaningless signs, inscriptions.
It has two levels, as you say. Basically when you look at how we developed, for example, numbering systems, especially geometry, which geometry has a lot of heuristic creativity. They have, again, some sorts of prosthesis logic, extended mind. You know, Chatelet talks about this in the state of the mobile a lot. Basically geometers always use gestures in order to be able to develop an intuition,
Kantian sense of a geometric figure or a geometric principle. They couple what Aristotle thought is the weak part of the metaphysics, which is physics, the mobility, motion, all the ickiest stuff in the world, with mathematical formalism. So it's like this constant going back and forth between the phenomenological aspect of living in the world and putting yourself in place of objects, like Einstein put himself in a place of a photon, thinking himself traveling at massive speed so he can understand the curvature, space-time curvature.
Or Archimedes put himself in the top as this demon of abstraction so he can be able to come up with the principle of buoyancy and tell whether the votive crown is fake or not. So there is this engagement with the phenomenological aspect in the sense of mobility, gesture, so on and so forth. But in order for a geometer to do that, it's not purely this gestural creativity either. He needs to know, for example, a precise definition of a concept. For example, Archimedes, in order to be able to conduct his experiment, this kind of intuitive
experimentation correctly, he needs to know the precise definition of a volume. So it's not pure inventiveness. You need to have this oscillation between precise mathematical concepts and gestural creativity, phenomenological experimentation. And going through these two, you are capable of developing a new geometrical intuition. So from that perspective, even the intuitive experimentation that you can see a lot in the the invention of mathematical objects involves both internalization and externalization.
Similarly, with the formalism, again it has two sides. As you say, once you invent a mathematical object, then you internalize it according to precise deductive chains, so on and so forth. But the whole idea of putting it on the paper, even if you do it privately in your head, that's again an externalization. The whole idea of symbol manipulation is an externalization of the mind. It's precisely because you follow the chain of deduction between concepts over which your intuitions don't have any hope. It's the idea of the concept in formalism is a space over
which man has no hope. And that's a form of externalization. That's a pure process of judgment, of cognition. So again, both of them has internalization and externalization. But the thing is that externalization of these two, the formal judgment and the intuitive judgment, intuitive creativity and computable formal de-semanified creativity, they're fundamentally different. Right, because one is more of a virtual externalization. It's a small lived experience, whereas the other one is purely the sign that controls
inscription, meaningless inscription that controls the chain. And to say that it's meaningless or to operate that way is to render it or to treat it as external to your phenomenological judgments and so forth. Yes. And that's like the demon of attraction would be like the emission of this virtual agent, which is independent of your phenomenological structure. Yes, yes. And there are, in fact, mathematicians who extract these intuitive experimentations and turn them into pure formalistic experimentation. And Cauchy is one of them. Kashi, in order to develop Kashi integrals, path integrals, the concept of path integral,
he exactly does the same thing as Archimedes. He puts himself in the place of an object, a point, so small in a curvature that you need to then, instead of this point, like Archimedes, his body is connected to the water and the lived experience, the phenomenological aspects of the top system, the fluid, the force, the gravitation, so on and so forth. Whereas Cauchy, once he's himself in place of a point, an infinitesimal point, he no longer has this phenomenological aspect. The infinitesimal point is no longer connected to some lived experience
of phenomenological aspects, but to other concepts. to the integral, to the path curvature, to summation of forces, so on and so forth. It's become a point in a different kind of space. Yes, yes. Okay. And Schottler, I think, is absolutely, you know, that book has got a lot of bad rep among kind of analytic philosophers of mathematics as being too French. Yeah, Châtelet is extremely French in a bad way. Well, French is always a bad way. But the thing is that it's absolutely, once you look into the history of development of mathematics,
geometry from antiquity to classical to higher scholasticism to Renaissance, Enlightenment, so on and so forth. You see, he absolutely has astonishing insights of how this historical development of concepts of mathematics were basically progressing. And the way that he formulated it, I think it's absolutely one of the best books on mathematics ever. Which one? Which book is that? Yes, take up the mobile, translated to English as figuring a space.
solutions to the exercise but you definitely need to formulate and think about these solutions I will give you those of you who are familiar and give you an exercise about so-called dining philosophers problem which is basically a concurrency problem. So yes, that's today's exercise. But I will write the assignment on the class board page. And for the previous assignment, I know that I have talked to a couple of you. Sorry, as I said, you guys need to give me a day so we can talk this week. And yes. Cool.
Thanks, Rafa. Rafa Ghoshan Welcome. Sean, it is figuring in a space. Not the figure in a space. Figuring a space. The translation is extremely bad. And you don't notice it until you go through it. Hopefully Robin had some plan to retranslate it and publish it in conjunction with the manuscript, the unfinished manuscript Shatlin left behind after his death, the enchantment of the virtual. So hopefully at some point they will be out.
I have the download version of it. I can put it. Oh, OK. Steven has it. You can put it online. OK. So if you guys don't have any questions, discussions, let's get into our today's course. So I'm going to skip that because some of you left at the end. There were some technical materials at the end of the last session. I'm going to skip that and hold it up until you guys have watched the whole of last session,
and then I will resume that part. So just to give you, again, kind of a summary of what we're doing. First session of the computation module, I introduced the historical stories and debates behind the emergence of computability theory, known as Church-theory thesis. All the debate surroundings, it's a little bit elaboration of what computability means in terms of lambda definability and lambda calculus
and effective this whole idea of isomorphism or equivalence between effective calculability and general recursiveness, which again was a center of debate between clean Godel, Turing, Then in the next, in the previous session, we talked about the kind of a strong interpretation of the Church Turing thesis, and then we introduced a different, because as I said, Turing in his 1936 paper, while he introduces, you know, his classical Turing machine, he also leaves
is a room for improvement of Turing machine and alternative paradigms of computation, precisely because computability theory is not properly speaking a theory of computation. It's not informatics as such. And so I introduced a classical Turing machine, and then sequential interactive machines, which is a kind of a refinement of Turing machine, the I.O. systems, then kind of persistent Turing machines, the ones that have not only interactive component but also history of the states.
And then I introduced the corresponding models of algorithms for these, which was for the So the classical Turing machine, you have classical sequential machine, sorry, classical sequential algorithm, wherein it's just basically a state transition, can be understood as a closed system. It accepts discrete input, goes through the state transitions or computations, throughout the computation. The system shuts up the environment, and then it yields discrete outputs. And we have intractive sequential algorithms, the refinement of the Turing machine corresponding
to sequential intractive machines. And these are, as I said, they come in weak type and a strong type, a smaller step, and weaker smaller step algorithms, and stronger smaller step algorithms. The ones that is basically between states, they accept streams of input. And the ones that throughout intra-step, they accept or admit streams of inputs. And as I try to formalize, these two weak type and strong type of smaller step algorithms are completely, fundamentally covering fundamentally different problems.
And weak type does not cover the problems and behaviors that the strongest of algorithms, the intra-step one, covers. Then I talked about, then inside within this schema of refinement of models of algorithms, sequential algorithms, from the very classical conservative one to interactive ones, I tried to what Tal was saying. I tried to kind of break apart and deconstruct this whole idea of interaction. Because once we say interaction as computation, you can get a very impressionistic idea of this, namely interaction as communication. Oh, we have a dialogue, and then that's called interaction,
so it's computation. But the whole idea is that once interaction is formally understood, and that's one of the job of computer science, is that you understand it is, you encounter extremely subtle problems in definitions, in whether your model of interaction covered these behavioral problems, the behavior of the system or not. And we talked about, you know, the varieties of scenarios that you can have in interaction, whether the choice is made by the environment or the system, whether the person is the player or the opponent, whether your queries and responses have
isomorphic of type, so on and so forth. So the whole point was to deconstruct this interaction so we can at least get rid of this, again, this kind of impressionistic, intuitive, common sense idea of interaction. Now with that said, now I'm going to break apart this history of interactive computation, which is at the center of contemporary theoretical computer science, apart, cover each section, and then converge them together toward interactive theory of computation. And then from that point, move to our third module,
the relation of this to language, AI, mind, social computation, concepts as computational spaces, so on and so forth, semantic complexity. So the map of our, basically, progression is something like this. One second. ! Yes? I have a quick question. Sure. Okay, so you spoke of interaction as a model of computation. And so what I'm asking, these are all some kinds of variations of the Turing machine.
What I'm asking is, is there a different abstract machine or is Turing just the most general one? You see... And to continue, the question is, is this interaction inter-step model can be translated eventually to a Turing machine? I guess that's what I'm... Okay. You see... That's right. The power of a Turing machine, it covers, as we talked about, what is computable, functions that are computable. So computability is still in computer science is kind of a universal
criteria and is an important one. But the weakness of it, other than all of this whole idea of whether it covers some informatic, because the whole idea is that the computation at the deepest level is about physics of information in the sense of mapping, transformation, flow, and conservation of information. And the whole idea is a Turing machine, at least in its classical sense, does not cover so many ranges of these informational behaviors, informational transformation,
formation conservation, so on and so forth. So, interactivity in a kind of precise technical sense was introduced to cover these behaviors. But also there is another weakness in Turing machine and that is really that, precisely because the Turing thesis, computability theory, is based on the study of functions, canonical mathematical functions. And canonical mathematical functions are extensional objects. Now, and again, this is a center of, again, kind of lively debates in theoretical computer science
these days, is that whether we can make a model of computation that is not restricted that is not restricted to functions but behaviors, because behaviors are processual, whereas functions are different. And for processes, you need to have a canonical definition, confluence of notions of process involved in process. You need to have intentional computation, intentional versus extensional, not intentional less about, but intentional with S, S-I-O-N-L. And this becomes the motivation behind the development of interactive computation.
So with that said, the goal is to do two things. One, come up with a confluence of notion in process-based computation, in interactive model of computation that can be merged with theory of computability, also known as Church-Turing thesis, namely Turing machines. So it's not to do this simply diverging from Turing computability, but creating a model of computation that also covers Turing machines. in a sense, Turing machine becomes a special case of a general model of computation
without excluding Turing machines. But this has also been, yes, so what the general machine. But also, some- Is this possible? I mean, the genius of the Turing machine was that it captured, maybe I'm wrong, or possible algorithms, maybe, or functions, or I don't know. I mean, that's the genius of it. So what I'm asking is, don't you need to invent? Are they trying to invent a new machine? That's what I'm asking, a new abstract machine. JOHN MUELLER- Yes, so that's what I was going to say. That, yes, so they are also going, they are talking about, but this is far from, I don't think
that it's going to happen soon, but nevertheless, they are making progress. The so-called interactive machines. Interactive machines are alternative to Turing machines. And they have the general recursivity criterion, but they don't have and they can compute functions that are not computable for Turing machines. But for that, and that's basically the center of this whole module and the third one, is that first they needed to develop conceptual tools, resources. How can you logically, in fact, talk about these kinds of machines?
How can you logically model them? How can you understand the problems arising in interaction where a classical Turing machine cannot cover? And this, as I will show the map, it basically came from three directions, these kinds of problems in the classical Turing machine had difficulty to handle. Multi-agent, a study of multi-agent systems, a study of concurrency and concurrent problems, a study of logical problems. Precisely because when you look into the development of church thesis, effective calculability, It is highly, it's strongly derived from some basic principles of classical logic and structural
rules where you have so many of famous structural rules and the resource unconscious allowing you to develop it in this thesis in this direction, lambda definability. If you have, for example, something like resource sensitivity of logical connectives, if you have something like kind of a very kind of a constrained structural rules or suspension of a structural rules in logic, you basically are not capable of developing or defining
computation in the sense that, for example, church does. It completely gives to a kind of a different model paradigm of computation with different logical properties, with different mathematical properties, with different models of programming. And again, this is something that we talked about. So the best way to put it, here is the map. Well, you're looking for it. Would it be accurate to say that both what Tal is describing as the power genius of the Turing machine and what you're sort of outlining as its limitations with respect to an interaction machine
is that the Turing machine exhibits or at least is able to facilitate the illusion of exhibiting causal closure that it makes like, if you look at Max Tegmark computational multiverse theories that you could have a master Turing machine plus all possible streams of input, all possible symbol strings, and that this encapsulates all things that could happen in the all-nothing because everything can be represented as a symbol string moving through a Turing machine, whereas the interaction model presumes an outside computation interacting with its outside. Either another computational process, multi-agent concurrency are all about presuming any given
computation to have an exterior that can't be reduced to it? Yes, we talked about this, I think, at the beginning of the previous session and at the end of it. This idea of approximation. The closed one approximates. Even when you introduce Oracle and I.O. systems, it's an approximation. But the whole idea is that approximation, as we talked about, doesn't really cover some of the problems arising in interactive, you know, transformation of information in the interactive regimes. For that, precisely because the logical mathematical fundaments of Church-Theoring thesis are incapable
of indexing and covering the kind of novel correspondences between rather anomalous or strange logical mathematical structures, objects, phenomena behaviors that can be found in interactive regimes. I mean, the problem is just, it's not simply the idea that, for example, interactive in physical systems or any kind of model of interaction has, like, these complex behaviors, resource sensitivity, so on and so forth, that a Turing machine cannot really genuinely represent
and cover. But really, at the deepest level, at the level of logical math, the correspondence between computation, mathematics, and logics, the kind of phenomena, the kind of objects, the kind of behaviors that are involved are also different from the ones that are involved in development of Turing machine, Church-Turing thesis. And this would be the third and the final emphasis of our module and covers and extends toward basically the whole of the third module, where we introduce linear logic, semantic
games, functional programming, the so-called Howard-Curry Lambic isomorphism, which is really this reappropriation of Brouwer's constructivism that shows that there is a fundamental correspondence at the deepest level between proofs, structures, proofs as objects of logic, structures as objects of mathematics, and programs as objects of computation. And these are studied under, for example, game semantics and linear logic.
As I will talk a little bit today, some of these problems that arise in the interactive regime and the way that classical logic and kind of effective calculability in mathematics are developed are fundamentally sufficient to study these phenomena, these correspondences, on these correspondences that computer science basically needed to wait until the invention of linear logic, or game semantics, or judgment calculi, or kind of like a really refined constructivism, in order to be capable of really talk
about these interactive behaviors, at least at the logical mathematical level. So, as you see, this is kind of the map of our progression. Previous session can be understood simply as deconstruction of interaction, kind of a contrastation between interaction as computation and the Turing model of computation in the sense of computability theory. Now what we are going to do is that we are going to develop a rather robust and broad
theory or interactive theory of computation. Specifically speaking, the way that interactive theory of computation was formulated in computer science was coming from three different directions. The study of multi-agent problems, and I will talk about this today. Classically, multi-agent problems were first introduced when people trying to study, for For example, uncertainty principles, decision problems, epistemic modeling, coordination of action, communication, all sorts of game theoretic models in multi-agent settings.
Settings that involves more than one player. Because one player games are a state transition, simply kind of a classical Turing machine. But once you have the multi-agent, once you have more than one player, the scenario will become different. And we talked a little bit about this last session in terms of interactive of at least games that involve with two players. And that instantly introduces the two key notions of interactions, queries and responses, assertions and questions, the game of giving and asking for a reason, confrontation of
polar actions, the so-called interaction. And then obviously after that was introduced games involving more than two players, and they are also fundamentally different. In fact, polar two-player games are in fact special cases of general multiplayer games. But this But this is something that we don't talk about today. We can't talk about it until I introduce linear logic. So the first is historically coming from the study of multi-agent problems. The second kind of trend or trajectory
that was key in emergence of interactive theory computation was the study of concurrency problems. Concurrency problems, historically speaking, was introduced more in the field of modeling and engineering. Really the main figure behind concurrency, study of concurrency problems, is Karl-Adam Petrie. Petrie was this genius from a really young age, started to, I think, age 13, started to think about problems that arise in parallel systems. For him, it was chemical reactions. Inconcurrency problems,
it covers a wide range of problems and behaviors that are key in understanding the theory of of computation, such as theory of process, what is a process, how processes behave, how processes can be synchronized. This is the scheduling problems. Given that some processes, the way that they move and they interact are completely asynchronous. Synchronicity is a special case. In order for us to think, really, interaction, we need to understand the general condition is an asynchronous game, asynchronous interaction between processes. Then also concurrency, another really key concept behind the concurrency problems is
resource sensitivity. of resource sensitivity to computer science came from concurrency, which was really a hot topic in system engineering especially during the 40s, 50s, 60s. And so this is also I will cover it today. In order to talk about concurrency problems, I will just introduce at this time Petri's Nets. of you are familiar with Petri Nets? Are you guys familiar with Petri Nets? I can't see the chat box because the screen is on. None? Are those like JARDS proof nets or something different?
No, Petri Nets are completely different. OK. Yes. Done now. Petri Nets are just like flow charts. But as I will talk about, they are, you know, even though the really intuitive idea of how the heteronets work and how they graphically represent parallel systems and current processes, and this hasn't been, you know, this wasn't really realized and discussed until, for example, like 20 years ago in computer science. The computer scientists realized that behind this kind of intuitive graphical representations
of PET-3Nets lies this really deep and profound complex understandings of concurrency. And really kind of it covers and implies certain problems that are still actually enigmizing computer science. They're hard to solve. So this would be the concurrency problems, another trajectory that led to interactive theory of computation. Then the third one, which is really our key one for concluding this module and starting and going through the next module are logical problems.
And you can think of this in terms of the difference between a structural logical systems, for example classical logic and substructural logics, logics in which one or two of the structural rules are suspended, either potency of entailment or monotonicity of entailment, contraction and weakening. This, the logical problem aspect, also itself came from at least in three directions. Refinement of proof theory in logics, a study of semantics in logics,
a study or analysis of sequence. Sequence, as I briefly talked about, but something that I will elaborate and formulate precisely in a forthcoming session. Sequence are basically judgments. The invention of sequence calculus is due to Gerhard Gensen. Gerhard Gensen developed is a device called a sequent calculus that allowed to, basically, what is a sequence? In traditional, before sequent calculus, the chain of deduction, the chain of judgment,
you had these kind of like a Fregean operators, Fourierian kind of logical notations, where each step of deduction is an unconditional tautology. Where, but Gerhard Gensen introduced, once he introduced the sequent calculus, what is sequent calculus? The basic form of a sequent calculus is gamma implies delta. a symbol gamma, a turnstile, and a symbol delta. You have antecedents, gamma, you have turnstile, the symbol of implication or entailment, which
is the key concept of logics, and then you have a consequence. You have premises, you have judgment, you have hypothesis. And this way of formulating a deduction allows you to individuate and carefully decompose the unconditional tautology of the previous Freedian notational system into conditional tautologies. So you have steps of sequence. You can analyze how the chain of deduction is individuated, is progressing. I will talk about this elaborated in more details.
So this was another part of this logical problem that was key in the development of interactive theory of computation. of judgment, of the structure of judgment or sequence. And the whole idea of logical problems can be summed up, and this is why it is really – I mean, the first two, multi-agent system and concurrency system, are keen development of interactive theory of computation. But really the formal core of it, basically what unified all of these three, allowed kind
of like this grand unified, grand unification scheme was in scientists study reinterpretation of correspondences between objects of logic, namely proofs, objects of mathematics, namely structures, and objects of computation, namely programs. This is very, again, I will talk about this in much more detail in the next session. This is a so-called Curry-Howard-Lambeck correspondence, or isomorphic.
This schema, this fundamental correspondence between proofs, structures, and programs, proofs as in linear logic proof theory, the structure as objects of category theory, and That was the invention of Joachim Lambeck and programs as types. This correspondence, this isomorphic between logic, mathematics and computation allowed reinterpretation of computation at the deepest level, namely understanding of computation as intraction, as logical intraction.
Within this schema, we will talk about linear logic. We will talk about logical gains. We will talk about operational gains, the relation of category theory to computation, proof theory, judgment and calculi, and finally, that this whole schema can be seen as some sort of refinement of Brouwer's constructivism. Basically, the entire schema of how Corey-Howard Lambic isomorphism is in fact simply a refinement of Brouwer's intuitionism. And this is really the centerpiece of Girard's linear logic project, which puts computer science kind of in this direction,
reinterpretation of computation and logical phenomena at their deepest levels that cover a range of wide variety of problems and behaviors that you can see in multi-agent systems, in concurrency systems, resource sensitivity, so on and so forth. So once we have done, once we converge these multi-agent problems, concurrency problems, logical problems, we can talk about more comprehensively about interactive theory of computation. And that puts us in the direction of why is it so important for construction of human-level AI, understanding of how language functions, both natural language
and formal languages. Why is it a key in a study modeling, talking about complex systems on the subject of the first module? And why is it really in theory, in tractive theory of computation, finally gives us an answer to what is exactly mind, social mind. Can it be understood? And that would be basically kind of like one of the key goals of our third module, presentation
of a computational interpretation of mind as language. So this is kind of like the map of how we are progressing and where we are. I'm going to talk about multi-agent problems and concursity problems today and next session, logical problems and extend this to the third module and cover the stuff that I briefly mentioned today. Any questions, discussion or anything before we move forward? Nothing.
Unconditioned tautology? Did I hear that right? Yes, unconditional tautology. It was the case before Gensen. Gensen put constraints on this tautology, made it conditional, precisely because sequence are individuated progressively, and then for them you have constraints of judgments for each step of deduction. Which is sort of why, I mean, I'm just sort of reading through about sequent calculus again, and it's, so each of the lines in the proof would be a theorem, like in Hilbert's dot, and so you're tracking
a set of theorems within first order logic or whatever logic it is that you're reasoning using sequent calculus in as opposed to like in a normal style proof all of the lines collapse into being a single theorem like you have worked out and proved one whereas in a sequent calculus like at each point in the line because it's conditional on everything previous it's more like you've moved from one theorem to the next is that tracing is absolutely a correct Yes, you can track. Luca Frazier, you're familiar with Luca's work, right? Any of you? Yeah. Luca has this fantastic, superb essay. I really recommend this. In fact, I should have included it as kind of a recommended text for a third module.
As Back to Anne Fang. It's on her academia page. You can see it. She talks about this historical progression of the kind of a classical friggin tar schema to introduction of sequins and how Girard understood to refine Ginson's sequin catalysts. And she says, she makes a really fantastic way of formulating philosophically, kind of continental vocabulary of sequent calculus, basically what is exactly sequent calculus. The good concepts, if you are familiar with, good concepts to understand what a sequent
is, is the concept of concretization in Simonda, Gilbert's Simonda. It's basically some sort of individuation schema. You can check concept of concretization online in Simondon's work. The schema of concretization is like the interaction space of oil, like for example, oil and water in the engine that he talks about, and the sort of sum possibilities that's reduced to neither and it has like it's that which exhibits boundary conditions yes under which yes works okay yeah
okay nothing no discussion should I move forward Sean any questions you have been Okay, go on Adam. I'm not sure how much we want to open this up, but it's really interesting to me the way that a program was conceptualized in a very black box way, which you guys have been talking about from various angles, right? So it's like, here's a program, here's all its inputs, it goes and runs. And it seems like there's at least some parallel, though I couldn't trace it historically necessarily, between sort of that idea and this very idea of like these ideas of technology as a very
separate thing, as very separate from society as you have a little bit of engineering sort of more like the idea of technology itself is this separated thing and you have this separated class of engineers that manage it. It's not something that's part of a social process of interaction. It's something that you just go and solve that problem as a formal engineering problem and then we tell you, we solved it for you. It's all good. And, you know, it seems part of that, or it seems connected to that same general sort of thought about it. Absolutely, yes. Or tool making.
And then the practical day-to-day sort of use of computers too, it's only really, you know, you had increasingly complex sort of socio-technical systems emerging, but it really broke out into the open with the internet, then you've got this really obvious sort of software based system which is completely reliant on interaction even though there's many other systems preceding it. So sort of the deficit there in the theory then gets flushed out into the open. Yes, absolutely. As I said, the interactive theory of computation had focused on two difficulties, two shortcomings.
one practical complications that arise in real situations that involve interaction, scheduling, resource sensitivity, deadlocking, so on and so forth. But also, once computer scientists look into these problems, they see that the way that the logical mathematical foundations of computability are set and where they are coming from, they are fundamentally insufficient, in fact, to index these behaviors. So exactly like any kind of breakthrough in any scientific field, they had to come, and
And this is the current step. They had to develop a fundamentally different conceptual regime to be able to index these phenomena and talk about them, to find their corresponding logical mathematical structures. And that wasn't really possible until Girard invented linear logic. The contribution of Girard is like a wacky figure. It's probably the wackiest figure that you can ever see in any scientific field. You should even read his papers how wacky they are.
It's just annoyingly, outputingly, badly humorously French. But his contribution is absolutely massive. is getting more and more accepted as the best tool, the best framework, logical framework to study computation at the deepest level, to in fact develop alternative models of programming. Okay. Okay.
So, before starting the multi-agent system problems, because I'm using a few terms that some of you guys might not be familiar with, I'm going to introduce a little bit, just but just very, very briefly, very rudimentally, sorry for this, diverge to explaining computational, I'm sorry, complexity classes for Turing computability, Turing model of computation, so-called P versus NP complexity, just so you get a very kind of a broad idea of what these things are. It's just very simple, but nevertheless I have to talk about it because I know that some
of you probably are not familiar with this. Let me just get this. God, I'm so disorganized with this. OK. Very briefly, one, we know that what can be computed at all is the subject of computability theory. In other words, here we deal with solvable problems, but ask how hard they are.
Some example of such problems can be said as to be this kind of a classical logic formula, a theorem of classical logic. is the short, we can say that is this a theorem of classical logic? This becomes our problem. Another problem that we can talk about how hard it is to solve it is the problem, the famous problem of shortest path from here to the central station or graph reachability problem. We are not really interested in such a specific problem instances, but rather in classes of problems,
parameterized by their size. n belongs to N, a capital N, natural numbers. For a given formula length equal or less than n, check whether it is a theorem of classical logic. Find the shortest path between two given vertices on a given graph with up to n vertices. Or is there a path equal or less than k? Finally, we will only be interested in decision problems, problems that require yes or no as an answer. Problem will be defined like this. So these are basically the criteria of defining complex classes in canonical theory
of computation. how hard it is, decision problems, reachability problems or accessibility problems, time problems, space problems, space, simply memory, time, how much time does it take for a program to execute and process and input. So instances of reachability problem, directed graph G with vertex and E two vertices, V and V prime belonging to V. Question, is there a path leading from V to V prime? These are kind of classical problems of reachability.
When it comes to defining complexity measures in terms of these problems in accordance to canonical theory of computation, First, we have to specify the resource, with respect to which we are analyzing the complexity of an algorithm. First one is time complexity. How long will it take to run the algorithm? And the second is space complexity. How much memory do we need to do so? Then we can distinguish worst case and average case complexity. Worst case analysis means how much time memory will the algorithm require in the worst case. Average case analysis means that how much will it use on average.
But giving a formal average case analysis that is theoretically sound is difficult. Where will the input distribution come from? The complexity of the problem, in this sense, is the complexity of the best algorithm solving that problem. Another key topic in defining complexity classes in measures of computational complexity is the so-called Big O notation. What is exactly Big O notation? Big O notation simply mathematically describes the limiting behavior of a function when the argument tends toward a particular value or infinity.
For example, take two functions, f mapping one natural number to another natural number, and again, g mapping one natural number to another natural number. Think of f as computing. For any problem size n, the worst game time complexity, fn, this may be rather be a complicated function. Then think of g as a function that may be a good approximation of f that is more convenient when speaking about complexities. Basically, the video notation is a way of making the idea of a suitable approximation mathematical precise. So sometimes when you're dealing with complexity classes
and solving the problems, it comes down to define these complex classes according to approximations. And this is really the core idea behind BTO notations. For example, we say that Fn is an O of G of n if and only if there exists an n0 belonging to natural number. And a, something is missing here. I've forgotten to put it there.
And c belonging to positive real numbers, such that f of n is equal or less than c.g of n, for all n greater or equal than n0. That is, from a certain n0 onwards, the function f grows at most as fast as the reference function g. Another topic behind computational complexity is tractability and intractability, so-called combinatorial explosions and stuff. Problems that permit polynomial time, namely the time
that the program takes to process the size of a certain input are usually considered tractable. Problems as required exponential algorithms are considered intractable. The polynomial algorithm running in n exponent of 1,000 may be a lot worse than an exponential algorithm running in 20 to raise to n divided by 100. However, such peculiar functions do not actually come up with real problems. In any case, for every large end, the polynomial algorithm will always do better. It should also be noted there are empirically successful
algorithms for problems that are known not to be solvable in polynomial time. Such algorithms can never be efficient in general case, but may perform very well on the problem instances that come up in practice. As I said, one of the key topics in talking about complexity classes in computation are decision problems. A famous example of decision problem is traveling salesman problem, or TSP. We have n cities, distance from each pair, k belongs to a natural number.
Then the problem is, is there a root equal or less than k visiting each city exactly once? A possible algorithm for traveling salesman problem would be to enumerate all complete paths without repetitions and then to check whether one of them is shorted up. The complexity of this algorithm is video notation of factorial n. The slightly better algorithms are known, but even the very best of these are still exponential. This is just a fundamental problem. Maybe an efficient solution is impossible. Note that if someone guesses a potential solution path, then checking the correctness of that solution
can be done in linear time. So checking solution is a lot easier than finding one. And I will talk about this, that basically this whole idea of the checking solution is easier than solving a problem, finding the solution. Basically the idea behind N versus NP. in defining complexity classes in computation. Secondly, in defining complexity classes in computation,
we have deterministic complexity classes and non-deterministic complexity classes. Deterministic complexity classes, A complexity class is a set of classes of decision problems with the same worst case complexity. The measure for it is time f of n is a set of all decision problems that can be solved by an algorithm with a runtime of big O of f of n. For example, reachability belonging to time square n. We have also a space in memory.
A space of f of n is a set of all decision problems that can be solved by an algorithm with memory requirement in big O of f of n. For example, TSP belongs to a space n because our brute force algorithm only needs to store the root currently being tested and the root that is the best so far. These are also called deterministic complexity classes because the algorithm used are required to be deterministic. And we have, as I said, non-deterministic complexity classes. Remember that I said checking whether a proposed solution is correct is different from finding one. It's easier.
We can think of a decision problem as being the form. Is there an x with the property p? It might be already in the form originally. For example, is there a root that's short enough? Or we can reformulate it as, is a formula phi satisfiable? Is there a model m so that m entails phi? When it comes to non-deterministic classes, the time measure and a space measure becomes like this. n time fn is the set of classes of decision problems for which a candidate solution can be checked in time big O of fn. For instance, TSP belonging to n time n because checking whether a given root is short enough
is possible in linear time. Just add up the distances and compare it to k. Accordingly, we have n time of f of n. The space complexity of non-deterministic computational class would be then n space of f of n. But the whole thing is that why are we called them non-deterministic complexity classes? There are two ways of interpreting non-determinism. Think of an algorithm as being implemented on a machine that moves from one state, memory configuration, to the next. For a non-deterministic algorithm, the state transition function is under-specified,
more than one possible follow-up state. A machine is set to solve a problem using a non-deterministic algorithm if and only if there exists a run answering yes. We can think of this as an oracle that tells us which is the best way to go at each choice point in the algorithm. This view is equivalent to interpreting non-determinism as the ability to check correctness of a candidate solution. All the small oracles along a computation path can be packed together into one big initial oracle to guess a solution. Then all that remains to be done is to check its correctness. Finally, in defining complexity classes of computational complexity, we have P and NP,
which is basically the most important complexity classes. From our discussion we have so far, it means that P is the class of problems that can be solved in polynomial time by a deterministic algorithm, whereas NP is the class of problems for which a proposed solution can be verified in polynomial time. So to sum up, complexity theory is part of a theory of computation dealing with the resources required during computation to solve a given problem. This is a space and time. And if you remember, we said that resource sensitivity in canonical theory of computation
in the sense of Church-Turing thesis is not really a fine-grained resource sensitivity. It's a general resource sensitivity that is about really time, space, and easy versus hard classification of problems. It's not the kind of resource sensitivity that, as I will talk, is covered in, for example, multi-agent systems, concurrency, or for example, linear logic. It's not fine-grained. It's just a kind of a general resources. The most common resources in defining complexity classes
in computation complexity, as I said, are time and space. Time, how many steps it takes to solve a problem, and space, how much memory it takes. There are, of course, other resources that still can be discussed in canonical theory of computation. For example, how many processors are needed to solve a problem in parallel. In addition to resource and defining complexity classes in computational complexity, there is another criterion, and that's decision problems.
Much of complexity theory deals, in fact, with decision problems. A decision problem is a problem where the answer is always yes or no. The is-prime problem, for example, given an integer written binary, we turn whether it is a prime number or not. Decision problems are often considered because an arbitrary problem can always be reduced to a decision problem. The complexity class P is the set of decision problems that can be solved by a deterministic machine in polynomial time. This class corresponds to an intuitive idea of the problems which can be effectively solved in the worst cases. The complexity class NP, on the other hand, is the set of decision problems that can be
solved by a non-deterministic machine in polynomial time. This class contains many problems that people would like to be able to solve effectively, including, for example, Boolean satisfiability problems. All the problems in this class have the property their solutions can be checked effectively. Their solution can be checked effectively, whereas in contrast, find it one. So the question of whether P is the same set as NP is the most important open question in theoretical computer science. Our daily experience is that it is, as I said, harder to solve the problem than it is to
check the correctness of a solution. Is this experience merely a coincidence or does it represent a fundamental fact of life or property of the world? And precisely this is the intuitive idea behind P versus NP. Could you imagine a world in which solving any problem is not significantly harder than checking a solution to it? These are all important questions in computer science. Would the term solving a problem not lose its meaning in such a hypothetical and impossible ... as is from the perspective of computer science world? So ... Are there checking problems in NP?
Checking problems in NP? Are there decision problems in NP? That's non-deterministic. Sorry, say again? As I said, those are the non-deterministic decision problems. So the non-deterministic decision problems are checking problems that are in NP, Yes, but that becomes basically the whole controversy that whether it is P or NP. That becomes basically decision problems. Yes, there are, yes, you can talk about it, but that's, I mean, I think the refined way
of putting it. There's a funny structure of the problem, Jake, that it's really interesting what they've been able to prove. They've been able to prove that a whole class of problems, that if you could solve one of them, and traveling salesman is one of them, you can solve one of them. Then you can solve all of them. Then you have a possible solution for this whole chain of problems. And that would show that, so if you can place one of them in P, then that shows the P equals NP, or would show. Yeah, because you see, there are subsets relations between these complexity classes, between P and P, you know, a space-time in different scenarios, a space-time complexity in different scenarios.
And in fact, that was, I was going to suggest you guys look into it, because we don't have time to really cover this, is that there is a subset problem. So as I'm saying, if you can't find a solution for one, and you are essentially finding a solution. But again, this is kind of a theoretical controversy. It is not far from completely solved. I mean, sorry, it's far from being completely solved. And so is that, is it because the problems are literally convertible to each other, such that if you found an algorithm for one of them, then you would actually have the algorithm for all? Or it just is impossible to face? JOHN MUELLER It's assumed to be so.
It is assumed to be so. Well, I think it's a little stronger than that, Reza. I think there's been proofs that if you can solve one, then with an extra problem .. Yes, I'm familiar. I've checked some of the papers. But even when people talk about .. Sorry, go on. Sorry, I just, other alternative, is it that they are literally convertible such that once you had the algorithm for one, you had it for all of them, or would it just mean that if you had found the algorithm for one, there were polynomial time algorithms to be found for the others? Would there still be more non-trivial work to be done to solve, to find a time?
I think it's more of the second case, to be found. OK, OK. Yeah, I have seen some papers and stuff, but still, so many computer scientists believe that some of these proofs are kind of either shaky or not covering all of the things. But yes, I understand. No, I completely understand that, especially people who work at this intersection between quantum computation and a Turing machine. And so many problems of P versus NP arise in this kind of polynomial times, and how easy or hard to solve the problem, and come up with proof of these things.
But just kind of like at least what is going on in computer science, still some computer scientists are suspicious of some of these proofs. OK. And then just one other question. So when you say on the lens of interpreting non-determinism, when you say we can think of this as an oracle which says, like, so, you know, at each point in a non-deterministic algorithm, you know, at a choice point, you have, like, more than one state you can move to. Like, what is the, then, which one is the best result in the shortest path? Like, what is that, what is that oracle in that sentence? Is it the non-deterministic algorithm that always does it
in the best possible way or is it something else that I'm not seeing? Would it be the quantum computer? I think it's a non-deterministic algorithm when we are talking about this. I still can't, sorry, I couldn't really gut the gist of your question. What's the non-deterministic oracle that gives the input that lets you then solve it in NP? Like how to conceptualize that non-deterministic oracle? Is that what you're asking, Jake?
Yeah, so like, say that, are you sort of referring to, like, iconically the quantum computer that can look at all of them in parallel, and so the one that, it's the shortest, the sum over paths is what happens in the macroscopic world that we see? Like, is that what we're kind of referring to with the Oracle? Well, Oracle, yes. So the whole point of the Oracle is that it doesn't essentially need to abide by the same constraint as that of a Turing machine. Namely, it can admit noncomputable functions. So basically any kind of... But the thing is that quantum computation, and that's one of the, again, the so-called
proofs, quantum computation, I don't think that falls into this oracle completely right, because quantum computation shown to be precisely abides by the constraints of computability of the Turing machine. Namely, it does not violate the computability criteria of a Turing machine. It does compute problems that are not computable in polynomial time. So from that aspect, yeah, it can be understood as a kind of a oracle. OK.
Okay. So I just wanted to talk about this P versus NP, so you get kind of like at least the kind of you should go and check articles online. There are so many good articles about this P versus NP stuff and complexity classes of classical theory of computation.
Just wanted to introduce these two terms, because I will refer to them throughout today's course. So let's start with our multi-agent systems. You see, multi-agent system traditionally, historically, simply was the understanding of conversation, interaction in a very intuitive sense. What is really interaction? It's confrontation between some actions. with these actions need not to be understood synchronously. When you have different players with different actions, with different behaviors, you have different scenarios
of how these players can confront one another. And precisely because of that, certain problems arise. the knowledge of players about one another, the decision problems, the problems regarding perspectivality. And these are the key concepts in the study of multi-agent systems. What is perspectivality? You see, when we are talking about a one-player game, one person, you have just one perspective, very intuitively. But, obviously this constrains your modeling, your presentational capacities.
You are not really capable of solving effectively problems, especially epistemic problems or knowledge-based problems that require multi-perspectives onto the same problem. It's like this, you have this intuitive idea again in mathematics, kind of famous that, for example, classical mathematical objects, the way that they are constructed can be understood as a very estate-based way of construction.
You have one perspective operator. When you increase these perspectives, you can again think of this as how we perceive the planet Earth. If I'm just walking on the planet Earth, one perspective, I see no curvature. I don't see any geodetic path, I only see a straight line. But if you pluralize these perspectives, and the perspectives representing agents, and turn them into satellites that move around the planet, then you see a straight path as geodetic curvatures, geodetic paths. And that gives you a different picture of your problem, different picture of your object.
So multi-agent systems has this capacity to understand and deal with novel problems that non-agent based systems can't. At least again traditionally in the study of multi-agent systems, the focus was always on two-player games, two-player scenarios. And only later it became more of true multi-agent system, namely a collection of agents,
that interact with one another asynchronously, meaning that the criteria of synchronicity, of how they confront, of how their actions confront one another, not need to be synchronous, not to be coordinated. Obviously, we see these problems and the kind of novelty of behaviors that arise in asynchronicity versus synchronicity in, for example, our natural environment. Usually, for example, again in our civilization games or in prey predator and asymmetric warfare, we see that the predators who behave asynchronously are much more scarier than the ones that behave
synchronously. Basically, they simply react to our actions. These are because they cover time criteria. The processes are not about what or about when they exactly target us. And these are all covering range of behaviors that synchronous, for example, games can't cover. Synchronous models can't cover. So multi-agent systems started with these problems, asynchronicity, conversation, in this rudimentary phase it was about just about two-player games, player opponent system environment,
separate clients, so on and so forth. So this whole idea of conversation or interaction in an intuitive sense, communication, is a key in what and was the key in the study of an emergence of the study of multi-agent systems. The first step in modeling conversation, as I said, is a good notion of the state, hence the static component of the total enterprise. Let's think of this whole notion of conversation and a static component and how this is related
to solving problems that involve knowledge or epistemic modeling of your total system, decision problems, accessibility relations between agents, so on and so forth, in terms of an example. Pick up, for example, a restaurant scenario. Zoe, the child, John, the father, Mary, the mother, ordering food. The child orders meat, the father orders fish, the mother orders vegetarian. Then the waiter comes with three dishes. He asks who has the meat, the child answers, and they put the plate on the table in front
of the child. Then he asks who has the fish, the father answers. Then, for the third question, he doesn't need to ask any more questions. He has the complete knowledge of how the sequence of estates needs to grow. Obviously, the vegetarian would be in front of the mother. Now, in this simple scenario, the initial information state of the waiter from the kitchen has six possible arrangements for three dishes over the three family members. As far as the new waiter is concerned, all are options, and he only knows what is true in all of them. The new information that the child has the meat reduces this uncertainty to only two options, fish vegetarian or vegetarian fish for her father and mother.
Either way, the waiter now knows that the child has the meat. Then hearing that her father has the fish reduces this to one single option. The waiter has complete information about the correct placement of the dishes and does not need to ask any further question, even though he may have to perform an inference to make this vivid to himself. So the first idea of conversation, the true conversation multi-gen systems, you can think of it as agents, as machines, as human actors, is that conversation allows us to perform
effectively a state transitions, moving from a state without having the kind of epistemic access that is required, for example, in traditional non-interactive computational theory. Precisely because the multi-agent systems solve some of the, you know, gives us this whole idea of conversation, gives us epistemic access. We can proceed to uncertain, basically we can overcome uncertainties and decision problems that might arise in our systems, and a classical, for example, sequential system cannot solve
them, precisely because it's multiperspectability, accessibility relations, that it opens up, so on and so forth. In the study of multi-agent systems, the way that usually this idea of conversation, this intuitive idea of conversation as a model of epistemic access and accessibility relation is presented is via the so-called epistemic logic. is due to Hentika and is really one of the fundamental logical frameworks in the study
of multi-agent systems. I'm going to very briefly talk about the idea of epistemic logic and basically how it's used in the study of multi-agent systems. Now in our examples, we have this. First we have state one, we have six options in terms of who gets which plate. Once the waiter has a conversation with the child, they exchange an information. The waiter knows child has a meat, then the options becomes two, state two.
Then the father has basically the fish plate, and it goes to state three. It doesn't need to know, to ask any more questions. In defining epistemic basic framework of epistemic logic, we can say, we can present it in this fashion, that the syntax has a classical preposition based with added modal operators, ki phi.
I know, sorry, I knows, I is basically your agent, I knows that's phi, and C, J, phi. Phi is common knowledge in group G. So we have a few relations in this framework. We have p, not phi, this junction between phi and psi. We have k, i, phi. i, as I said, is just the index of agent. And we have cj phi. Basically, g is the notation for group.
The state of our informational processes are models for this language, are E triples of M, W, tilde I, is uncertainty relation or accessibility relation, which might be uncertain, kind of a decision problem. I belonging to G and V, where W is a set of walls in the sense of modal logic in a possible world. It's possible states, possible options in our example, so who gets what. The tilde I, the binary accessible to relations between worlds that agents I cannot distinguish
as a viable canvas for the real situation. And V is a propositional evaluation. The fundamental epistemic truth condition for knowledge of an agent is then as follows. M, S entails that the notation of symbol, S entails K, I, phi, if and only if, for all T with S tilde T, M, then T entails phi. This language can define an existential dual of knowledge, not KG, not phi, or J phi.
Agent J considers it possible that phi, plus other useful expressions such as KJ phi, this junction, Kj, not phi. Agent J knows whether phi, basically it's an explanation of the formula. In particular, multi-agent interaction is a crucial feature. For example, in asking normal questions, a questioner Q conveys he does not know if phi not KQ, questioner, phi, conjunction, not kq, not phi.
Moreover, usually he also thinks that the address a might know, which can be as stated as an iterated two-agent assertion, k a, phi, again, disjunction, k a, not phi. So once you have the conversation, basically this conversation provides you with certain epistemic logical accessibilities to your system. It becomes whether, either, or, and. These are all possible scenarios, possible logical scenarios,
modal rules, options, that are unfolded once the conversation between the waiter and the members of the family are initiated. So in this sense, conversation puts in motion and unfolds certain epistemic accessibility relations between agents involved in that conversation. Precisely because of that, it allows us to observe and study different kinds, both effectively
better and also qualitatively different kinds of decision problems, uncertainty problems that might arise in a system. Another, so with having this in mind that conversation opens up or unfolds epistemic accessibilities, and that's modeled by way of epistemic logic of Hentika, traditionally a study of multi-agent systems. But having this in mind, it also interaction of conversation in the intuitive sense in
the multi-agent settings allows us to think about problems that involve information flow and mod update. If you remember last session, I said, you know, when we were talking about the first module, one of our kind of key topics was this idea of model checking. Model checking in complexity sciences requires for you going back and forth between your model and the results and the observations. It requires an interaction that itself part of the complexity.
You can also think about this model update and why is that update is really important. An update cannot be understood robustly, genuinely unless we have a logical account of interaction, of conversation. You can think of this, again, other than model checking. And those of you who are familiar with Brandome's work in terms of commitments, sorry, updating your commitments. Commitment, simply in Brandome's vocabulary, is a kind of refinement of belief. Every belief or every commitment, intentional commitment,
has two parts. Once I have a belief, this belief not only presupposes other beliefs, sorry, not only it implies other beliefs that you hold by virtue of holding the current belief, but also you have this belief by virtue of other belief that basically implied it. So you have your current belief, your current commitment have two parts. One, the space of its future, of its consequent implications, and one is the space of its antecedent implications, the beliefs that led you to your current belief.
So, but once we have a, for example, think of this, that for example, I have some sort of a racist belief, and this obviously comes from somewhere, a set of other beliefs, but also it implies a set of other beliefs, basically leads to other beliefs about, for example, social policies, how I interact with other people, so on and so forth. Now if, for example, I'm open-minded, if I see that there is an incompatibility relation in my belief, if there is a contradiction in my belief, or my belief is wrong, then
how am I supposed to update my entire belief system? Obviously this means that once there is a compatibility and a contradiction in one of my commitments, then I have to go back and basically repair the repertoire of those beliefs that led to my current belief. This idea of repairing commitments, updating beliefs, updating commitments, is also can be seen as a model update. And perfect way of formulating it is via the logic of multi-agent systems.
Obviously, as Brandon says, no one has the complete mastery, global kind of control of his or her own commitments, beliefs. We can only go so far and update our commitments. In order for you to be able to commit this correctly, not only you need to interact with people and engage in a rational conversation, to the game of giving and asking for reasons, but also you need to have a broadening of your control over the tracking of your own
commitments, how basically one leads to another. If we do not have these trackability criteria between our antecedents, current, and consequent beliefs or commitments, we are capable of doing a global commitment update or belief revision. So before moving to this idea of information flow and model update or belief revision. Any of you guys have any question? Because it brought up random stuff. No one? Would, or what would the relationship between
so like example of racist beliefs so like we instantiate a racist belief R and that at least like for some people and maybe not in all instances maybe implicitly in some forces the back propagation of some sort of justifying belief structure like whether it's that you know God blasted people's skin and turned them red or whatever, or like genetic determinism and human biodiversity and whatever. And then on the other hand, when we say we instantiate not are, and that forces back propagation of like,
does that mean I no longer believe in genetic determinism? Does that mean I don't believe that genetic determinism implies racism anymore? And that like forces that kind of way. Are those the same thing when these open antecedent variables, like the need for justifying beliefs pop into existence, or the disruption of existing antecedent beliefs, and the need to find the ramifications of that disruption pops into existence, if that makes any sense. I think from what I got to your question, I think you were talking about whether this whole idea of belief revision, global commitment update system,
repairing your commitment toolboxes, is it like a linear? Is it kind of like it? Or is it you? It's also what the computer science called is a backward chaining. Does it only forward chaining, or is it also backward chaining? I think it basically requires both backward chaining and forward chaining between the commitment and that makes it quite different from the kind of linear progression that you can intuitively imagine. Judgements has exactly as you say, you know, this back propagation, so called backward chaining and forward chaining, going back and forth really, and that's basically what
Hegel calls a determinate negation. A determinate negation as opposed to an abstract negation, resolving incompatibility relations in the sense of retrospection and projection. because the entanglement of our commitments do not fall into this kind of very sequent calculus, allergens and antecedent, you know, implication, consequence. Sometimes consequence propagates their own antecedents, you know, and reinforce them.
Can you say that again? You broke up slightly in that sentence. I said that sometimes consequence propagate their own antecedents and reinforce them. Okay. Yeah, sorry, I'm just sort of visualizing that in my head. So yeah, so we're seeing like forward chaining is like the projection of need, of need for what will be the antecedents of the belief once it's been confirmed. like, yeah, confirmed like a transaction, and now like we are not only have this belief but are sure of where it fits into our revised net of ramifications. Yeah, and you can get a kind of a very actually exciting model of time in this kind of model
of belief revision. It's not only the traditional looking to your past retrospection, but it's also about prospection, looking into the consequences of the future implications bearing on the past. And that's really the core idea of diffusibility, not monotonicity. Right, is that it's possible for these things to be wrong, and that it's this possibility space like in the past of your propositions or beliefs being wrong, which is also your future capacity for new ramifications and revisions. Yes, yeah. Aaron, as a guy who reads sellers and brands,
do you have any question for moving forward? We should keep moving on. I'm kind of like coasting and hungover today. OK. So when it comes to the information flow and model update, another main idea in multi-agent scenario is the level of knowledge of agents about other agents, so that's accessibility relations. For example, think of this scenario. Three cards are given to three agents. Agent one got red, agent two got white, and agent three blue. Each agent can see his or her own card, but not those of the others.
Agent 2 is allowed one question and he asks agent 1, do you have the blue card? Agent 1 answers truthfully, no. Which agent figured out what in this process? If we asked them before agent 2 posing a question, they would say they would know nothing. But if we ask again right after the question, agent one would tell us that she knows the cards. Her reasoning would be simple. She would not have asked if she had the blue card herself. Now all this can be analyzed in words in this kind of, again, epistemic logical framework. But here is how things would look like in this kind of idea of epistemic state transition
in multi-agent systems. The initial situation again has six options, and the uncertainty lines in terms of the knowledge of agents as to the state of other agents indicates what players hold possible from where they are. This is kind of the basic diagram of it. Agent 2's question, seen as informative, eliminates all modal rules or options with the second position B. And then the diagram transforms to this one. We see at once that
in the real world, you know, red, white, blue, RwB, agent 1 has no uncertainty line going out and hence he knows the cards there. We also see that agent 3 knows this as it happens of both RW, red, white, blue, and white, red. Next, agent 1's answer eliminates all worlds, basically all the possible options, with the first position B. And the diagram converges to this. This reflects basically the final situation of the knowledge, epistemic accessibility, between agents. Again, in this scenario, the multi-agent interaction
was crucial. The agents achieved a new level of knowledge that is sui generis. And what is really the sui generis level of knowledge? It's what we call common knowledge. In addition to what they know about the facts of the situation, they also know that the others know, and so on, up to any iteration. And this idea of common knowledge is another key in the study of multi-agent systems and how can you be computationally formulated agents having epistemic access to knowledge of other agents, to the state of other agents. Common knowledge occurs in philosophy, linguistic, economics as a kind of prerequisite for coordinated
action because if you do not have this access to epistemic relations, this common knowledge, coordinated action between your machines, your agents is impossible. For example, there is the work of Canadian mathematician and scientist David Reiter. David Reiter, he invented the situation in Catalyst, which was a massive revolution of robotics. these ideas of how agents interact and how this epistemic action, this interaction unfolds
epistemic accessibility relations, and that brings forth common knowledge, formally understood, which enables coordinated action is an extremely important topic in robotics, especially situation and event calculus. Any of you who are interested in the formalism behind these kinds of stuff, the study of multi-gen systems, the relation between knowledge and action, which I think is absolutely not only important for robotics and AI, but also for any kind of really consequential political
project in fact. How we can scientifically talk about these things is David Rater's famous book, Knowledge in Action. It's an extremely great book. It starts from the basics and moves to our, you know, quite detailed formalistic accounts. So common knowledge occurs, as I said, in philosophy, linguistic and economics as prerequisite for coordinate action. Technically this new notion is defined as follows over our model. Model N, S entails CG phi, if and only if, were all T that are reachable from S by some
finite sequence of tilde i, s steps, as I said, up to an iteration. i belonging to g, m, t entails phi. This multi-agent view may seem far from standard logic in computation, where single agents draw inferences or make calculation steps, but real argumentation is an intractive process. And even the classical history of computation, as I said very early on, Turing emphasized the crucial social character of using computers and learning and conversation. The whole idea that when he tries to formulate a human level AI, in fact, I think it's that
essay called Heretical Machines, if I remember correctly. The whole model is a model of a conversation between a machine child and a teacher-instructor adult. That the conversation understood as a multi-agent interaction allows and enables the computer child, the machine child, enters to cover new behavioral novelties, evolved basically, precisely because of these going back and forth and the knowledge access points that
are unfolding, so on and so forth. Knowledge is just one informational attitude of agents. One can also model beliefs, probabilities, and so on using a broader variety of accessibility relations between agents. As I said, another example of this was Brandon's idea of belief revision, commitment of data. which involve this going back and forth, acquiring knowledge by way of this accessibility relations.
And once you have a kind of a common knowledge, basically openness between your agents, and each one has a state of knowledge of itself, then this becomes basically what we call a communication channel opens. It gives us much more details about the state of the system than the simple sequential one-player game would have allowed us. Now... Sorry, I forgot, just something came to my mind I wanted to talk about before moving forward.
I can't remember. Anyway, let's move forward. Communicative events range from simple public statements to complex private ones, each resulting in different behaviors. When we talk about communication, We mean a broad range of conversations, from a dialogue to computational systems that have many agents engaged in a wide variety of tasks. Compare this with our previous disquisition on algorithm and its environment, server and the client,
queries and replies, so on and so forth. In this sense, conversation really is about information flow and how it affects actions. And actions, first, this action in the traditional setup of multi-gen systems was simply just really action, action in the sense that we understand this action. And that's why it was very, a study of multi-gen system was very fundamental in robotics. But you can also think of action, this information flow, and how it affects action as programs. That's how this isomorphism between how information following multi-gen systems affects action, coordination,
synchronous and asynchronous actions. This is how it's received in computer science. Actions were interpreted as programs. An example of public and private conversations and how they affect actions in multi-agent systems is public announcement as world elimination. The public announcement of true propositions P changed the current situation as follows. For any model M, world S, and formula P true at S, M and PS, M relativized to P at S, is
the submodel of M whose domain is the set T belonging to M, M, T entailing P. In this diagram one goes from M, P and not P at S to M and P at S without the not P. Crucially, truth values of formulas may change in such an updated step, most notably because agents who did not know that P now do after the announcement. This truth value change can be quite subtle over time, including in cases where statements make themselves false. One needs logics to keep this all straight.
So, this, as I said, idea, go on. Sorry, that t element of m such that m t entails p would be like all of the possible explanations for p, or all the possible ramifications of P that delimit us further inside M? Like M where P is true, all of the statements that might be true because of that? JOHN MUELLER 1 more time. Sorry. No, no, no, that's OK. JOHN MUELLER 1 No, no, go on, go on. You've got to kind of add something. JOHN MUELLER 1 Go on. No, no, repeat it. Sorry. JOHN MUELLER 1 Yeah. Your question is about it. Yeah, it happens to you as well.
It might be my Wi-Fi here. So the statement in curly brackets, T element of M, such that M, T, and T. So that submodel is all of the potential sets of statements that could be true because P is true in M. So it's M minus all of the statements that contradict P, or that make P not a possible... Yes, yes, yes, yes. That's the whole idea of updating. And you can think of this, again, as a randomian global updating of your commitments. Yes. Public announcement... Yeah, I'm just making sure I know how to... So public announcement, again, you can see this as a conversation with a person who argues
against you, has more knowledge, and rules out step by step your options again. And then this, at the same time, puts you in more ramification paths and a space of implications, but also reduces some of the other ones that have incompatibility relations. For example, whispering, again, you can think of this very intuitively in terms of whispering, is a public announcement in a subgroup
of a larger group. but it is only partially observable to the others. Hiding secrets, limited observations are ubiquitous in everyday communication. And you cannot think of this, again, in terms of asymmetry. In our game, civilization game, in our interaction of machines, some of them are black boxes to the others, how they interact with one another. You can think of this as an intuitive idea of whispering, and how it gives certain accessibility relations to some agents and not others, and how it affects different kinds of actions and behaviors in your multi-agent system. For example, consider your email.
The epistemic dynamic rule of carbon copy, CC, is a public announcement. But the more sophisticated button, BCC, blind carbon copy, achieves a partial announcement that can even mislead other participants. More complex scenarios arise in computer security and the arena of games, which are often designed to manipulate information flow. This partial announcement, private announcement, versus public announcement, formally in the way that I presented it, leads to a kind of a different model modules of information flow in your system, how these accessibility relations between
agents and obviously because of that, different actions affected by partial announcements as opposed to complete public announcements. Total observation of events may be analyzed as the following construction for changing models. Scenarios where information flows in different ways for different agents can be represented in event models A, we have E tilde I and I belonging to G. Precondition E and E belonging to capital E. Here capital E collects all relevant events, the uncertainty relation
to tilde i or agent i, encode which events agents cannot distinguish. For example, again, in our card scenario, when the agents checked their cards, agent 1 with the white card could not tell one's thing red from one's thing blue. Now information flow occurs because events e have preconditions and that's for or symbolizes capital P-R, capital E-E, for their occurrence. Say my having red card, not knowing the answer to my question, etc. When you observe an event, you learn that something must have been the case for this to happen.
The following update rule encodes the resulting mechanisms of information flow in this scenario. For any epistemic model, M and S, an event model A and small e, the product model, M product A, S and E, has a distinguished new world S, capital S, capital E, and then one, a domain SE as a world in M, E an event in A, so that MS entails precondition for the event. B accessibility relations SE tilde I, as I said, it's just notation for accessibility
between agents and the world. TF, if and only if both S tilde IT and E tilde IF hold. Three, the valuation for atomic formula is P at SE is that for S in M. Product update models. Product updates, or you can think of this as a global update of your commitments in Brandoomian sense, models of wide variety of information scenarios. And the universe of models with product update, end product A, has a rich logical computation of the structure. And I will come back to this more in details
when I talk about in terms of this updating process, in terms of in the framework of linear logic that linear logic, even though epistemic logic really gets us the conceptual framework of this multi-agent relations and behaviors and accessibility relations, but it's fundamentally insufficient to really model the kind of computational logical structure of this scenario. Linear logic is really the proper tool. So in this sense, within the multi-agent systems, we have, as I said, belief and other dynamic phenomena.
We have belief provision. We have dynamic updating of forward chaining, backward chaining, updating. You can also think of this not only in terms of beliefs, but also in terms of your knowledge accumulation and the idea of non-monotonicity of knowledge, that these kinds of models of conversation, multi-agent interaction, allows us to formulate new models of knowledge, especially in philosophy of knowledge, or in designing models of database of how you revise or repair or update your accumulated
knowledge, your accumulated database. With the understanding that in the kind of very classical form of epistemic progression or in philosophy of knowledge or in models of database, you have simply an accumulated knowledge tagged by the label past. And then it always, in the classical models, your past knowledge bears on your present knowledge. But that also creates so many biases. Past knowledge always bears on your present knowledge. How is it possible to generate genuine knowledge, where the effect of the past knowledge on
the present is no longer biasedly strict and strong, where you can actually revise, update, or repair your past knowledge and arrive at a kind of future knowledge that are not fundamentally shackled to your past knowledge, to your accumulated knowledge, to your so-called—it's not simply speaking, it's not simply retrospective. So you can see the implications of this, in philosophy especially, all this stuff coming
about over-emphasis on past and knowledge of the past, on retrospection. These are really quite from a modern perspective in philosophy of knowledge and computation, in how systems of knowledge are generated. These are quite actually biased views of overemphasis on past knowledge or accumulate knowledge or retrospection and so on. So as I said, knowledge was just one feature in information flow. If we also model agents' beliefs and expectations, product update can describe events affecting belief including misleading actions leading to false belief.
Moreover, we need not just record information of that, we can also model belief revision, more agent dependent phenomena, which can depend on very different policies for different types of agents, more conservative or more radical. Again, think of this as different concrete scenarios in Brandomian commitment, philosophy of rationalism in terms of commitment of belief revision. The real benefit of bringing together computation and multi-agent system is not the reduction of one to the other. It is creating a broader theory with interesting new questions, in particular a theory of computation
that absorbs ideas from multi-agent systems must incorporate the dynamics of information flow and multi-agent interaction. We will mainly discuss one way of doing this. It starts from knowing algorithm and then adds further structure. Then I proceeded through a very rudimentary example. basically our aim is merely to show some of the questions that can be asked at once in this setting, without going much into trying to answer them. But as I said, this whole idea of introduction of multi-agent systems to computer science
was really indexing new problems, coming up with new questions. was even that they were hidden to the classical, traditional patterns of Turing computation. So one of these, another aspect of multi-agent system that is also a key in its role in computer science, and again was kind of adopted in theoretical computer science,
is the problem of epistemizing algorithms in accordance to multi-agent cynics. For example, consider the basic computational issue of graph reachability, GR, the shortest path scenario that we talked about, also known as shortest path. Given the graph G with distinguished points x and y, is there a chain of directed arrows in G leading from x to y? This task can be solved in p-time in the size of the graph. There are fast quadratic time algorithms finding a path. The same analysis holds for the task of reachability of some point in G, satisfying a general goal condition find.
GR, graph reachability, models search problems in general, and the solution algorithm performs two closely related tasks, determining whether a root exists at all and giving us an actual plan to get from X to Y. We consider various ways of introducing knowledge and information in the multi-agent systems within the scenario of graph reachability. Knowing you have made it, suppose you are an agent trying to reach a goal region phi, but with only limited observation of the graph in which you are moving. In particular, you
need not know at any point x at which precise location you are. Therefore, the graph G is now a model, a tuple, G, R, and tilde, accessibility relation, with accessibility arrows, but also epistemic uncertain links between nodes. A first epistemization of graph reachability merely asks for the existence of some plan that will lead you to a point that you know to be in the gold region fine. We can also think of this in practical settings involving a robot whose sensors do not tell her exactly where she is standing. In this case, it seems
reasonable to add a test to a task, inspecting current nodes to see whether we are definitely in the gold region or not. And that gold region is K-phi in our presentation. In the setting, further issues arise. What about the plan itself? If we are to trust it, should not be required that we know it to be successful? For example, consider the following graph with an agent at the root trying to reach the phi point. The dotted line indicates the agent cannot tell the two intermediate positions apart. A plan that achieves the goal is up across, but after following one part of this, the
agent no longer knows where he is, and in particular, whether moving across will reach the five point, or rather moving up. Let's formulate the requirement. Suppose for simplicity we have this, a plan is just a finite sequence A of arrows. We may then require initial knowledge that this will work, K A, K phi, but this is just at the start. We may also want to be sure at all intermediate stages that the remainder of the plan will work, because we said once that initial moves are done,
different uncertainty accessibility relations are unfolded. And then it becomes again a kind of a decision problem. This would require truth of all four . A1, K, A2, K5, where A equals A1, A2. The existence of such a transparent plan can still be checked in p-time, since the number and size of the relevant assertions only increase polynomially. But this quickly gets more complex with plans defined by more complex programs. For example, it's not obvious how to even define the raw notion of epistemic reliability. And we suspect it may lead to new languages, basically
to new logical frameworks, to which move, what would be the next move in this framework. But there is more to the epistemic setting in the preceding example. Note that the agent in the graph has forgotten her first action. Otherwise she could not be uncertain about the two nodes in the middle. Our earlier agents with perfect recall would not be in this situation, as they can only in that card example you can think of this, as they can only have uncertainties about what other agents did. And the earlier mentioned communication law, KA-Phi to AK-Phi, which holds for them, will
automatically derive intermediate knowledge from initial knowledge, KA-Phi. But there are many kinds of epistemic agents with perfect recall, with finite memory bonds. Therefore epistemized algorithms naturally go together with questions about what source of agents are to be running them. And the complexity of these stats for agents can vary accordingly. So depending on the kind of agents that interact, that navigate this environment, we have absolutely different behaviors. We have different kind of problems. In our card examples, we had kind of a perfect ideal agent.
But that's always just a special case. Sometimes you have agents that, as I said, they have finite memory, finite random access memory, different basically qualities, types, constructions. And then when they interact, when they navigate, their behaviors would be different. Problems arising would be different. Solutions to these problems would vary. But also in an epistemic setting, the notion of a plan itself requires further thought. A plan is a sort of a program that can react to circumstances. It's basically a real time.
is interactive via conditional, for example, instructions such as if alpha, then do a, else b. The usual understanding of a test condition alpha is that one finds out if it holds and then chooses an action accordingly. But for this to work, the agent has to be able to perform that test. Say we ask a computer to check the current value of some variable or a burglar to check whether the safe has a good lock or an inferior lock. But in the above graph, the plan, if you want up, then move across, else move up, though correct as an instruction for reaching the goal, is no use, as the agent has no way of
deciding which alternative holds. There are two ways of dealing with this. One is to include the knowledge into programs, namely the question of epistemizing algorithms. And for that you need the multi-agent setting. There are two ways of dealing with this. One is to include knowledge into programs. We make actions dependent on conditions like the agent knows alpha that can always be decided, provided agents have epistemic introspection. Suitable epistemic programs are automatically transparent in the above sense.
The other option is to define a notional executable plan in an epistemic model M, making sure that agents can find out whether a test condition holds at any stage where this is needed. And these complications and the multi-agent settings, the decision problems and the kind of the diversification of complexity classes and the kind of computation navigation that
our agents need to undertake leads to another key topic in multi-agent systems, and that's dynamifying static logics. You know, in a kind of traditional framework, it's the static logic, modeling our total system. Whereas now, we need to have a dynamic logic that allows for updating action according to these specific criteria at each step, at each interactive step. Finding out whether a proposition holds involves actions
of communication or observation. And hence, you move beyond epistemized aesthetic logics to dynamic ones. And this is one of the reasons that this whole historical progression moved more and more from a kind of aesthetic logics to more of a dynamic logics in the sense of really explicitly capturing dynamic properties, but also logics that have dynamic frameworks, like linear logic, like ludics that I will talk about. Then we could model the above test conditions alpha as explicit actions of asking whether alpha holds.
This requires richer multi-agent models, though where one can query other agents or perhaps the environment about certain things. Again think of this in terms of a strong, small set of algorithms where the algorithms communicate with the environment into queries and answers throughout the steps. That would be kind of a way of thinking about these. Multi-agent scenarios and interactive games, again, is another key topic in the study of multi-agent systems
and reasons behind its key role in the emergence of new topics in fundamental computer science. Several epistemic scenarios in the preceding discussion suggest adding more than one agent, moving from traditional, lonely, algorithmic task to more social ones, basically multi-agent, involving more than one player. As I said, one player is just the model of a traditional, classical interpretation of a Turing machine estate transitions.
Whereas multi-agent systems opens up to sequential interactive machines, persistent Turing machines, weak type of interactive machines, strong type of interactive machines, depending on how these agents are plugged together, how they interact synchronously, asynchronously, which one makes the first move, which one. Are there queries and answers, or simply their respective actions, are of the same type or nonsense? These are all different configurations that lead to different problems with different solutions and multi-agent systems.
For example, reaching a goal and knowing that you are there naturally comes with variants where other should not know where you are. Examples in this literature include the Moscow puzzle, where people have to tell each other the cards that they have without letting a third party present know the solution. Card games, or the earlier mentioned use of email, provide many further examples of this. The social interactive perspective comes out even more in the setting of games and interactions between different players. Turning algorithms into games involves the prying apart of existing algorithms into games
with different roles for different agents, different types of agents. Three examples are logic games in the style of Lorenzen and Antica. In our third module, that would be one of the key concepts that we will investigate, the concept of logic and computational games, formalization of them, kind of the history of their evolution. Again, consider graph reachability. The following picture gives a travel network of logic and computation.
It's easy to plan trips either way between Moscow and Iriban, but what if the transportation system breaks down and a malevolent demon starts to canceling connections anywhere in the network. At every stage of our trip, let the demon first take out one connection, now we have a two-player sabotage game. And the question is who can win it where? From Iram, the traveling agent still has a winning strategy, but the Russian situation, the Moscow one, is less rosy. Demon has the winning strategy. This example suggests a general transformation for any algorithmic task. It becomes a sabotaged one when it is cast as a game with obstructing players. This raises several new questions, examples, about logical languages describing
these games. Because, as I said, different types of agents, precisely because they have behaviors. For them, for you, in order to be able to model them, logically model them, hence also computationally really observe their behavior, you need to develop new logical languages. Whether your agent is an obstructing agent, a sabotaging one, or whether your agent is a coordinating one. And again, a very powerful logical language to capture these various
types of agencies, representing different types of processes in a system, both in the sense of obstructing, sabotaging, or reinforcing, coordinating, is ludics, a refinement that that Girard himself made from linear logic. We'll talk about this really in details. So would a potential way to look at describing these games be to view the canceling of connections as public announcements and then find a way of comparing the size of submodels? like your ideal moves as the demon or your more optimal moves are those public announcements
of cancel trains or no taxis to this location that produce the smallest new subset of potential moves for the enemy? Yes, yes, yes, yes, absolutely, yes. Yes. Yeah. This is formalized, this whole idea of downsizing your model that becomes basically more optimal with better accessibility relations. I think I need to think about this carefully, though. But my intuitive understanding is that in Girard's logic, but I will talk about it in detail.
use all of the notations and stuff. Takes one whole session. It's, I think, very intuitively can be seen as Girard's concept of focusing. Focusing is exactly like this in Girard's linear logic. It's focusing is precisely this kind of reduction, but also effective navigation in your logical chain for me once. If you're familiar with focusing, but I will definitely introduce this. Focusing is basically, you can think of a dialogue, for example. The first thing is that in kind of a dialogue, you need to pair your conversation on the
same topic. This is basically the constraining of the player versus the opponent. You constrain one another around the same topic. You can see, for example, we meet each other, you say something and I say something and And then as we have interaction, this is slowly our conversation, our, you know, come around a common topic. This common topic is really the idea of focusing and the idea of model to sub-model that rules
The result is to obtain access both to relations and opens up others. So drawing down, paring down the range of possible next steps for each agent until they share a common space, which could be establishing a translation protocol, establishing a common topic, or forcing, like in the case of two agents moving around a network of transit methods, and maybe one of them is trying to evade the other, and the other is trying to force them into the same location so you can arrest them, whatever.
Yes, asymmetric warfare. Yes, absolutely. Yes, yes, yes, yes. True it, yes. So this is something like there is a formal, like focusing is something that is formally defined? It's a formal representation of this, but different scenarios is from focusing. Even when you have a focusing, even when you have this, you know, kind of a constraining still if your players have different strategy, which of course as general case they should have because having the same type of a strategy. And again, formally, processes can be understood. This is the whole idea of untyped logical system. You see, typed logical systems are processes of the same type. Queries and responses are of the same type in the mathematical sense.
Untyped logical system is a wholly different wild jungle, basically because it opens up these really kind of complicated moves and strategies that can happen while you have different strategies for different agents or different types of processes while at the same time you have a focusing constraint forcing one to adopt my location my topic right so they get more complicated so when you have a typed system and you have different kinds of agents with different fitness criteria or whatever then the focusing constraint necessarily becomes nonlinear because the focusing occurs between two different strategic lines.
Yeah, this is an untyped system. Yes, an untyped system. Untyped systems, really, an untyped system is, you see, the whole idea is that linear logic is more of a typed system. Ludix, Girard refined it by turning to an untyped system. An untyped system, Jean-Baptiste Jonet, another great logician computer scientist that I mentioned session, he compares it with this really wild jungle of logical computational phenomena. And it is quite perplexing, the kind of winningest strategies, moves that are being made in these
games and these logical systems. We'll talk about all of this when we're talking about the Howard-Curry, Howard-Lambeck correspondence. First we need to understand what type system is, and then what can be an untyped system, and how interactive an untyped system works. Okay, and so the type system then is the one in which cops can only interact with cops, and criminals only with criminals, and so on and so forth. So it's because it's untyped that you're able to have wildly different agents interacting with... asymmetry of moves, behaviors, asynchronicity, winning strategy, possible modal scenarios for winning.
Obviously different games, copycat strategy, not simply copying. Girard really formalized all of these. You have different copying moves, stealing strategy, obstructing strategy, copying. replicating, yes, try to cover as much as this stuff in the last module. Which is really, that's the realistic account of natural language conversation, if you think about it too. Right. The openness of the encounter, that it is untyped. Yes. Cool. So, as I said, back to our example, the Russian situation is less rosy, Demon has the winning
strategy. This example suggests a general transformation for any algorithmic task. It becomes a sabotage when it's cast as a game without obstructing players. This raises several questions, example about logical languages describing these games and players' plans and strategies in them. In particular, how does the computational complexity of the original task change when we need to solve the new game? For sabotage graph reachability, it has been shown that this complexity moves up from low p-time to p-space completeness. That is, the problem now takes a polynomial amount of memory space, which makes it of complexity class of Go or chess.
Another example of this kind of anomalous behaviors and once you have non-coordinating behaviors among your players or agents or machines is catch me if you can. So there is no general rule predicting when a newly created game becomes more complex than its algorithmic ancestor. Again, consider graphs, the setting for excellence for algorithmic tasks, but now with another game variant of graph reachability. Obstruction in this sense, one player obstructing another player, could also mean that some other player tries to catch me en route, making it impossible for me to continue.
This is the whole idea of catch me if you can. It is easy to cast this as a game too. Starting from an initial position g small xy with me located at x, u at y, I move first then u and so on. I win if I reach my goal region in some finite number of moves without meeting you. You win in all other cases. This game too is very natural. It models a wide variety of realistic situations, such as warfare or avoiding certain people at parties. But this time the computational complexity stays lower. Solving catch me if you can only takes p-time in the size of the graph.
This can be seen by the analysis of the analogous cat and mouse game, adding knowledge and observation again to the system as you make your moves. In actual warfare, catching games naturally involves limited observation and partial knowledge. So they don't have that kind of completeness of epistemic logic that was the case in our simple interaction games. In such games of imperfect information, players need not be able to see where the others are, and solution complexity may go up to PS space and beyond. Merlin Sevenister, for example, conducts an extensive study of various epistemized algorithms
in the aesthetic, using connections with the if-logic of Hentika to clarify their properties. In particular, it shows that the situation is delicate. For example, consider the mild form of warfare called Game of Scotland Yard. Here the invisible player who tries to avoid getting caught has to reveal her position after every K moves from some fixed K. But then the game can be turned into one of perfect information by re-encoding players' moves, making case sequences of all moves into single steps. Oops. So that would be like if we were in an RPG or something,
and there's some plot item necklace of Golgotha or whatever. which is to go and get this amulet that's going to get us into the tomb, but we can narrow all of that down, you know, killing the guards on the amulet, negotiating for it, whatever, into step, get the amulet. Uh-huh, yeah. Okay. Another topic that, as I said, often comes up in the study of multi-agent systems and problems, And again, one of the main ideas why multi-agent systems were so widely adopted in development of new models and paradigms of computation was asynchronicity.
As I said, agents in the environment can interact in cooperative, neutral or malicious way with an interaction machine. Again, as I mentioned, adversaries that interfere with algorithmic goals provide a measure of the limits of interaction machine behavior. Synchronous adversaries control what inputs an agent receives. What inputs an agent receives. What asynchronous adversaries have additional power over when an input is received. Asynchronous adversaries who can decide when to zap you are interactively more powerful
than synchronous adversaries. They have different computational capacities. And asynchronous study, generally speaking, and study of games, the main figure behind is Samson Abramsky. Linear logic, in the first way that Girard formulated it, only managed to index synchronous global polarities between player and opponent. Blass, Andreas Blass,
made refinement of it and turned the global polarity between processes or agents or player and opponent into local polarities. It was shown that reduction of global polarity or duality to local duality or polarity leads to a different computational logical phenomenon. Abrams made another refinement on blast games and took out the synchronicity problem, synchronicity constraint, showed the relaxation of synchronicity, proving that asynchronous games are general
games. Basically all games are generally asynchronous. Synchronous games are special cases. And asynchronous games again cover broader computational logical problems that even games that are locally simply are not globally, locally polar, but nevertheless synchronous can't cover. We talk about this when I talk about copycat strategy. From a genuine, you see, game-theoretic viewpoint, many other questions may become relevant. However, for example, Seven Stars' major complexity results are in the IF tradition
of asking whether some player has a winning strategy even when hampered by lack of knowledge. But the most crucial feature of finite games of imperfect information, both mathematically and in practice is the existence of something more delicate, the so-called Nash equilibria in mixed strategies, letting players choose moves with certain probabilities. Maybe it is the resulting game values that we should be after for gamified algorithms. Therefore, gamification and generalized computation should also make us pause and think about the most natural counterparts to the properties of algorithms when they were still pure. This is just one of many issues when we take game structure and multi-agent scenarios seriously.
Imperfect information games also invite explicit events of observation and communication with nations and the environment. Moreover, they fit naturally with the parallel action scenarios, parallelism and computation. Much of game theory is about simultaneous choice of moves by players. In our civilization games, every set of civilization doing their own thing, you might not be even interacting explicitly with one another. And then, why two players and not more, as I said, because traditionally multi-gen systems were simply transformation of one player transition state to two-player games. But again, this is something that Abramsky was very much
responsible for how in computer science, he formalized and kind of worked out different kinds of problems and solutions that arise in many player or multiplayer settings. Traditionally, again, I will talk about this. Traditionally, in linear logic, you have player opponents or processes or agents. Their interaction is symbolized by the notation of duality in linear logic called linear negation.
It's the notation of an orthogonal symbol. Orthogonal symbol is simply a notation for duality, player, opponent, system, environment, agent one, agent two, process of one type and process of another type. Dualities in the framework of linear logic indexes simply interchange of roles between your processes, your agents or player opponents. Ebronsky showed that once again you understand duality, namely interchange of roles, as a
special case of a mini-agent game or true genuine multi-agent interaction, duality becomes something else. Interchange of roles becomes something else. of role becomes permutation of roles in your game. Permutation of your, permutation of roles in the sense of permutation of role of player opponents, player one, player two, player three, four, so on and so forth, again gives to different problems with different solutions, with different computational behaviors. And again, that was part of his refinement the original contribution of Girard's linear logic that was simply capable of indexing
dualities or polarities in interaction by way of the concept of mathematical duality, simply interchange of rope. Oh my goodness, we're at 2.15. Seems that concurrency problems are so, I just basically, let me just finish this part about the multi-agent system. And then basically we are moving to concurrency problems and introduction of Petri Nets and the kind of key concepts behind a study of concurrent systems that were adopted in theoretical computer science. As I said, imperfect information games
also invite explicit events of observation and communication. Moreover, they fit naturally with the parallel action. as much of game theory is about simultaneous choice of moves by players. And then, why two players and not more? For example, even inside the heartland of logic games, it has been proposed that argumentation, often cast as a tennis match, really needs a proponent, an opponent, a judge. In this sense, we can see that the view of algorithm in social settings or multi-agent system naturally merges computer science and logic and game theory with new links and new research questions running at Ross, leading to refinement in computer science and game theory and logics.
Our discussion was basically just a bunch of examples trying to address some of the key concepts in multi-agent settings and why these multi-agent driven concepts were highly significant for computer science, especially from the 80s onwards. Hopefully next session I will try to really quickly go over concurrency and introduction
of PetriNet, talk about the key concepts of concurrency systems, and then we finally move to our last one, which are the logical problems, and that allows us for making that kind of a grand overarching unification between all of these key problems, accurately formulate them, show their significant computer science, and their possible implications for, as I said, artificial intelligence, construction of language, complexity science, theories of cognition and mind, et cetera, et cetera. Questions, stuff, discussion, observation. Is a turn-based game kind of a mixed state
of synchronous and asynchronous? Like whether it's chess or D&D, like you have a game board, which is like a . It's a sequential game. I think the whole idea that sequential is extremely important for computation, whether we are talking about a Turing machine, classical Turing machine computable theory, or we are talking about interactive things. Because sequentiality can accept both synchronicity and asynchronicity. And again, I will talk about, you have in the very, very kind of traditional, very conservative sequential way, You can think of this as simply a Turing machine. Then you have a kind of weak interactive sequential algorithms, and you can think of this as a
kind of a very conservative term based that you make one move and the environment instantly responds to you with an answer to your query. Then you can think of this asynchronous turn-based or asynchronous hyper-sequentialized algorithms in terms of our civilization games. We are making turn-based, but we are moving asynchronously. Our responses to other civilizations are asynchronous behaviors that emerge, come out of this asynchronicity, but still can be captured by the sequentialized roll of dice or turn-based algorithm. Okay.
Raza, does that apply also, like, I'm thinking of other turn-based games that kind of almost lend synchronicity, like in XCOM you can set troops to Overwatch, and you can effectively steal a turn because they'll take an action in your opponent's turn, if that makes sense? I haven't played XCOM. So, but yes, that makes sense. But yes, yes, it does. Again, another example of this in Civilization games in terms of asynchronicity. Asynchronicity usually arises because of a few factors. agents of different types interact, but also agents who ethnically steal, copy, or obstruct
moves of the opponents. Yeah, yeah, that's a- Indirectly, indirectly, by way of a third agent. the asynchronicity, for that reason, implies a genuine multi-agent system, namely an end-game player, an end-player game, rather than just a two-player game. You can think of this in civilization games very actually funnily, that sometimes, you know, I want to go for a science victory. I don't want to enter war, but everyone tries to wage war on me because I don't have war units. Now, instead of actually entering war directly with these superpowers, I use my resources
that are making massive amounts of gold. I bribe other civilizations to enter war with one another. Use an intermediate player to enter war with another player. this move by way of an intermediate player of a different type, breaking the polarity. And that's sort of like your use of gold as an asynchronous strategy or asynchronous game to create a synchronous game which is you and all these civilizations potentially being at war with each other. Yes. Is that kind of... Uh-huh. Uh-huh. Cool. Yeah, I think you can do similar things.
Well, the mechanics of the game are very different, but XCOM has, I think, similar things which allow you to achieve, like what you describe, a synchronous game within the asynchronous one. I just asked because I was thinking about writing about that for the second module. Superb. No, I haven't. Is it a good game? It's a superb game. Especially, there's like a massive community mod called Long War for the rebooted version of X-Men. It's like an early 90s classic and then a reboot, which is, yeah, the modded version of the reboot is really, really good. You sort of, Earth's being invaded by aliens and you sort of, it's a turn-based strategy game
with like small squads, but you reverse engineer the alien technology it's quite superb, okay I will definitely look into it I know the game but I've never played it so the one to get is XCOM 2 sorry? is the one to get XCOM 2 that was what came up when I googled yeah there's XCOM 2 has just come out recently but it's sort of there's three things you could do really the very original game from the early 90s if you're into, like, very retro gaming. And then there's XCOM Enemy Within, which was released, like, three or four years ago, I think. And that's where they rebooted the franchise,
and then XCOM 2 is the sequel to that. And both are good. I'd actually play Enemy Within slash Enemy Unknown first, and then go to XCOM 2. All right, heard. Thanks. These are all excellent, I think, really. That's why I was saying that, you know, When we are talking about artificial intelligence and this idea of open harness, computer science as the vector of evolution of intelligence, that players are constrained by one another, but also their interface drives them toward evolution of strategies for each process of And the more arbitrary asynchronicity you have, the more complexification of intelligence
in your open harness schema you have. And I think a good example of this is that so many of these turn-based strategies, they do not have arbitrary input from the environment. I think the old civilization games had this. You had it in climate catastrophe. If you nuke too much, tiles start to flood. You really get fucked up. You basically need to completely come up with different strategies rather than simple brute force warfare, which can be understood as once you see not only asynchronously in the sense of interaction between agents, but also the arbitrary effect of the environment over
the system. As a hidden player, as a black box player, you have, again, different kind of behaviors. You have an evolution of different kinds of complexities. Yeah, that fits well in XCOM 2. The environment is destructible and it really informs the gameplay quite heavily, like managing lines of sight within the spaces of the map. Without destroying obstructions or allowing disadvantageous ones to exist? Yeah, and often the game mechanic everything is shrouded in the fog of war so you have to encounter the aliens
and a lot of the game ends up revolving around managing the fog itself because you don't want to encounter there are too many aliens in one go, so you have to have these very constrained firefights. You constantly want to flank, but you're scared that if you do, you'll reveal more aliens, and then get crushed. So you have to use these technologies to manage fog of war, basically. It's quite fascinating. Yeah, that sounds awesome. I mean, this is not only of a, we can even think about this, why is it scientifically so important to model old scientific concepts and think of them
in terms of interactive computation theory? Which one of you asked me about natural selection? Was that you or that was one or who was that? And I said that we need to wait until we talk about computation and fine-graining discussion. I think, yeah, I think so. I mean, I will answer him when he comes back. You see, natural selection is basically, at its core, is a interaction as computation. You can see this as different modes of interaction. Interaction in the sense of closed interaction,
asexual reproduction, or sexual reproduction. Sexual reproduction and asexual reproduction are two different vectors of natural selection, precisely because they give rise to different landscapes for evolution. One is the fitness landscape, the asexual one, interaction with myself, or any kind of asexual reproduction that you can think of. Then the sexual production, in fact this is part of the evolution of sex, is a sexual production, precisely because it recombines alleles from different players, from different factors,
from different agents who are having sex, who are engaged in sexual reproduction, it creates an altered landscape. It puts pressure, accelerates the pressure of natural selection toward further complexification. Outward landscapes happen only through sexual reproduction, a vector of natural selection. And sexual reproduction, in this sense, as a computational vector, one that combines moves of players, alleles, genes. It creates an altered landscape and
leads to especiation. Especiation, complexity of emergence of a species, is part of this, can be formulated quite accurately and very faithfully by these interactive models of computation and gains. It's interesting that speciation is the loss of ability to interbreed. So once like sex, speciation is the loss of ability to interbreed. Like once populations diverge, it's no longer possible for them to at least have reproductive sex with each other is sort of the definition of the emergence of two species from one, or from whatever baseline. And I guess my question, or it's not really a question,
it's just sort of a thing about it, is the status of the environment as a kind of non-agent in the game. So as a source of hazards or of arbitrary variability, as an individual organism, what I think of as my environment includes members of my own species, other living things which are engaged in the same game of sex and selection, and adaptation, and then these acts of God, which are gamma particles that fry a particular gene or storms, you know, changing climate, which force... Mutations. Yeah, mutations were the things, and then also the things that interpret mutations, I guess, in the sense of assigning them values of good or bad, which would be like changes
in climate. And so now, like, if the climate gets colder, then mutations which cause me to be less gracile are sort of over-interpreted as being positive, and ones that cause me to be more gracile become negative. And I'm just sort of like wondering how... Can you find it to be understood as the general category of asexual calibration of fitness landscape rather than altered landscape? So a calibration of the landscape as opposed to altering it? Can you elaborate there at all? Like what is the difference between alteration of the landscape and calibration of it? Alteration creates opportunity for, as we talked about, diversification of agents, literally
a speciation. Whereas fitness landscape or calibration of the landscape is really the adaptation of individual species or group of species in the sense that it does not lead to variability in the sense of a speciation. Outer landscape is the diversification. Fitness landscape is quite literally the fitness criteria for the members of a group of species. Male Speaker 2 Is it kind of focusing? Male Speaker 2 Focusing. Male Speaker 2 Like a definition returned to a particular equilibrium given the… Of same type, of same type, yeah. Of same type, yeah. You've got kind of like nested landscapes,
and they're nested or encapsulated in terms of divergence and convergence. And then eights are just sort of part of, like any particular agent could be in relation to another, could be in any of these nested layers. So like a condition, well, let's see. a condition which forces variation could be the behavior of some other species or some other group within my own species and be part of that opportunity landscape. And then what I do in response is part of the fitness landscape. So like an agent or whatever we want to call an agent can fall in either of those landscapes both and so forth with respect to me, whoever I might be.
Okay. Yeah. And this is the reason that I mentioned this, because this kind of a game framework of computation, as I said, is not simply this kind of intuitive idea of interaction. But interaction, once we understand the way we are now understanding it, adds to pressure. It's that idea of open harness. It constrains you, drives you toward some specific implications.
And by narrowing down certain ramified branches, or broadening the others. And this is, in evolution, this is precisely the case. Usually people of sex, and so many good philosophers I have seen them saying that sex is about procreation. Sex has nothing fucking to do with procreation, that's just some stupid Pre-antiquity idea of sex. Sex is about altering the landscape in the sense that it adds pressure to possible moves of agents that have been interacting
and hence leads to alteration of behaviors by narrowing down certain possibilities and broadening up the others. Right, because we never needed sex in order to make more copies. No, that's stupid. I've heard this from really good philosophers. It's just mind-boggling that these people still have this kind of very intuitive idea of biblical idea of sex. Yeah. Well, you know, it's parochial, but it's what matters to them, right? Like, you may or may not end up with a kid because of it, and that's my next problem. We're getting narrowed.
I think we're getting winnowed down. It looks like we're down to like four or five of us now. Yes. So I will let you guys go. And next session, I will talk about Petrinets. And so I hold up the exercise, the dining closet problem. And then we move to our main discussion. Cool. Thanks, Reza. That was great. Thanks, Rostov. Thank you very much. Hope you have a great day. Take care, guys. MALE SPEAKER 1