So do I need to repeat this stuff that I was... We missed about 15, 20 minutes. Oh, my goodness. Okay, I will just start from... I mean, what we could do is we could just find the part. I could find the part where it cuts off, and then I'll email you later on this week, and you can just send me notes for... Okay, sure, sure. And then instead we'll just upload the notes. Sure, sure. So I start from the part about the Wittgenstein, and I made the distinction between the Laplacian determinism, causal determinism, and the computational determinism.
Basically, you should make a distinction between them. Of course, historically, you can see that the Laplacian classical physics influenced classical logic and the way that these things are formulated. But I don't think that in a way that these two trends of determinism are formulated, we should be very, very careful not to align the distinction between the two. And so I said when we reflect, but when we reflect that the machine could also have moved
differently, it may look as if the way it moved must be contained in the machine as symbol, i.e. an abstract machine, far more determinately than in the actual machine, as if it were not enough for the movements in question to be empirically determined in advance, but they had to be really, in a mysterious sense, already present. And it is quite true, the movements of the machine as symbol is predetermined in a different sense from that in which the movements of any given actual machine is predetermined. Indeed, the given way of moving described by Wittgenstein corresponding to the machine as symbol amounts precisely to the notion of formal in its computational variation.
But of course, Wittgenstein also says that the actual machines do not necessarily behave mechanically, especially, but not exclusively due to hardware limitations and constraints. Thus, when we speak of a mechanical way of proceeding, we in fact typically have in mind ideal abstract machines, not real ones. The intuitive notion of computability, as I mentioned before moving to kind of a more formal notion of computability, means that a calculation or computation can be defined as the passage from one initial state, the premises, or more generally the initial state
of information, to a final state, namely the conclusion or the result of the calculation. means of successive small passages from a state to a state. It is a successive transformation of innumerable finite states yielding a particular output from a given input. Given that the idea is to obtain some output, a crucial element in the notion of calculation is that it be a finite procedure. It is a procedure that must come to a halt. I will talk about this It can be represented as x1 arrow x2 arrow x3 arrow xn.
The key point is defining the rules or instructions allowing for the passage from a state to the next state in such a way that any agent would affect the passage in exactly the same way. important, i.e. obtaining the same, for example, x subset j for any x subset g minus 1, g equal or less than n. Seen this way, a computation has a few fundamental properties, such as it is discrete, one, i.e. it is not a continuous process, whereas it progresses through discrete individual steps. It is a dynamic process taking place in time
and with clear temporal direction. Every step is completely determined. Either instructions are applied strictly, requiring no insight or ingenuity. Now, I said that also another theory for this notion of calculation is that it needs to come to a halt. Basically, this is an essential aspect of a notion of computability, or one that is unanswerable for Turing machine. Some Turing machines, this is basically a halting problem. Some Turing machines on certain inputs never halt. Typical ways in which a program, a computation, is non-terminating are cases of basically
loops or of infinite progress. This is not a flaw of the definition of a Turing machine, because it is intended to be perfectly general. It must assume that the tape where the symbols are written is infinitely long, and the time for the calculation is also infinite, so that it does not rule out functions as noncomputable simply because the machine runs out of tape or time. So this is basically the gist of the whole problem. An algorithm or effective calculation method is a procedure that determines univocally by means of explicit instructions, which must be expressed by means of finite number of symbols. What X subset J is to be for any X subset J minus 1 when J is equal or less than N.
Naturally, this description invokes the notion of a function. I will talk about this in more details at the end. The canonical definition of function. I.e., an operation taking arguments into uniquely determined values, at most one value, but possibly none. But as is well known, not all functions are effectively computable. And the famous Church thesis is the claim that the function of positive integers is effectively computable only if it is recursive. I will talk about all of these, about recursivity and Church's definition.
After the formulation of Church thesis, Turing proposed another but equivalent, as we now know, analysis of the notion of computability, one in which informal features of this notion are better represented than in Church's thesis, the concept of what we now refer to as a Turing machine. We call them logical computing machines. Turing's main accomplishment is to provide a precise formulation for the rather vague informal idea that a calculating procedure should involve no ingenuity or insight, i.e. that the instructions in question can be applied mechanically, in that mechanical sense that we talked about.
A Turing machine is a state machine, constituted of an infinite one-dimensional tape divided to cells. It is infinite in only one direction, and a read-write head, which can move from cell to cell and can read the symbol contained in a cell or write a symbol in it. Each cell can contain one symbol, either zero or one. Its actions are determined by a table of transition rules, specifying for each essay J and for each symbol, either zero or one, what the with right head should do next. Each table of transition rules defines a different Turing
machine, while the hardware or the tape with cells and with right head remains the same. A transition rule is a four-tuple. Let me share the screen. Can you see the screen?
Yes. Okay. So, the four tuple, state j, symbol, state j plus one, basically next state, and action. The possible actions are, write a symbol in current cell, hence writing the symbol currently in it, move one cell to the right, move one cell to the left. Once the next action is completed, determined by the state and the symbol in the given cell, i.e., according to the table of instructions, either no action or more than one action is prescribed for a given state, n and symbol s. Then the procedure comes to a halt, and the computation comes to an end. This is the schematic of the Turing machine. Thus described, a Turing machine appears
to be an exceedingly simple device. But the corner of Turing's analysis is the proof that such a simple device can nevertheless calculate any recursive function of positive integers. The point is that given the initial state j and the symbol written on it, the action to be undertaken by the machine and what the next state is going to be are completely determined, in that logical sense that we talked about, determined by the table of transition rules, which in practice is the program for the machine. Now, for our basic discussion, it's important to emphasize the crucial role of concrete external symbolic systems at the very heart of the notion of computability, and hence
why we started with elaborating the notion of formal as intrinsically connected to symbolic regimes. So, and that's basically, you get a rudimentary form of an algorithm, this whole idea of, you know, basically actions performed, allow you to, you know, basically make that historical concept of algorithm more technical. as I will talk about in the next session, hopefully, is that still, even after a theory of computability, the concept of algorithm is not well understood.
In fact, it is at the center of a massive controversy in fundamental theoretical science, especially it has been in the past couple of decades. No one really knows what an algorithm is because of the problems that we'll talk about at the theoretical level. Generally, algorithms depend critically on their instantiation in actual portions of writing. Once mastered, an algorithm, say, for example, carrying when undertaking sums within the familiar Hindu-Arabic numeral system, can be simulated mentally, but this is, in fact, corresponds to an internalization of the external cognitive artifact, the procedure as defined
in a given notation. While claiming that symbolic instantiation is a necessary, i.e. constitutive condition for something to count as an algorithm or calculating procedure is an exceedingly strong claim. It is sufficient to notice that in practice human beings have developed basically calculating procedures in close connections with external notational systems, which of course says something, I think, very profound about the structure of human cognition, that notational systems are cognitive prosthesis in that sense. As we talked about in the last session,
they basically augment human cognition. So, in effect, Turing description of a Turing machine makes the connection between computing, calculating, and what can be described as an externalization of reasoning, even more patent. The tape with cells, the Reed-Wright head, and the table of instructions are all external, physical devices involved in the calculating procedure. There are, as I said, cognitive artifacts. From this point of view, the formalist computable is inherently related to the idea of cognitive extension and integration. And I think a good amount of philosophical discussion can be put into this topic in terms
of extended theory of mind, that actually once we understand basically what is exactly a computation in the formalistic sense, then we can talk about them in the sense of theories of extended mind, as I said, external prosthesis of cognition. This also means that when applying to the notion of formal languages, the formal as computable clearly suggests that an extended cognition perspective is particularly suitable to investigate the effects of using formal languages and formalisms when reasoning. Now, another way of formulating roughly the same point is that informal concepts of computability
is thus from the start motivated, in fact, by inherently cognitive considerations. How do we exclude appeal to ingenuity and insight from certain reasoning processes? Notations which incites sensory motor manipulations greatly enhance, for example, the possibility of blocking the interference of ingenuity and insight, kind of filtering out some of those intuitive biases that we talked about last session. And in doing that, they block tacit external assumptions and reasoning shortcuts. A passage by Whitehead, illustrated this idea particularly well.
He says, by relieving the brain of all unnecessary work, a good notation sets it free to concentrate and more advanced problems, and in effect increases the mental power of the race. In mathematics, granted what we are giving any serious attention to mathematical ideas, the symbolism is invariably an immense simplification. By the aid of symbolism, we can make transitions in reasoning, almost mechanically, by the eye, which otherwise would call into play the higher faculties of the brain. It is a profoundly erroneous true reason that we should cultivate the habits of thinking
what we are doing. This is, I think, superb, what it says here. The precise opposite is the case. Civilization advances by extending a number of important operations which can perform without thinking about them. Indeed, following Whitehead, we can say that the less we think about what we are doing in certain procedures of cognition, the less likely it is that the ingenuity or insight will be called upon. So to sum up what we talked about before moving to more focused investigation of the debate
between Church, Turing, and Godel and the rise of computability theory, what we have talked about so far is that we introduced two concepts, two notions of formal. as de-semantification and formal as computable. Formal as decoupling from intentional content, as I said, this is one of the main senses in which the formal languages are thought to be formal. Even though there exists, of course, formal languages which are meaningful in a kind of a logical way and does not uninterpreted languages. For example, Martin Loew's constructive type theory.
Formal languages, as they are currently used, are predominantly uninterpreted language. But also notice that the idea of manipulating symbols as inscriptions with no meaning at all, simply by virtue of their location in a symbolic regime, an interactive symbolic regime, is not sufficient to constitute a formal language or a formal system theory. Although Girard, I would say, as we will talk about this in the last module, I think has
shown that all you need really to develop a system that is as powerful as natural language And as powerful as a massively formal system, all you really need is really the location of the sign, simply devoid of any referential meaning of the sign, basically. But this is something that we need to just wait for until we get into that point. Explicit and exhaustive rules of how to manipulate symbols are also required. In this sense, the formal conception of arithmetic, as championed by Thome and others in the 19th century, is already a protovariation of formal as desematification,
in the sense that Sybil Cramer used the term. But it is not based on an underlying, fully-fledged, formal language. Kramer presents the idea of operative writing as a particularly vivid illustration of the process of de-semanification. Signs can be manipulated without interpretation. This is what she says. According to her, calculus is an ideal example of the process of de-semanification. The rules of calculus apply exclusively to the syntactic shape of written inscriptions.
not to their meaning. Thus one can calculate with the sign zero long before it has been decided if its objects of reference, the zero, is a number. In other words, before an interpretation of the numeral zero has been found that is mathematically consistent. Now it might seem awkward to use the term de-semantification or decoupling from semantic intentional content with respect to formal languages, and so far as basically their components are presented as meaningless signs from the start. That is, as a mathematical rather than a semiotic object. But in reality, what this semantification refers to is the more general historical development
from our usual tendency to operate and reason with meaningful languages toward the technique of reasoning with manipulating meaningless signs Goa inscriptions. Besides offering a terminological reason why formal languages are indeed formal, the de-semanification aspect of reasoning with formal languages will be of absolutely crucial significance for the explanation of the cognitive impact of using them. And that's why I mentioned very rudimentary as basically being these cognitive artifacts, cognitive prosthesis. And as I said, you know, Stanisla Dehaan has written about this in the number sense, and
also, you know, basically the cognitive technologies provided by the invention of arithmetic. And Katarina Lutlano-Weiss has talked about this extensively in relation to neuroscience and theories of extended mind in her book. You can get into more details by reading those books. So the second concept of the meaning of the notion formal was formal as computable. While the formal as de-sematification is crucial for the cognitive input of use of formal languages, it is neither necessary nor a sufficient condition for a language to count as formal.
The formal as computable does constitute at least a necessary condition for something to count as formal language. Moreover, it is also a decisive aspect of cognitive resources afforded by formal languages and formal systems or theories more generally. Indeed, precisely the combination of de-semanification with the application of external rules of transformation that allows formal languages and formalisms to be such powerful cognitive tools. Essentially, the explicit formulation of rules of transformation results in an externalization of reasoning processes, which moreover rely heavily, as I said,
on sensory motor processing by the agent, literally moving bits and pieces of the notations around. As I said, the general idea of the formal as computable operates on two different levels. The level of how the lexicon of a given language is combined to general well-formed formulas on the basis of the syntax of the language, basically its formation rules, and the level of the rules of transformation of the logic or the formal systems or the rules of inference that are built upon the formal language in question. In the first case, the procedure is computable in the strict sense that it can always be decided on a finite number of steps, i.e.,
assuming no infinite formulas, whether a given formula is well-formed or not. In the second case, basically the rules of transformation, rules of inference, the procedure is not always decidable in that there may not be an effective recursive procedure to determine whether a given formula can be attained by means of a finite number of inferential steps from a given set of starting point formulas premises. Nevertheless, even in undecidable systems, a significant number of conclusions can be drawn by a strict application of the rules of transformation inference of the system.
Strictly speaking, the latter case do not qualify as computable in the sense of the availability of the general decision procedure. But they do display a similar pattern for the application of rules. So in any case, a formal language, strictly speaking, is generally characterized by the fact that its well-formed formulas are recursively enumerable. When this condition fails, we can at best speak of semi-formal languages. So this was a little bit about the informal notion.
I mean, when we talk about the concept of formal as computable, we try to talk about it formal, computable in two sense. Again, formal in the sense of intuitive concept of computability and formal in the sense of rigorous and systematic concept of computability. But I very briefly mentioned this distinction between the two. But in order for us to entangle the relation between the intuitive concept of computability and the formal concept of computability, and hence the theory of computability as proposed
by Church and Turing, we need to kind of get into debates between Godel, Kling, Turing, and Church. So this is what we are going to do. We are going to untangle the relation between the intuitive concept of computability and the formal concept of computability. If one takes Godel's notion of general recursiveness as the rigorously defined concept and effective calculability as the informally grasped one. So basically, general recursiveness represents the rigorously defined concept of computability, whereas effective calculability, as provided by Church,
is more on the side of the informal concept of computability. Then Church expresses the relation between this and that concept of computability for number theoretic functions. We can basically say they are coextensional. Godel, in the historical context, Godel introduced general recursiveness for number theoretic functions in 1934 via his Equational Catalyst. He viewed it as a heuristic principle that the informal concept of finite computation can be captured by suitably general recursions.
Refining and generalizing a notion of finitistically calculable functions due to Herbrand, Godel defined a number theoretic function to be general recursive just in case it satisfies certain recursion equations. And its values can be determined from the equation by simple steps, namely replacement of variables by numerals and substitution of complex terms by numerical values. When he gave this basically definition in 1934, Godot was not really himself convinced that the underlying precise concept of recursion was the most general one. And Basically he expressed his doubts in conversation with Alonzo Church.
In 1936, two years after this, Church published a bold conjecture, nowadays we call it Church Thesis, that only recursive functions are computable. A few months later, independently of Church, Turing also published a powerful speculative proof of a similar conjecture. Every computable real number is computable by the Turing machine. Through this basically series of publications, Gödel found Church thesis thoroughly unsatisfactory, But later he was convinced to Turing's publication by basically Church thesis.
But then again he later worried about a possible flaw even in Turing's argument. Here is a statement by Church. Godel has proposed a definition of a term recursive function in a very general sense. In this paper, a definition of recursive function of positive integers, which is essentially Godel's is adopted, and it is maintained by the notion of an effective calculable function of positive integers, should be identified with that of a recursive function, since other plausible definitions of effective calculability turn out to yield notions that are either equivalent to or weaker than recursiveness. This is basically the gist of Church's lambda
calculus. So Church thesis in a nutshell, also known as, you know, basically lambda definability. The notion of an effectively calculable function from natural numbers to natural numbers should be identified with that of a recursive function. Basically, the thing is that when Church talked in his essay about functions, he meant total functions, not partial functions. I will talk about this concept of functions and the empiriciveness as soon as we wrap up this historical debate. Around the same time, Stephen Clean improved
on Church thesis by extending it from total functions to partial functions. Originally, Church hypothesized that every effectively calculable function from natural numbers to natural numbers is definable in his lambda calculus. But Godel didn't buy that. He basically, in another essay, 1935, he wrote to Kling about his conversation. wrote to Colleen about his conversation with Godel, about Godel's doubts about this lambda definability. He says, in discussion with him, Godel, the notion of lambda definability
developed that there was no good definition of effective calculability. My proposal that lambda definability be taken as a definition of it he regarded as thoroughly unsatisfactory. I replied that if he would propose any definition of effective calculability, which seemed even partially satisfactory, I would undertake to prove that it was included in lambda definability. His only idea at the time was that it might be possible in terms of effective calculability as an undefined notion, to a state, a set of axioms which would embody generally accepted properties of this notion, and to do something on this basis. Basically Church and Gödel took the evaluation of function in some form of the Equational
Calculus as the starting point for explicating the effective calculability of number-theoretic functions. And Church basically generalized broadly, and evaluation is done in some logical calculus through a step-by-step process, and the steps must be elementary. Church argued that functions whose values can be computed in this way must be generally recursive, and this is basically the idea of general recursivity. Godel, in contrast, made this basically penetrating observation. The rules of the equational calculus are part of any adequate formal system of arithmetic, and the class of calculable function is not enlarged beyond the general recursive one,
if the formal system is strengthened. Godel basically formulated the significance of his observation as follows. He says, Tarski has a stress in his lecture, and I think justly, the great importance of the concept of general recursiveness, or Turing's computability. It seems to me that this importance is largely due to the fact that with this concept, one has for the first time succeeded in giving an absolute definition of an interesting epistemological notion, i.e. one not depending on the formalism chosen. In all other cases treated previously, such as demonstrability or definability, one has been able to define them only relative
to the given language, and for each individual language it is clear that the one thus obtained is not the one looked for. For the concept of computability, however, although it is merely a special kind of demonstratability or decidability. The situation is different. By a kind of miracle, it is not necessary to distinguish orders. And the diagonal procedure, you know, Canturian diagonal procedure, does not lead outside the defined notion. He continues, Sorry, that was basically quote.
So I think at this point, before moving a little bit to this historical context and you know, showing basically how this idea of computability merges, for those of you, I mean, it would be fantastic if you can have a very small discussion about this idea of recursion and recursivity. I'm sure some of you guys have already have some definition in mind. It would be fantastic if you give me what you think a recursion or recursive procedure is. So precisely because recursion is used widely in formal systems,
but also it has different uses, basically, and different applications in different domains. For example, in theory of abstraction, theory of language, theory of computability, so on and so forth. So any of you can give me a good definition of recursion, at least something that gives us some conceptual, intuitive background about the formal concept of general recursivity in the theory of computability. So I guess in programming, at least, in computer science, it's this very widely used notion
of self-referential computable steps, on a present this sort of framework for a computation that sort of intrinsically has some of the next step of it, so kind of is like this depth of computation instead of this width of computation, I would say. Superb, yeah, self-referentiality, I think, is the most concise way of putting it. Okay, so basically there is a kind of a very strict philosophical definition of recursion and even prior to self-referentiality, and self-referentiality is in fact the conclusion
of this definition. This has been put forward basically in the 1950s, basically at the intersections of linguistic theories, basically a study of syntax, theory of computation, proof theory, mathematics, etc. The thing is that, according to a strict definition, is that a recursion is the embedding of a constituent within the same, but also different, but mostly the same, of the category of constituents.
So embedding of one constituent within the same category of constituents. Now, it would be actually useful to talk about this recursion, but even though it's a kind of excursion from our discussion. When you see, there is a difference between the procedure of iteration and the procedure of recursion. Iteration, very intuitively for you guys if you want to think about it, iteration is a form of operation that you do not need to proceed. You can proceed in spite of the action previously performed.
Whereas in recursion, you proceed by virtue of the action already performed. An intuitive example of this in cooking, cut the garlic into paste. That's iteration. You basically cut the garlic into paste without needing to know what your previous action was until it becomes paste. Whereas cut this pizza into eight pieces. You have to cut this and proceed according to the previous cut you made. So you can get basically eight pieces out of this pizza.
Now, this is basically the most basic definition of rudimentary account of iteration and recursion. Now, recursion, so iteration basically allows you to concatenate constituents without restriction. You can put a, you have, for example, a repertoire of discrete alphabets of letters, A, B, C, D. You can put A, B, D, C. You can put B, C, D. Any kind of order, you can make these concatenations, basically. Whereas recursion is a form of embedding. Basically, it's a form of, it's exactly like our pizza example.
Your action that you, in each time you perform, embeds a piece of your constituent within the constituent that you have already established. So hence it creates a memory system, basically a memory between your constituents. And this allows for establishing of dependency relations between the constituents of your category. So two things are very important about recursion. Recursive operations or recursive embedding allows for the instantiation of two things, hierarchies and dependency relations between your constituents and your actions.
And precisely because of this embedding of constituents within the category of the same constituents, within the same category of constituents, you have a self-referential, basically system, a self-contained, basically system. Now, the thing is that this has been massively studied in evolutionary biology, in basically cognitive science, that it seems that there is a connection between performing of recursive
basically operations and the evolution of basically intelligence. What you briefly put is that the way that, for example, this idea is formulated, for example, in cognitive science or in evolution of biology is that basically this idea of embedding of constituents within the same constituents that allow you to encode dependency relations between your constituents, between your actions, provides you with a minimal regime of abstraction, minimal tool or system of abstraction. There's also what we talked about
at the beginning about the Go thing, about chunking. It's the idea that you can basically that you can basically contract massive amounts of information that are otherwise really hard to contain within a very encapsulated regime of dependency relations. Right, so in the context of like a program, right, in a conventional programming language, so usually when you would use iteration it would be connected to some sort of termination
condition, so it would be like while this condition holds to these things, right? So whereas the way you're sort of describing iteration is almost like it doesn't have the condition attached to it. I think... Sure, and that's basically the distinction between the formal, at least in the way that as computer science talks about it, and the kind of way that, for example, the more general concept of recursion is being studied, for example, in language, cognitive science, so on and so forth. Yes, it doesn't have, obviously, these kinds of constraints. But nevertheless, there is a kind of common ground,
and that's really hierarchical embedding and encoding of dependency relations that allow you to have self-preferential, self-similar, self-contained systems. You see, I don't know, a translation of this, I guess, though, in programming languages where if you have a loop, like a while loop, versus a recursive function, if you're strict about the way you treat state, If you say that the recursive function can only take state as a parameter, that there's no other way of getting at it, then you get all the dependency relations encoded as parameters to your function.
Whereas in an iterative sort of expression of the same thing, the state will be less foregrounded, it will be a bit more implicit in the way that that block of code works. I think there's some straightforward examples that I could give, if this is useful for other people. But I would also say that in programming, the construct of recursion is just purely cosmetic. Like what the compiler is doing or what the runtime is doing is always going to be iterative. Yeah. Yes, that's true about programming.
But it needs to be, again, within the computer science, there's a distinction between the formal recursivity, basically computational theoretical undergirding, and kind of a method of applying recursion. As you say, it's more of a cosmetic makeup. I think that they need to be, again, distinguished. But there are still, I think, there are underlying common, basically, elements between all of these. It goes back to this idea of the way that cognitive science and evolution biology talks about,
and especially linguistics recursion is talked about, is that recursion, so with recursion, you can generate rules as you encode dependency relations between constituents. And then because you embed constituents within the same category of constituents. But I guess it's this embedding bit, which is really interesting. This is where sort of the model of computation sort of breaks down. You know, you can sort of imagine in computer programming that you have, you know, a stack where the next step is determined by the previous step, and you have this sort of state. In category theory, you have sort of like this automorphism,
which is kind of just acting upon itself. But there is some kind of distinction there. Is the state of the category is somehow changing even though it's like a new form, our new differentiation of the category. A new construct, yes. Yeah, so I'm trying to figure out how to frame it, but it's clear that sort of like the, in sort of these recursive morphisms where the sort of are predicated on the domain being the co-domain, and then there's some kind of external parameterization which is changing, like the outcome. But I don't know where that memory is coming from. So yeah, I'd be curious if you could sort of... That's a really good question. I need some thought.
It is actually, that is completely true. That is completely true in category theory. Also constructive type theory and multiple type theory. We have the same kind of, basically, instantiation of new constructs that have different properties. But in the sense of memory, I really need to think about where this memory exactly coming from, or exactly how we can frame or attribute this memory to what kind of particular feature of basically the categorical structure. I need to think about this. But I think there's, coming up with a half-brained idea here,
I think there is a sort of duality between sort of iterating either on the object or on the space itself. And it seems like there's some kind of an iteration, you're kind of moving around within the same category. And in recursion, you're somehow transforming the category around sort of a fixed point. It is kind of like the state is some different instantiation of the category instead of some different instantiation of the object, which would be more iterative, so almost vertical versus horizontal. I think there's some kind of . Yes, yes. No, I know what you are saying. And I think this, are you familiar with the concept of UNEDA lemma? The UNEDA lemma? Yes. No.
It is basically the most powerful and the most trivial tool of category theory. Simply, it's the most, it's basically a phenomenological tool applied to category theory. And it has exactly the same what you were talking about, this transition between iterations of morphisms and recursion of morphisms allow you to make these kind of local global transits between basically simply decomposition of categories to more rudimentary categories with the same property
or constructing or basically composing completely complex categories that are, you know, don't share any common properties with, you know, the category or the set that basically you you have embedded using the Unida embedding. I will try to write a little bit of note on this. Actually, it's quite really interesting, this idea of recursion iteration and what you are saying in terms of different embedding. Because iteration also have embedding. You can have iterating procedures. You can also have embedding procedures. But the recursive embedding is really the idea of that category of constituents that allows for creation of hierarchical, self-contained,
but also encodable dependency relations, diversification of dependency relations. That Ersman's model of category neurons that I talked about, actually I think some of the the stuff that I mentioned are the weak point of response model, I think can be done. And I gave it some rudimentary thoughts by way of how we can move from the concept of co-limit construction, which is purely basically a recursive kind of embedding in the sense that we talked about, to a unique dilemma of construction that allows us to both basically prune understanding what pruning is,
and for example, in neural architecture, but also what construction is. How some connections can be eliminated, but how some connections can be basically new connections can emerge. And I will talk a little bit about this in the classroom page. Yeah, so anyway, back to our, before getting into the rest of our historical story. You see, with cognitive science, the way that, so recursivity, as I said, allows for encoding of dependency relations. It gives rise to basically a power of simulating or abstracting self-similar structures.
And self-similar structures are quite powerful in simulating technologies, basically. They are rudimentary, but they are powerful. There is a reason, for example, when we do abstract intuitively, we usually abstract by way of these kinds of chunking methods, you know, contracting massive amounts of dependency relations in favor of kind of broad, long distance rule between basically levels of dependency relations or, you know, self-stimilar basically regimes. But this is also, there is, cognitive science has, there are some good studies on this,
empirical studies, that showed that basically studies that in this sense, a recursion is very prone to transfer of bias, cognitive biases. Wherever you have abstraction by way of self-similar self-contained, basically encoding processes, you have transfer of biases. Because once you start to embed the constituent of one category within the same category of constituents and create these massive amounts of dependency relations, you have long distance rules. will start to transfer basically whatever that was in the memory of your history of
your encoding to basically the rest of the structure, the rest of dependency relations. So if you had a bias at one basic level, at the most elementary level of your recursion, elementary level of your dependency relations, recursivity can basically transfer this bias down the line. Basically, it creates a completely biased regime that has been transferred from biases at the level of most basic dependency relations to the highest dependency relations. So it is intuitions, at least in the way that, for example,
we talk about this in the sense of that kind of sensory motor processing of information. And with a kind of creative, the so-called mode of reasoning that requires basically intervention of meaning are very prone, in fact. Or in fact, are using massively these kinds of simulating, encoding, abstracting tools, which are recursive in their structure. And because of that, they are extremely prone to transfer biases from at the most basic level
of dependency relation between your constituents to the highest level of dependency relations. We can see this basically in any form of habits of thinking. Habits of thinking, in fact can be thought in a very romantic sense, in the sense of this recursivity in the way that evolution and biology talks about it, namely creating self-similar basically regimes or creating this long distance dependency relation. Wherever you have long distance relation, basically your structure is susceptible, as I said, to transfer biases from elementary levels to the highest levels.
precisely because of this, you know, memory preservation between your levels of dependencies. And I think somehow we have the same kind of, not the same, we have a kind of a similar thing to this, to this transfer of biases because of the embedding and preservation of memory between dependency relations.
in classical logic. And basically, that's the structural rules in classical logic, contraction and weakening, monotonicity and potency of entailment, where basically, you can transfer. You can add copies of your premises that don't change your hypothesis. You can basically transfer your premises without any restriction and perceiving as if your hypotheses are not being changed. So at this level, I mean at this rudimentary definition
of recursivity as a sort of operation that gives rise to structures that are prone to transfer biases, we can make a connection in fact between those kinds of abstract intuitive creativities that we do regularly in everyday life, and they are in fact, you know, have biological evolutionary, you know, basically, roots, and, you know, the kind of, as strong
structural rules of classical logic, that precisely uses these kinds of, again, these kinds of forms of abstraction. And precisely because of that, it creates these extremely powerful systems, but nevertheless really weak when you look at them. And this is something I will talk about this more thoroughly when I talk about Jean-Yves Girard's substructural logic and his critique of classical logic and his refinement of it, way that the rule, idempotency, structural rules such as idempotency and monotonicity of entire movement are terminated or eliminated in Girard's version of logics, precisely
because in order to mitigate this bias transfer. So that was just kind of like an excursion to this idea of a little bit of a recursion and intuitive idea behind what recursive operation is and what it basically generates. So back to our debate about effective calculability and general recursion among Church, Godel,
Turing, and Stephen Klein. So I said that during the 1930s there's this debate between Church, Godel, Klein, and Turing. During that time, I said that Church had this correspondence with basically Klein and Godel that he tries to argue why his thesis about effective calculability in fact isn't susceptible
to Godel's objection. In that timeframe, basically, Church says something like this, that evidently it occurred to him to Godel that Herb Rahn's definition of recursiveness, which has no regard to effective calculability, could be modified in the direction of effective calculability. He made this proposal in his lectures, and at that time he did specifically raise the question of the connection between recursiveness in this new sense and effective calculability, But said he did not think that the two ideas could be satisfactory, identified, except heuristically.
Effective calculability, the informal concept of computability, and general recursivity, qua rigorous and formal concept of computability. The lectures of Godel that Church mentions in that passage were given at the Institute of advanced study in Princeton. In 1965, Godel wrote, however, I was at the time of these lectures not at all convinced that my concept of recursion comprises all possible recursions. Soon after Godel's lectures, Church and Kline proved that the Herbrand Godel notion of general recursivity
is equivalent to lambda definability, the idea of effective calculability as far as total functions are concerned. And Church became sufficiently convinced of the correctness of his thesis to publish it. But Godel still remained unconvinced. Indeed, the question is why should one believe that lambda definability captures the notion of computability? Why the informal notion of computability as encapsulated within effective calculability indeed, basically, captures the robust notion of computability. So that's a question itself.
The fact that lambda definability is equivalent to general recursivity and to various other formalization of computability that quickly followed Church's paper proves only that Church's notion of lambda definability is very robust. To see that the mathematical definition captures the notion of computability, one needs an analysis of the latter. And this is basically what Turing provided to justify his thesis. And this is Turing's thesis as complementary to Church's thesis. Let sigma be a finite alphabet, a partial function from strings over sigma to strings over sigma.
So basically, the sigma or refer to our final alphabet, they are both of the same kind. Let sigma be final alphabet. The partial function from strings over sigma to strings over sigma is effectively calculable, if only and if it is computable by a Turing machine. Turing designed his machine to compute real numbers. But the version of the Turing machine that became popular works with the strings in a fixed alphabet, hence the Phoenician, mapping one string over sigma to another string over sigma. Turing analyzed the computation performed by a human computer, as I briefly mentioned,
by a machine he meant as a human computer. He made a number of simplifying without loss of generality assumptions. Here are some of them. The computer writes on graph paper. Furthermore, the usual graph paper can be replaced with a tape divided into squares. The computer uses only a finite number of symbols, a single symbol in a square. The behavior of a computer at any moment is determined by the symbol which he is observing and his state of mind at that moment. There is a bound on the number of symbols observed at one moment.
Turing says, we will also suppose that the number of states of mind which need to be taken into account is finite. If we admit it, an infinity of states of mind, some of them will be arbitrary, close, and will be confused. He ends up with Turing machines, simulating the original computation. Essentially, Turing divides his thesis from more or less obvious first principles, though he didn't state those first principles carefully. It seems that only after Turing computation appeared, writes Stephen Klein in 1981, did Did Goethe accept Church thesis, which had then become the Church-Turing thesis?
Turing's argument, he adds, eventually persuaded him." So this addition of Turing, basically, of partial effective calculability and general recursive in terms of partial functions to effective calculability thesis, or lambda definability of Church, basically became the body, the skeleton, of what we call the Church-Turing thesis, or the theory of computability. Church's lambda calculus was destined
to play an important role in programming theory. You know, the mathematically elegant Herbrand-Gaudel clean notion of partial recursive functions served as a spring word for many developments in recursion theory. The Turing machine gave us honest step counting and became eventually the foundation of computational complexity theory. Very quickly, the Church-Turing thesis acquired the status of a wide shared belief. Meantime, Gödel grew increasingly skeptical of at least one respect of Turing's analysis. In a remark published after his death, Gödel writes this. So Gödel was always very skeptical of this theory
of computability as formulated by Church, Turing, and Stephen Klein. This is what Godot writes, a philosophical error in Turing's work. Turing in his 1937 paper gives an argument which is supposed to show that mental procedures cannot go beyond mechanical procedures. However, this argument is inconclusive. What Turing disregards completely is the fact that mind, in its use, is not static, but constantly developing, i.e., that we understand abstract terms more and more precisely as we go on using them,
and that more and more abstract terms enter the sphere of our understanding. There may exist systematic methods of actualizing this development, which could form part of the procedure. Therefore, although at each stage the number and precision of the abstract terms at our disposal may be finite, both and therefore also Turing's number of distinguishable states of minds may converge toward infinity in the course of the application of the procedure." So Godel is famous that Godel was extremely cautious in his writing, very careful person when he's using vocabularies and terms.
So it's not clear whether the remark in question was intended for publication or not. As I said, this was part of his writings published after his death, unpublished stuff. In any case, the question whether mental procedures can go beyond mechanical procedures is something that we will talk about at the end of this module in the next module, especially in the sense of developing this kind of dynamic rather than a static picture of mind, a dynamic rather than a sequential one. That at each step, you have the streams of input into your system. And that basically becomes, we can only
do that by way of that kind of interactive model of computation, a computational picture of language. So this is something that we'll come back to it. So nevertheless, Turing did not intend to show that mental procedures cannot go beyond mechanical procedures. In basically Turing's essay, the expression A state of the mind was just a useful metaphor that could be, and in fact, was eliminated. We avoid introducing the state of mind by considering a more physical and definite counterpart
of it," remarks Turing. But to entertain the possibility of this Godel's note and skepticism of Turing's work, let's consider the possibility that Godel didn't speak about biology either, or biological cognition in the sense of a state of mind. That he continued to use Turing's metaphor and worried that Turing's analysis does not apply to some algorithms. You see, so if even we rule out that, in fact, when Godel talks about state of mind, he means a state of cognition as we know it's a state of human mind, but simply a state of mind in the sense of mechanistic sense that Turing deploys it, then because we talked about it,
in that mechanistic sense, a state of mind are simply sequential algorithms, or Turingian algorithms. So then this means that what Godel really was basically trying to say was that talking about the need for giving rise to a new model of algorithms rather than the sequential, mechanistic, effective calculability algorithms that have been provided by Church-Thering thesis. And this is something that we will cover. Can an algorithm learn from its own experience, become more sophisticated, and thus compute
a real number that is not computable by the Turing machine? Note that the learning process in question is highly unusual because it involves no interaction with the environment. This is the kernel of fundamental theory of computation as interaction, as in contrast with theory of computability as provided by Church and Thierry. And Godel really was more interested in a fundamental theory of computation. What is exactly computation? How is it performed? kind of processes it consists of.
So to repeat, note that the learning process in question is highly unusual because it involves no interaction with the environment. On the other hand, it is hard to stop brains from interacting with the environment. gives two examples illustrating the situation, both aimed at logicians. Note that something like this indeed seems to happen in the process of forming stronger and stronger axioms of infinity in set theory. This process, however, today is far from being sufficiently understood to form a well-defined procedure. It must be admitted that the construction of a well-defined procedure, which could actually
be carried out and would yield a non-recursive number theoretic function would require a substantial advance in our understanding of the basic concepts of mathematics. Another example illustrating the situation is the process of systematically constructing by distinguished sequences alpha, subset n, arrow, alpha, all the recursive ordinals of the second number class. Now, the logic community wasn't swayed. I think it is pie in the sky, wrote clean. Here is a more detailed reaction of basically Stephen Kling to this.
But as I have said, our idea of an algorithm, his reaction to Godel's skepticism, but as As I have said, our idea of an algorithm has been such that in over 2,000 years of examples, it has separated cases when mathematicians have agreed that a given procedure constitutes an algorithm from cases in which it does not. Thus algorithms have been procedures that mathematicians can describe completely to one another in advance of their application for various choices of the arguments. I said that basically the choice of the language is no longer important at that point. How could someone describe completely to me in a finite interview a process for finding
the values of a number-theoretic function, the execution of which process for various arguments would be keyed to more than the finite subset of our mental estate that would have developed by the end of the interview? The total number of mental estates might converge to infinity if we were immortal. Thus, Godel's remarks do not shake my belief in the Church-Turing thesis." Now, if Godel's remarks are intended to attack the Church-Turing thesis, then the attack is a long shot. On the other hand, in contrast to what Stephen Klein says here in theoretical computer science has been basically at the center of controversy in the last couple of decades. Even though
the notion of algorithm is richer these days, it is less well understood. In fact, there are more questions as to what an algorithm actually is. And this is something that we'll We'll talk about next session, sequential algorithms and new forms of algorithms and interactive algorithms and so forth. And of course, there are algorithms of modern and classical varieties, not covered directly by Turing's analysis. For example, algorithms that interact with the environment, algorithms whose inputs are abstract structures, and geometric, or more generally, nondiscrete algorithms.
computational but not digital or sequential. So for those of you who are not familiar with some of these basic definitions in computer science, it's important when people, especially in this kind of cultural climate, everyone talks about algorithms. And people really throw these words around in a very confused manner. First of all, not algorithms mean the same thing. Nobody really knows what an algorithm is, even
in the most fundamental basic level. Algorithm doesn't essentially mean digital computation. Algorithm doesn't essentially mean computation. There are all of these, basically, subtleties involved. So when we are talking about these issues, everything basically needs to be carefully examined according to a specific criteria. So let's take a step back in our history lesson, getting back to Church and Godel debate, you know, prior to the emergence of computability theory, also known as Church-Thering thesis. And there's basically the argument for Church's claim.
And that the so-called lambda definability. versus Godel's basically formal concept of computability, which is defined by general recursivity. So what is the argument for chair-scaling and what could be for Godel's? If one uses the strategic considerations underlying the proof of Cline's normal form theorem, it is in both cases easily established that the functions calculable in the broader frameworks
are general recursive, as long as the steps in the logical systems are elementary, formal, that is, general recursive. Church turned the elementary steps explicitly into general recursive ones, whereas Godel could not but exploit the formal character of the theories at hand through their recursive presentation. Taken as principled argument for the thesis, Goodell's and Church's considerations rely on a hidden and semicircular condition for steps. Hilbert and Bernice move this step condition into the foreground when investigating calculations in deductive formalism,
in the chain of deductions, and reconnable functions. They impose explicitly recursiveness conditions on deductive formalism and show that formalisms satisfying these conditions have as their calculable functions exactly the general recursive ones. In this way, they provided mathematical underpinnings for Godel's absoluteness claim and for Church's argument, but only relative to the recursive conditions, the relatively recursive conditions. The crucial one requires the proof, predicate of the deductive formalisms, and thus the steps in formal calculations to be primitive and recursive.
The work of Godel, Church, Kline, and Hilbert, and Varneyse had intimate historical connections, and is still a deep interest in philosophy of computer science. It explicated calculability of functions by exactly one core notion, namely calculability of their values in logical calculi via a finite number of elementary steps, primitive steps. But historically, no one gave convincing and non-circular reasons for the proposed rigorous restrictions on steps permitted in calculations.
The question is whether this stumbling block for a deeper analysis can be overcome. The answer lies in a motivated and general formulation of constraints on steps. Church reviewed in 1937 the two classical papers by Turing and Emil Post, another basically father of computability theory, which had been published in 1936. When comparing Turing computability, general recursiveness, and lambda definability, Church claimed the first of these notions has the advantage of making the identification with effectiveness in the ordinary, not explicitly defined, sense evident immediately.
Church reasons in the following manner. non-effectiveness as computability, then arbitrary machines subject to restrictions of finiteness would seem to be an adequate representation of the ordinary notion. Basically the finiteness restrictions require that machines occupy only a finite space and that their working parts have finite size. Turing machines are obtained from such finite machines by further convenience restrictions, but these are of such a nature obviously to cause no loss of generality. So as I said, the idea is that Turing machine is causing no loss of generality, but is basically
developed by introduction of basically restriction on size and the steps in the machine procedure. Now the thing is that when we talk about just moving a little bit forward, when we talk about the interactive theory of computation, basically the theory of computation is provided once at the same time observe the generality of the Turing machine, but at the same time show that the model of computation differs once you relax these restrictions.
Different computational phenomena enter into equation. And that's what we will talk about, how the relaxation of these restrictions lead to a different model of computation, as different from the model of computation encapsulated theory of computability of Church and Turing. Church then observed completely reversing Turing sequence of analytic steps. A human calculator, provided with pencil and paper, explicit instructions can be regarded as a kind of Turing machine. It was obviously captured by the machine image and saw in it the reason for deep interest
of Turing computability notion. In sum, we have arrived at three church canons in support of the thesis, namely one, the confluence of notions, two, the step-by-step recursive argument, and three, the immediate evidence of the adequacy of a Turing's notion. But in his reviews, Church failed to recognize two crucial aspects of a dramatic shift in perspective. One aspect underlies the work of both Turing and Post, whereas the other is the Turing's. The first aspect becomes visible when Turing and Post. Instead of considering schemes for computing the values of another's theoretic functions,
have identical symbolic processes that serve as building blocks for calculations. In order to specify such processes, Emil Post uses a human worker who operates in a symbol space and carries out over a two-letter alphabet exactly the kind of operation the Turing machines can perform. Post expects that his formulation would turn to be equivalent to Godel's Church development. Given Turing's proof of the equivalence of his computability notion with Church's lambda definability, Post's formulation is indeed, you know, can be called equivalent.
Post asserts that Church's identification of effective calculability with recursiveness be viewed as a working hypothesis in need of continual verification. In sharp contrast, Turing's attempts to give an analytic argument for the claim that these simple processes are sufficient to capture all human mechanical calculations. Turing exploits for his basically reductive argument broad constraints that are grounded in limitations of relevant capacities of the human computing agent. This is the second aspect of the novel perspective that made for genuine progress, and it is unique to basically Turing's works.
When Post proposed his worker model, at no place did he use the fact that a human worker does the computing, whereas Turing, who seems to emphasize machine computations, explicitly examines human computations, called a human computing agent who proceeds mechanically a computer. Such a computer operates on finite configurations of symbols and for Turing deterministically. So the computer hovering about in Turing's paper is such a computer. And Wittgenstein appropriately observed about Turing machine that these machines are humans who calculate as we talked about. But how do we step from the calculation of computers to computations
of Turing machines? When Turing explores the extent of computable numbers or equivalently of effective calculable functions, he starts out by considering two-dimensional calculations in a child arithmetic book. Such calculations are first reduced to computation of a string machines, and the latter are then shown to be equivalent to computations of a letter machine. Letter machines are ordinary Turing machines operating on one letter at a time, whereas string machines operate on finite sequences of letters. In the course of this argument, Turing formulated broadly motivated constraints.
The argument concludes as follows in Turing's 1936 paper. We may now construct the machine to do the work of the computer. The machines just described as string machines do not differ very essentially from computing machines as defined in the section two of my letter machines. And corresponding to any machine of this type, a computing machine can be constructed to compute the same sequence, that is to say the sequence computed by the computer. So this whole idea of the equivalence between the letter machine and the string machine becomes giving rise to this idea of computer machine equivalent to the human computer.
We will talk about this when we are criticizing the strong interpretation of Church-During thesis and how this has been turned into this kind of a dominant culture of basically algorithmic replication of cognition, some of the really kind of controversial discussions in kind of canonical textbooks of computer science, et cetera. For the presentation of Turing's argument, it is best to consider the description of Turing machine as post-ML post-production system. This is most appropriate for the reason
this description reflects directly the move in Turing's 1936 paper to eliminate a state of mind for computers in favor of more physical mechanistic counterparts. More importantly, it makes it clear that Turing is dealing with general symbolic processes, whereas the restricted machine model that results from this analysis almost obscures that fact. Now I mentioned about these restrictions that Turing imposes on basically symbolic processes and they are at the core of the Church-Turing theory of computability.
These two restrictions are usually defined by boundedness and locality. So very briefly, the constraints Turing imposed on symbolic processes derived from a central goal of isolating the most basic steps of computations, that is, steps that need not to be further subdivided, important, most primitive steps, as I said, elementary steps. This objective leads to demand that the configurations, which are directly operated on, must be immediately recognizable by the computer. So the elementary steps is basically demand is a necessary condition for recognizability
by a computer. This demand and the evident limitation of the computer's sensory apparatus motivate most convincingly two central restrictive conditions. Boundedness, i.e. a computer can immediately recognize only a bounded number of configurations. And the second one is locality. A computer can change only immediately recognizable configurations. Let's look at this diagram.
So Turing's considerations leading from operations of a computer on a two-dimensional piece of paper with tape to operations of a letter machine on a linear tape are represented schematically in diagram. Step one, from calculability of number theoretic functions to calculability by computer satisfying bottomless and locality, indicates Turing's analysis.
Whereas step two refers to Turing's central thesis, asserting that the calculations of computer can be carried out by a string machine. And basically, the sum of the step two and the equivalence proved between a string machine and a letter machine, between basically a letter computer as we understand it nowadays, and a human computer, which as I said, what's projected in the equivalence between a letter machine and a string machine is called the equivalence proof, which is captured in the step two. Basically, in addition, once added to the step one,
it basically yields computability by letter machine. And ultimately, the idea that basically what a computer does in the sense that we understand computers is precisely what human reasoning does. Some well-motivated ideas can be formulated for computers. They operate deterministically on finite configurations, one. Two, they recognize in each configuration exactly one pattern from a bounded number of different kinds of such.
Three, they operate locally on the recognized pattern, boundedness and locality. Four, they assemble the next configuration from the original one and the result of the local operation. So these were basically, as I said, locality and boundedness where the restrictions through which computability theories in its current state and our definition of computers basically emerge. And basically the Church-Turing theory of computability becomes the canonical theory
of computation. And in theoretical computer science in the past few decades, assaults have been made against precisely these two key restrictions that Turing imposes in order to create the equivalence proof and basically, you know, elevate theory of computability to the Nicole theory of computation. So summary to finish this session. One, computability theory is concerned
with computability of extensional objects. Extensional objects, you can think of, for example, two functions yield the same number. And then these two functions can be said to be extensionally the same or equivalent. So computability theory is concerned with computability of extensional objects, numbers, sets, functions, et cetera. These objects, existential objects, are inherited from mathematics and logics. Computability requires additional structure, an algorithmic process for computing the sets or function. We talk about primitive steps and effective calculability and other stuff. So computability, in this sense, relies on characterization
of algorithmic processes, especially sequential algorithms. In computability theory, we have a confluence of notions, a definitive calculus of functions, which is the lambda calculus proposed by Church, and axioms of extensionality. And axiom of intentionality for sets, we have the following, basically. Can be said that a set is completely characterized by its members. And functions, we have the idea that a function is completely characterized by the input-output correspondence, i.e. the first set of input-output pairs which it defines.
So this is basically the mathematical definition, actually very rudimentary definition of function mathematics. There is also the argument from the continuity that's a different, actually gives rise to a completely different interesting computational definition of algorithms. The property of functions, basically, is intrinsic if it can be defined purely in terms of f, f that maps a to b, as a set of input-output pairs and any structure pertaining to a and b, more formally, using only bounded quantification over the structures
a and b. In order to define whether a function is computable, we need to refer to something external, a process by which f is computed. A function is computable if there is some algorithmic process which computes f. And what is computable? Process. And that basically becomes a question for us to move in the third session of this module to interactive theory of computation. So very briefly, the idea is that the theory of computability basically at its core uses the canonical mathematical
definition of function. And basically uses sequential algorithms to basically capture the canonical definition of function. But the thing is that in using the canonical definition of function, theory of computability in Church-Turing thesis, as I said, needs to refer to something external, to something that is not really, cannot be defined in terms
of function, a process by which F itself is computed. You know, it's a move again to a degree even deeper, you know, beyond the domain of the function in the sense that mathematically it's understood, the domain of processes. The thing is that, and this is basically where contemporary theoretical computer science is focused on, the formalization of processes and developing theories of computation that are directly working with processes rather than functions.
And this is something that I will talk about more elaborately in the course of the next session. So that was just kind of like a historical background of the concept of computability, formalism, some of the debates involved in it, and the consequences of the emergence of computability theory, at least in the church theory in sense. So any questions, any arguments, any observations, anything would you appreciate? Maybe I should have asked this earlier in the sequence because I think it's a pretty
simple question. Do you think there's an aspect in which Church Turing is just defining what was previously a pretty loose concept? So rather than being a thesis, it's more like a definition or a premise in the way that it sort of gets worked? It is a thesis. I mean, in the sense that in Logix they say it's a thesis, it's not a theorem. Yes, as you say, it simply makes highly, you know, astringent and effective a very loose, basically definition or a confluence of definitions that have been around since the Middle Ages
in logics and mathematics. Yes, absolutely. But nevertheless, it is, you know, I will talk about even the sequential regime or this kind of very straightforward computability theory. It is extremely powerful in the way that they developed it. It was quite an astonishing feat. But nevertheless, I think the thing is that, you know, Turing himself was quite a very open-minded person. had this habit of being very open to future developments and future, basically, correction
of his insights. He always very cautiously moves in his papers. And the way that he, in fact, developed this theory of computability and Turing machine, he left open, in fact, In fact, he actually says it. He leaves open room for development of new models of computation that are not sequential. Questions? Tal, Steven, Victor, Adam, Sean, Aaron, anyone?
I guess in the absence of other questions, the other thing that I was reading through is the Millikan paper, the Ruth Millikan paper on... Yes. Push Me, Pull Me. Push Me, Pull You Representations. Pull You, sorry. Right. Yeah, yeah, correct. And that seems to be setting a stage for sort of these representations as tokens in a game, I guess, or as sort of meaning primitives.
Is that sort of what you're finding to explore? Yes, absolutely correct. in the game. I think Milken is a really interesting philosopher. She's very systematic. But she's also, when you look at her stuff, she comes up with really some insightful stuff, especially it's kind of really interesting about the bees and basically they have the proto-semantic system of normativity. She's a right-wing Szilardzian, basically. Basically, she wants to show that normativity has evolved from this naturalistic component. In fact, you
can have that naturalism and still be able to explain normativity without actually having simply the normative regime as such. You need, so in order for you to have like basically this whole idea of reason and cause duality or you know, norm nature duality, she wants to basically show the primacy of nature when it comes to norms and or causes against reasons. So this is basically a tenet of the right-wing Szilardzianism, whereas the left-wing Szilardzian of the Brandenburg and MacDowell, they want to emphasize the primacy of norm and reason
of nature. Now the thing is that I think in Milliken's idea, I mean, it is interesting that yes, these are representational components. For example, the dance of a bee is basically what this representation requires in order to be a representation. It needs a mapping from how objects affect the organism, namely the sensory input, a sufficient a structure or a sufficient wiring that mediates this input and turn it into a behavioral output. So a sufficient structure. So this representation is basically not a linguistic representation
in American sense. It's a representation that happens, that takes place between two natural items, between the wiring structure of the dancing bee and basically how it is affecting it is affected by the objects of Kantian sense impressions. So I think this is, yes, basically, we talked about in terms of indexical sign and the causal interpretations and stuff. I think this is in fact the core representational core from which some of our, some, not all,
of our linguistic faculties have emerged. But also in that sense, it is a representation in quite a parochial sense, precisely because a token is the way that Melkin tries to formulate it. It's not a token. A token can be set a token once it solely stands in functional role with other tokens rather than to cause it. So that's the referentiality. The token in Millikan's system has a referential correlation with an object, namely its cause.
It's basically, as I said, the mapping between two natural objects, the wiring structure and basically, for example, a pattern occurrence in the environment. And that, for Milliken, is the representational mapping. Now this representational mapping cannot be even said to be a token because the tokenness of it, if there is such a thing, can only be defined in terms of how the organism is affected by a pattern and by virtue of having the sufficient wiring structure to turn this into a behavioral output. From that, the robust concept of a token, at least in the way that language or symbolic
regime they talk about it, is precisely the relation, whether it's syntactic, inferential, semantic, the relation stands to other tokens without, regardless of its basically referential correlation to an object. And precisely because of that, it is highly manipulable. A token that is not manipulable, that you cannot play with it and manipulate the rules of play and introduce new rules cannot be said to be a token. It's only a token in a very parochial sense. And that's why I think. MALE SPEAKER 1 So she is talking about these
as quite primitive representations in some sense. MALE SPEAKER 1 Yes. No, she's brilliant. She's really good. But I think Milliken also sometimes comes to these really bad confusions and makes these massive jumps. There is this book that I mentioned on the Google Classroom, Millikan and her Critics. It's a really interesting book because these people like trying to rip her arguments to shreds and then she also comes back and responds to them. It's very entertaining. But yes, this is basically the core of the Millikan theory that representation, basically, you don't need
essentially language in order to have representation, or norms, regime of norms, semantic norms to have representation. Because representation is just basically a mapping between two natural items, the wiring structure of an organism, for example, and pattern of occurrence in the environment. But it is representation. And it is, in fact, a representation that played an evolutionary role in how some aspects of our language evolved. But nevertheless, it cannot be set to be a representation the way that we linguistically define it, namely a piece of judgment, a piece of perceptual judgment.
Because for perceptual judgment, you need to have concepts. So it's more raw than that, in a way, right? Yes. Parochial, I meant it. Not parochial in a negative sense, but raw, crude, elementary, atomic. Okay. Yeah, no, that's good context. It's also interesting. I wasn't aware of Milliken's larger project in terms of sort of a naturalistic grounding, but I can see this connection to that where she's talking about how these PPR, the Push
Me Fully representation sort of form parts of what people perceive as the moral order as well. She doesn't spend a lot of time on it, but that's also an element of that paper where she's sort of saying these things are perceived as quite fundamental and sort of like having this moral force as well, these sorts of... Yes, yeah. I mean, that's the whole point that, you know, so many people, it's basically the idea that we talk about that basically so many of these biologically evolved mechanisms systems have turned into basically habits of thinking, habits of evaluation, habits of judgment. And the task of thinking is really to systematically dehabituate thought, gives rise to new habits.
And for that, basically we need to break away from our evolutionary heritage. And I think artificial general intelligence is a good, at least one aspect of this dehabituation process.