Now, this is third lecture on Turing machines. In the very first, I have introduced the notion of Turing machine and as a language acceptor, we have understood like how a language can be accepted by Turing machine, certain examples are there. And how to give the output, the notion of giving output in Turing machine is also discussed, we have fixed some notation for that and a computable function is introduced in the last class. So, using Turing machine, we have two things that one is computing a function from strings to strings, so called computable function or Turing computable function more precisely or as a language acceptor, where we talk like Turing acceptable functions, Turing acceptable languages or recursive language languages, this is what I have introduced. Then I started discussing about how actually a complicated Turing machine, a bigger Turing machine can be constructed through some of the Turing machines that you have already constructed. So, for which we have started looking at very basic machines, I have fixed the notation for the basic Turing machines namely left, the left moving Turing machine, right moving Turing machine and printing Turing machine, these are the basic three important steps that we perceive with a Turing machine. That means, at a given position the Turing machine, whatever it is reading, it will move, it will take one left move and simply halt. So, the Turing machine, such Turing machine I am representing it by L, similarly the Turing machine, whatever it is reading, it will take one right move and simply halt. So, for that we are representing it by R and I am calling for a given A in sigma the alphabet P A, Turing machine that prints simply A, whatever it is reading in the current cell, there it will print A in the symbol A and it will halt there. So, these are the three basic Turing machines, I am L, R, P A, of course this is for all A in sigma. So, these are the three basic Turing machines that we have looked at. Now, when I am talking about combination of some smaller Turing machines, first let me introduce a notation, what it indicates the meaning of that and those things let us first discuss that is as follows. If you take two Turing machines, now if I use the notation this m 1 say symbol A let me write here m 2. The meaning of this is this arrow indicates that this we start the process at the machine m 1, this arrow indicates that and the Turing machine m 1 with the whatever the input it will pursue and then whenever it is halting if it is reading A that is what is indicated on this arrow, whenever it is halting if it is if it is halting by reading A, it would not halt rather it will connect to the Turing machine m 2 and pursue the job whatever that m 2 is doing. Now, whenever m 2 halts this entire Turing machine will halt. So, that means essentially this Turing machine if I write m, the behavior of m is m 1 followed by m 2 with a condition that whenever m 1 is halting if the current reading symbol is A then it will proceed to connect to m 2 and process the input with that. So, that is how the process is now for example, when it is reading now let me give one say for example, when it is reading B for example, if you want to do it as m 3 now you have a choice here when m 1 is halting if it is reading A it will simulate m 2 and whenever m 2 is halting this will halt or whenever m 1 is halting if it is reading B then it will simulate m 3 on the rest of the input what are the current input available on the tape and then whenever m 3 is halting then in which case this will halt. So, this is what is the phenomena here the composition when I am writing this is how it is the arrow is a condition here. Now, for instance if sigma is equal to say A B blank then when I am combining say m 1 this is the initial machine let me call and for A I have defined say for example, m 2 and for B also I have defined this is m 2 and for blank also if this is the situation that means for all symbols of sigma if I am doing this I may simply write m 1 is the starting machine then without any condition here on the arrow I do not write anything I will simply write like this. This also I will write this as just simply m 1 m 2 let me follow this convention. So, for that means essentially here I wrote sigma is A B blank. So, in general for all symbols sigma in sigma if I have the situation these two machines are connected for all symbols of sigma then this is what is m 1 m 2 this is for all sigma in sigma in this situation we are writing m 1 m 2 we do not put that arrow in between unconditionally whenever it is halting m 1 it will simply connect to m 2 it will simulate on it because for all input this is doing therefore, this is the situation. Now, let me give one more notation also here which we may very frequently use that is for example, I have the situation like this I have A B blank and I am connecting m 1 to m 2 for A and B. So, that means for non blank symbols of sigma if I have this situation then I may also write this is because here only two symbols writing two symbols is not a problem if I have ten symbols here writing A 1 comma A 2 comma and so on A 10 and other than the blank essentially this I may abbreviate or use the notation that which are not blank here m 2 this is how we will write this bar if I am giving other than blank for all symbols of sigma this is connected to m 2. That means for fixed A in sigma if other than sigma if this is connected. So, this m 1 A bar m 2 I mean this is m 1 connected to m 2 for all symbols of sigma minus that particular symbol A except A for all other symbols this will be connected to m 2 that is the notation. So, I will use these notations very frequently when I am composing some smaller Turing machines. So, let me just look at some examples you know the Turing machine L if I connect this unconditionally to for example, L then what it does this Turing machine from the current reading cell it will take one left move it will halt that is the first machine, but unconditionally whatever it is reading again since it is connected to the Turing machine L what will happen it will take another left move and then as L is halting after one left move. So, this is a Turing machine. So, that means the Turing machine if I write L L is a Turing machine that takes two left moves from the current cell current cell and halt. So, that is what it does and for example, if you take this machine this the effect of this Turing machine is null because from the current cell it will take one left move and since unconditionally it is connected to R it will take one right move and it will halt. That means from the current cell it will take one left move and one take one right move and halt, but actually here is a problem when I am saying left move if it is say even in the first case or in the second case here the situation is if it is already at the left boundary for example, if it is already at the left boundary then the left move will make the machine hangs. So, the effective Turing machine will hang. So, if you have an assumption that at least one cell is available left to the current cell then of course, this machine the effect is nothing and in this case if you have first case if you have two cells available to move to left then it will take two left moves from the correct cell and halts otherwise it hangs of course, if the two cells are not available in the first case that hangs. So, that is what is here if you write this machine. So, I will let me fix A for A in sigma some fixed A. So, I print A and take a right move. So, that may be written like this because from the current cell in the current cell it will print A and it will take a right move and halts. So, I hope the things are clear this is unconditionally I gave here, but if I give some thing here for example, if I give B here where B is different from A when B is different from A then what will happen here this will simply print in the current cell A and halts. The reason why because B when B is different from A you know in the current cell it is printing and simply halting and this condition will not be satisfied and it will not take the right move and thus the effect of this Turing machine is simply printing A in the current cell and halts. So, it is nothing else, but just P A if B is different from A this machine is nothing else, but you know the effect of this is P A because B is different from A in the current cell you have A. So, it is not going to take it is not going to connect to this Turing machine. Now, let us look at this if I give this with symbol A for A in sigma of course. The effect of this Turing machine is in the current cell say first very first it will take one left move on the tape say let me say A 1, A 2 and so on A k is the input given to you and assume this is where the input suppose if I am like this. Now, it will take one left move here it will see if it is A it will take one more left move and as a A k minus 1 if it is also A then it will take one more left move and so on. So, if the input is sequence of just A's then it will come till the end and it will come to here and since it is not A it will simply halt here see this composition with a condition is very important to understand. Once again this is take a left move you come here and now if the current available symbol in this cell if it is A then it will take it is connected to the same machine that is L. So, it will take another left move so it will come here. So, when this is A this takes one more left move and suppose here the A k minus 1 that the A k minus 1 the symbol if it is not A then at that point it will halt. So, when I am giving the input like this whenever you are encountering non A that means a symbol which is not equal to A on the tape then the machine halts otherwise as long as you are getting A's it will keep moving to the left that is how it is. For example, if I give the machine this with A bar this is on the negation of that that means on the tape on the tape if it is getting other symbols than A it will move to the left keep moving and whenever it encounters A whenever it encounters A then it will halt. So, that means this Turing machine now we have constructed earlier. So, this actually accepts those strings x for example, let me consider here A B star as a fixed for example where A is a substring of x. Now, you look at here I have fixed the alphabet to be A B star. So, here the symbols in the Turing machine that I am going to construct you may consider A B blank like that. Now, with this notation I need not say that it is over the alphabet A B you can have some another 10 symbols or 100 symbols or whatever. So, I can simply say in this situation this Turing machine if I write with this notation the advantage is I can simply say x belongs to say some sigma star such that A is a substring of x. So, those strings which are having A that you are collecting in this language. So, that is how we can represent this. Now, similarly you can think of you know the connecting the right the Turing machine which makes one right move to itself conditionally unconditionally or whatever. Let me give a short notation for this Turing machine which we will often use here for a fixed symbol let me write that to be A in sigma. If I consider the Turing machine A bar that means L is connected to itself I may write this Turing machine by the symbol L A suffix A. That means this searches for A from the current cell to its left whether there is an A whenever A comes that holds. So, this Turing machine is searches for the occurrence A to the current cell. So, if it is available it will hold there if it is not available of course, when it is going to left it will hang. Similarly, for a fixed A in sigma I will write R A to denote the Turing machine which takes right move as long as it is encountering some other symbol than A. So, this is keep going to write when till it receives this. So, in particular if I say L hash is a Turing machine on the input if you give like this suppose some input you are giving normally we do not give blank in the input. If this is the input tape this machine this performs this L hash performs. So, here it will hold of course, these are all blanks and afterwards need less to mention. So, that is how the situation L A I mean L hash similarly, whatever is the symbol you write and with the suffix is what is its performing. Now, using for example, these Turing machines let me discuss a Turing machine that constructing for example, A power n B power n such that n greater than equal to 0 for which you remember that I have considered I think about 7 8 states to draw the to write the Turing machine the transition map of the Turing machine. Now, let us follow the same logic and see like how we combine the Turing machines x is the input given to you and this is how we are starting or you can write A 1 A 2 A n this is the current cell. Now, we take a left move and see whether this symbol is A or B. So, based on that we take a decision. So, we have to encounter B to cross check whether there is A. So, take a left move now you have two possibilities if you are encountering A then what to do that we will see that we should not we do not want to halt the machine in which case I may take left move keep taking left move unconditionally it will go and hang. Now, for example, if I get B then we are printing their blank. So, this is what the machine that prints blank and then go till the end of this that is L as for our convention and then take one right move. So, take one right move and then see whether you are getting A there. If you are getting A you are happy you print blank there then take R as that means it will come till this position because here you may this is blank. So, let me make R hash. So, from R hash again you pursue the same job that means connect back to this if in the beginning I mean the beginning or after few iterations if you are getting blank then you are happy you may just halt. So, halting means you whatever you perform even if I do not define here. So, anyway let me say print blank now the situation is when I am not getting A here when I take right move that means it can be blank or B these are the possibilities I can write A bar. So, in which case again if I put this loop that it will keep going to left and hangs and you see now how elegant is this picture. So, now you can quickly understand that how the Turing machine is working. Now, these are the Turing machines that in which we have used the Turing machine L L hash P hash R. So, these are the Turing machines that we have used the basic Turing machines and what are the Turing machines and there after we have constructed and we have constructed this Turing machine. Now, this is the starting Turing machine indicated by you know this arrow this is where you have to start and now give the input in the prescribed format and pursue the job. Now, you see that this Turing machine precisely accepts the language A power and B power n such that n greater than or equal to 0. So, instead of you know giving the transition map very that with huge number of states by following this composition or the composition this kind of notation I have followed to construct such an elegant representation of the Turing machine which accepts A power and B power n. Now, let me give one more some useful Turing machine that is right shift Turing machine or left shift Turing machine let me discuss. So, left shift Turing machine let me write this as SL maybe. What is the job of this? You give an input of the form X with this and what it does it transforms SL transforms this on this form. That means, the entire input whatever that you are giving it will shift one cell left for example, here say A B A if this is the input given to you and suppose this is available on the tape for example, like this or whatever it is. So, this after finitely many steps you will see of course the initial state whatever you call this A B A is shifted like this and finally, it will halt again here. So, when I am talking about this Turing machines I am not the prescribed input is for the entire Turing machine, but a particular Turing machine when I am talking about if the respective places are available then it performs the desired operation otherwise depending on the input given to us it may hang or it may not pursue and all those things, but for the entire Turing machine for a particular task if you are constructing Turing machine the input format and output format they are fixed. Now, you see for example, instead of this SL when you are performing here I said I am starting with this with a blank here or whatever. Now, here if there are two blanks for example, in the beginning then the in the rest it will be you know one blank will be available because the entire input is moved one cell to its left where it is blank. So, that is how we are we have to consider here. So, to indicate now you can ask me the question that for example, here if there is no blank that is not the hypothesis for this Turing machine because there has to be a blank that indicates that the input you know what are the string to be shifted there is one cell available. So, now to perform this task let me construct a Turing machine and see the input assume you are here and say a 1 a 2 a n is given here is a blank. What do you do you just go till this end and you keep shifting one one symbol to its left this is how you can do and to get the desired output a 1 will be shifted first here then in a 1 position you can move it like this a 2 can be moved and in a 2 position you can move a 3 in a 3 position you can move a 4 and so on that is the process here I pursue this is a lash I will come first to this position and then take a right move. Now, whatever that I am reading if it is not equal to blank this is the notation very important you have to follow here. So, if I if what are the input that sigma I am reading if it is not blank then I take a left move and then at that place I print this particular sigma. So, the notation here is what are the input I am reading that symbol to be printed here error. So, that I am taking in the variable sigma the sigma which is not equal to blank the same sigma will be printed here and then take a right move and now further one more right move you have to take to continue in the loop. So, when you are receiving blank that means you have reached to the end of the input then what do you do come one cell to its left and there you print blank and halt. This is how we can pursue you see once again what we are doing and the input let me just take an example say a b a blank I am here of course let me use this symbol because here you require finitely many operations. So, this L hash in the beginning that takes the cursor to the first blank symbol to its left that means it will come to this place and of course normally it holds L hash, but it has connected to R it has connected to R unconditionally. So, from here by taking this step it will come to this position a b a this is the situation R means. Now the current reading symbol is not blank that is a in fact. So, it will take one left move so that means now with this L this condition has been cross checked and it is carrying the input in the variable sigma it takes one left move that means it will come to this position a b a now this is the situation. Now there in the current position it will print what are the sigma that it is carrying it is carrying a. So, it will print a so now a comes here so a b a this is the situation now it takes one right move with this machine. So, that is now a a b a so one right move now in this loop again I have connected back to this R. So, that means it take one more right move so it goes to this place a a b a this is the place with this R now this is not blank again so it will take one left move there it prints the current reading symbol that is carrying in sigma that is b. So, now it will be a b b a it prints and takes one right move and further one more right move so that comes here. So, a b b a and again this is not equal to blank this is not a blank symbol. So, it will take a left move a b again there a it prints a this is a so it takes one right move and further one more right move that means at the situation what it does a b a a it comes to this place blank now the current reading symbol is blank. So, what it has to do it will take one left move there it prints blank and simply halt. So, that means this is a b a so this is how the input a b a has been shifted one cell from the current position to its left the entire input x has been shifted one cell to it that is that is what is the machine SL is doing. Now, similarly one can think of right shifting machine how what is the process of this given input it will leave the input in this format one cell from the current cell. So, it has to shift this x one cell to its right so that the format will be this. This now take it as an exercise to construct this Turing machine SR right shifting machine construct right shifting Turing machine SR this is the notation let me use. Now, let me go back and see when we have constructed Turing machines for a power n b power n the notation what we have used here some of the important points let us look at here. So, it takes one left move and when a b are blank these are the three possibilities we have enumerated here. If the input alphabet has some other symbol if a input alphabet has some other symbol here when the first left we have defined for a b and blank for all the three symbols whatever in this particular context we are writing we have written. If the input has some other symbol then the machine halts and the input will be accepted. So, in this case we have to restrict because we have to specify that the input alphabet has to be a b sigma for which only this will work to accept a power n b power n. Otherwise as I had mentioned in the beginning if any other symbol is encountered when it takes left move it will halt and the input will be accepted as per our definition. Now, this is one important point and you see here we have defined for a and here it is unconditional. So, at every connection you see for every symbol the things are defined here and here it is assumed that sigma to be a b blank this is the important high process. Now, when I am coming to this Turing machine here some other conventions are being adopted that is we are carrying the input because what are the symbol that you are reading that is shown on the arrow and you see here for every symbol first arrow is given for every symbol this is for non blank symbol second arrow the third arrow nothing is written that means for every symbol and this arrow is for every symbol this arrow is for every symbol this is given for non blank and this is for blank symbol. So, you see on an arrow everything for every symbol the current reading symbol whatever it is it will work. So, thus you see this machine is independent of the sigma whatever that it is under consideration only thing is some alphabet is fixed and on that alphabet this performs a job you see this is the basic difference between these two constructions there we have to indicate that sigma has to be this accordingly it performs to accept a power and b power n. Now, assume in the previous case if sigma is a b c there are three letters and now the you have the choice of you are giving input with some c is available. Now, in which case what will happen it will accept a power and b power n this the strings if you give a power and b power n anyway it will accept, but if the if it encounters c on the tape and the input then since there is no definition then it will simply halt that is the problem. So, it will accept few more strings now you understand what are those strings that it can accept if you make it is if you make it independent of the fixed alphabet. That means here when you are combining Turing machines as I had mentioned you have a choice like to what you want to connect under what conditions you wanted to connect the condition will be specified on that arrow. As such you know you see we have started with when we are defining Turing machine we have a formal definition for this Turing machine we have given it as a quadruple there is state set like for the other automata we have state set alphabet and a transition map and where you have to start. Now, when I started discussing about this diagrams and all that now the question is whether is it using that generality that means any Turing machine as we have defined that this Turing machine the way that I am now introducing this kind of notation whether they are actually as per the definition or not that you may have a doubt. I will address that yes this will actually follow the definition what we have defined that means corresponding to this as such we can give the corresponding state set and as I had mentioned that this will give this gives the advantage of you know not representing the states explicitly rather it will capture the entire idea of the basic definition of Turing machine through state transitions. Now let me give the formal definition how to combine this Turing machine then you will realize this yes exactly these diagrams are corresponding to the original definition. So, now for which let me first introduce the notion because when you are combining Turing machines you require certain Turing machines to be combined that let me call it as machine schema that is a machine schema. The machine schema is a quadruple what do you give here let me write by S a set of a finite set of Turing machines let me call it as m and or same alphabet let me say that is sigma and a partial map eta from where to where let me mention later this is m not the initial Turing machine where m is a finite set of Turing machines is a finite set of Turing machines over the same alphabet over the common alphabet sigma and m not is a specified machine in m this is the starting machine that we will. So, to combine Turing machines we have to give this machine schema and eta this is a partial map that is from given a machine and a symbol which machine to be connected when it is halting a particular machine is a partial map. So, why this is partial map you have a choice that when a machine is halting when I am halting by reading a particular symbol at that particular symbol if you have a definition as I had mentioned you will continue to connect to the next machine and it will continue the process if there is no definition of a particular symbol then the machine simply halts the composite machine simply halts. So, this machine schema is given as a quadruple here this is a partial map given a machine and a symbol given a machine and a symbol what is the next machine if required. So, that is to be given to this partial map this is machine schema and each mission each such mission schema represents because depending on that eta what is the combination will be declared and based on that we will see that what is the simulation of that representing Turing machine. So, here let me give that definition also a machine schema let this S is m sigma as I am writing eta m naught be a machine schema. So, you are given a machine schema now yes this machine schema represents a Turing machine. So, here let me specify machine schema with this m because this is a finite set let me call them as m naught m 1 and so on say m n there are n number of Turing machines or common alphabet where each m i let me fix that to be with the state set q i as there is a common alphabet sigma that is what is here and for this m i let me take delta i to be the transition map and the initial state of that Turing machine let me call it as q i. So, for 0 less than equal to i less than equal to n as for all these Turing machines let me take this way now this S the machine schema as represents a Turing machine a Turing machine let me write that to be m with state set say q of course, the same alphabet sigma with the transition map delta and the initial state will be the initial state of the initial machine that will that is q naught here is q naught and where what is q q is essentially all this state set. So, here very important thing is we have to see that in the machine schema these are pair wise disjoint sets of states. So, that is very important here in the machine schema let me put that condition here here these state sets the common alphabet and pair wise disjoint states as a finite m is a finite set of Turing machines or common alphabet with pair wise disjoint state sets. So, this is important that means here if you take q i intersection q j this is empty for i different from j this is the condition you have. So, there is a disjoint union essentially here. So, these are all disjoint sets and to combine this let me pick up some new states say there are new states which are not there in any of this capital Q i. So, these are new states with the condition that the p i is not in union q i i equal to 0 to n. So, this is the that is how you have to choose this state set. So, essentially when I am talking about the Turing machine that is represented by the machine schema this has to capture whatever so far we have constructed because the original Turing machines will be lying there in the in that circuit what are the circuit that we are drawing the diagram that we are drawing. So, those states will also be will be there and this new states p naught p 1 p n one for each Turing machine that I consider for what purpose whenever a Turing machine is halting particularly for example, if M i is halting as we know that we should not the we should not make the machine the composite machine halt. We have to crossing the condition under the current symbol if there is a definition to connect to some other Turing machine we have to connect it to that. So, if it halts then the machine halts the entire machine will halter. So, what we have to do a component machine a particular machine whenever it is halting as per its definition delta i here whenever it is coming to the halting state h we change the transition to you know by keeping to an auxiliary state for each M i I take one p i a new state instead of putting it in the halting state I put first in the state p i for that purpose we consider this for each machine one auxiliary state p i. So, that is how this states are considered this states are considered now you put it there and you cross check eta whether eta has a definition for that particular symbol at that particular moment. If there is a definition that means what is the next machine will be known from eta if there is a definition then you connect it to the particular Turing machine and start simulating the rest on that machine otherwise then you can halt the machine. So, that is how essentially the delta works where now let me give that also. So, this is a state set and now delta is defined as follows because in this four components in this four components M the q is mentioned sigma is the common alphabet and delta I have to define q naught is the initial state of the initial machine that is where the process will start now delta is defined as follows now delta is defined as follows. Now, this for this condition if the current state q is in the component q i what are the symbol it is reading if this and the definition of delta I at the symbol q a is p b whatever it is then this delta at the state q a it will consider p b provided p is not halting state. If p is halting state it will not halt rather it will put it in the state corresponding to this machine that p i and whatever it is performing the same thing it will perform p i b if p is halting state that is how this performs and now for states which are not in any of this q i we have to define because here we have defined the first statement is for any state which is in q i and now there are only two possibilities if you pick up any state whether it will be in the union of any of the states or any of this p i's now the situation is if the state is from p i then that means for just a in sigma now I have to give the definition for this p i's only that is p i at a is defined to be this halting a whatever is that a if eta of m i at a is undefined if this is not defined if there is no next state from this state at this symbol then the machine should halter otherwise whatever the next machine if it is defined so and so if I say q j what are the next machine it is doing so you can do this you can connect it to this the first state initial state of the next machine is q j if it is m j so if eta of m i at this symbol is m j look at this transition whether it has captured carefully there are two possibilities for a state and for each symbol sigma that I have to define because the transition map has to be defined for each state and the symbol. So, here the states either it is any of this machines or the new states that I have introduced to p naught to p n now the definition here is if you if the state whatever that I have consider if I have to define delta of q a if this thing has to be defined you just look at if this q is in any of this q i's then you simply define as in that particular machine in that particular machine if delta of q delta of q a is p b then you follow the same provided if that resultant state is not a halting state that is what is the condition here if the resultant state is a halting state as I had mentioned you do not make it halt rather you put it in that auxiliary state p i corresponding to this m i the machine because when the q is in q i that means I am simulating the machine m i in which case you put corresponding corresponding halting state that is what is p i. So, this is the condition here if it is halting state put it in p i now the definition for when I have somehow come to the any of this p i's now for each symbol a in sigma how I have to define it now you just look at because if I am in p i that means this auxiliary state corresponding to the state m i. So, you just see m i at that particular symbol whether this definition is given that eta is defined or not if it is defined then we have to act one way if it is not defined we have to act another way what is that if it is undefined then you simply halt that means halt on the same in the same position that means since I am reading a I will of course, do I have to do something. So, I will print the same symbol that is how the definition is given that is h a if there is a definition eta has a definition for this space assume it is also to connect to m j then in which case what you have to do with this current symbol whatever the machine m j does in the initial state initial state of m j is q j. So, delta of q j a that is how it is defined. So, this is how the total map delta is defined for the Turing machine m and the machine schema given a machine schema that means a finite set of states and declared as with some initial machine or common alphabet with a disjoint set of states if when eta is given that eta tells you that how the machines are to be combined and as per this you this to this machine schema that represents a Turing machine as defined here. So, this is the total definition of that now what you can do you just take you know some machine schema or some combination and you can what are the component Turing machines the respective states you can write and see. Now, the question is if you are having you know some Turing machines where you have to use them twice or twice for example, if you consider the Turing machine l l now if I if you consider say for example, this you have considered the state q naught because you know the Turing machine will have only one state. Here also if I consider q naught then that creates a problem that you have to realize. So, realize the problem if you consider same q naught here what is the problem as per the desired thing. So, if I consider here also q naught the state set and in this component also q naught as I had mentioned when I am taking two machines you have to have disjoint set of states. So, by considering same state set what type of problem that you will encounter we encounter. So, that you just look at and we will discuss these things in the next lecture and now for some you can write the machine schema and what is the machine schema for that and appropriate combination. For example, so first understand that and accordingly whatever the machines that we have already constructed one is for a power n b power n such that n greater than equal to 0 we have constructed a Turing machine for which you write the machine schema. So, this information will be useful to you this is useful information for this purpose. So, x i is 1 is this and write machine schema for whatever the left shifting machine we have constructed write machine schema because we have constructed composition of Turing machines. So, now first you realize what type of problem that you encounter if you take the same state set. So, what is the difference why we have to consider different this thing. So, that how you have to represent those things that you should discuss in this particular problem that will be useful to answer the these two what are the machines composite machines we have constructed write the machine schema for that and we will discuss the rest in the next lecture.


favorite topics, sexuality. But the thing is when it comes to female desire, it's a taboo. People don't like to talk about it. Or when we talk about it, people think of it as something that's like salacious, something that's indecent, something that's inappropriate. And so we need to reclaim this idea of desire from the woman's perspective, and specifically in Hong Kong, because we talk about many places. Actually, it's a global issue of how we've been controlled, our bodies have been controlled and continuing to be controlled in different ways. But so let's talk about this whole idea of the rights to our female desire. And I have here wonderful Vera Luy from Hong Kong. And Vera has a toy store, toy store, has a sex toy business in Hong Kong. And Vera has a very engaging way of speaking about sexuality with the Hong Kong audience, which I think is a very important approach. So Vera, welcome to Quok Talk. Thank you for having me.  So I was born and raised in Hong Kong. I moved to the state when I was 16, but then I came back because I met my husband. I came back when I was like 23. So I actually started the business when I was 23, after I came back to Hong Kong and, and all because I, I was also growing up in Hong Kong without any kind of sex education. Basically, all we did in school was giving us like master packs. And that's it. No one never talks about the topic. My mom never talks about it. And I still remember when I had my first period. She just gave me the pad, show me how to use it. And that's it.   And then it was, it was like, you know, the daytime use pad. And then she also tells me, Oh, at night, you use the nighttime one. But that's it. Like, there's no conversation about feelings or emotions that I'm going through during my puberty and, and having this like menstruation coming into my life. Like, we don't really talk deep about it. And that's normal. Just for people to know that's normal. Probably not just Chinese society, but many cultures. You don't talk about it. You don't put it on the table. We don't talk about it enough. Yeah. Yeah. And also when I, then I got to the States and I will basically my sexuality started, like my, I was sexually active since I was 17 years old. But then, oh, my kids is in the back. That's good. It's all, see? Wait, you know what? Wait, wait, wait, wait. So I have to interrupt you for there. Because every time when, when my kids were going up and they were asked or saying something, they think it's inappropriate or silly about sex, my husband would just shut it down and say, hey, if we didn't have sex, you wouldn't be here today. Ah. Right. And then I, like, yeah. Exactly. Why do we say think of it as a shameful thing? It's a process. It's a, it's a human process. Yeah. Okay. So I, yeah, I, so I didn't know anything. I was sexually active since I was 17, but still, like, it was all learning from child and era. So it wasn't until I got back to Hong Kong, I met my now husband and boyfriend and he gave me, gave me my very first sex toy that I started exploring my own body. That's interesting. Yeah. So the first time I got it, I was really confused of where to use it because I've never really touched myself. Okay.   Okay. So I got it, I didn't know how to use it. I got it at home and it was like, I was still living with my parents and I was so afraid that they would find out. He, like, making all this noise in the next door room. Yeah. So I hit it until, like, it was like 2am in the morning and they all fell asleep and then I finally took it out. I opened it and I was like, how do I use it? So I didn't know how to do it. So I googled, like, how do you use the sex toy? So they googled and I learned so much.  I was like, I've never self-pleasure. And then what do you find out during self-pleasure? You may find your orgasm, you may find like your own kind of, like, your own kind of pleasure and where you find it, like stimulating, blah, blah, blah. And I was like, okay, like, I have to figure this out. So it was like, I spent an hour studying and until it was like 3 or 4am in the morning, I finally have my very first orgasm in my life. Wait, wait, wait. So you never had an orgasm before that or you didn't know how to do it? No. Yeah. Even though I was sexually active for five years, I still haven't, like, feel anything. Because we're not taught. We're not educated. Nobody guides us to search for that. And a lot of times our partners, and I don't know how to generalize that Asian partners tend to be less sensitive about this stuff, but they're also not educated to bring that attention to female pleasure, right? I remember, do you remember when I had my show a long time ago in Hong Kong, but I had on cable TV, I remember this one lady, our topic was women on top. That was the focus. And this one mother who's been married for over 10 years, she called in, she says, oh my gosh, because of that position, she was able to find her climax. But after being married for over 10 years, she's never had a climax before. And it was like, Hallelujah.  Yeah, nobody teaches us. The only way that we learn from it, maybe from porn, and there's a lot of false information on there. Exactly. Yeah, it just shows, it's more like an entertainment than the reality. Yeah. So that was it. That was my, that was the climax. This changed my perspective about sexuality. It changed the perspective about how I see my own body. So it really empowers me to be like, hey, my body belongs to me. And also it can give me lots of pleasure. And I can own that pleasure. I don't need to rely on anybody to give me pleasure. And I can learn about my body. And, and as I came on exploring, I find that it's really liberating. So I was like, okay, this is something that I should tell people. But I don't know how I don't know what the format will be. But I told my boyfriend, like now husband, I was like, okay. Wait, when you came on my radio show years ago, were you married already? I think so. I got married when I was 26. So probably. When you're launching, yeah, your business, right? Okay. Yeah. So that week, I was like, we need to tell somebody, like we need to tell people if I grew up in Hong Kong and I didn't know about this, I was just an ordinary Hong Kong girl. And probably lots of people don't know. But when you're exploring, don't you have girlfriends that would you ever talk about sex? Or, you know, like, never talk about this, right? Yeah, we never talked about it. We talk about all kinds of things like boys love relationship. But we really never talk about this. Why do you think that is? Why do you think that Hong Kong has been such a taboo against us talking about pleasure and owning up to it and searching for that? I think it mainly maybe it's because of the culture, like how in your own household, this is not a topic that has been raised out even when the topic comes up.  And it's just kind of discourage you.  So where does that come from? Why do you think we're slut shamed if we talk about sexuality or if we even think about women seeking pleasure? Why is that something that is considered inappropriate? I think, okay, this is my own personal theory, right? But I personally think that if you can control a woman's pleasure or control her sexuality, it makes her doubt herself. And it kind of makes her also become not as confident or as authentic as she is, or as powerful as a woman can be. Then she just, then she becomes like a secondary citizen in the society. And all the other people can be on top, you know. Yeah, that's part of my theory. No, that's good, because really it does come down to power and control and the fear of them giving up their power. Like what is the threat of a female in power to them? What is the threat of sexual power to a man? Is it they think that we're going to go out and screw other guys? Or is it because it makes them feel less because we have control over ourselves? I think maybe part of it is for some people, for some, especially in this kind of society, like they feel like the only way that they can have power or control is through controlling the other person's sexuality. Like instead of having power individually, they want to control others to gain power. That's how I would put it. And it's not just political. It's also personal. It's also like, for example, in a marriage, like the power that's in between those people also kind of showcase that. But you know, so I dated one Hong Kong guy while I was living here. And I remember he did not know how to pleasure me. I realized it wasn't even a thought. Like nobody educated him or he didn't care to be educated or to can think about the female pleasure. It's not his vocabulary. Right. And it wasn't intentional just to deprive me of it, right? But so do you think that's like the typical, can we assume that that's the general way that a lot of Hong Kong men, you know, embrace or approach sexual relationships? Or do you think it's changing? Or I think there are two sides.  Yeah, yeah, I know there's a lot of those people, right? But I've also seen a lot of men, they want to know how to pleasure their partner, and they want to give pleasure, and they want to be part of her her sexuality journey, like whatever she's exploring. Yeah, but they don't have the skills technically and also in terms of communication. They don't know how to communicate that. They don't know how to tell her, I want to be part of it. They cannot put the words out. So it becomes like, oh, I don't know if she wants me to, or if she expects me to, or if she wants me to be part of it. And then, and then also from the women's side, like, oh, I really want him to do this, but I don't know how to tell him. If I tell him or his ego, it all comes down to lack of communication or lack of ways to communicate. And that's like the essence of like the whole Chinese culture though, right? It's the lack of communication. Oh, yeah, yeah. You go to a dinner table, nobody talks.  It's just like that's the way the Chinese are. And sometimes culturally, we don't understand that it comes from like hundreds and hundreds of years of a certain kind of rude tradition in this distance. I don't show you your emotion. Yeah, yeah. I told you to your elders and also physical touch as well, right? My mom and my dad never kisses me or hugs me. Yeah, me too.  Good night. Okay. So we're also a culture that is very unfamiliar with showcasing physical or affection. Yeah, yeah. Most intimate relationship, these kind of things also play a part like, oh, I don't know how to show her that I love her. And even though if I want to hug her, I don't know if she wants to create like a gap between the two person. So do you think we need to educate men how to find pleasure from seeing pleasure from the woman? Like, is that part of the thinking that we need to change? Or, you know, how does how do we open up dialogue? I think for, I'm also certified sex educators. So when we talk about sex education in this context, we always talk about how like, there's a few things that people need to learn when it comes to sex education or sexuality. First, it's basically, you know, the anatomy, right? Like, you need to know the body parts. Yeah. And second, of course, sexual health, how to do it safely and helpfully. But also, another part that is always gotten neglected is communication and also how to be in a relationship. Like, these kinds of things are always forgotten when it comes to talking about sexuality. So I don't, I wouldn't say it's only men who needs to change their perspective. I think it's all genders need to be educated in this way. When it comes to sexuality, it has to be consensual. And what we mean by consense is you have to have communication before you do anything or also communication along the way. So it might be like, we may also have a man who has never explored his own body, right? Maybe he grew up in a very traditional or a household or a very religious household. He has never touched himself. And then he, this woman, and they want to explore things together and he doesn't know how to. So it can also be like, in that, that it can also be one of the scenarios. So I would say like, both or all genders have to learn about how to communicate. Also learn about your own body before you engage in a, oh, you cannot expect your partner to know your body if you don't know yourself. So explore your body, learn the knowledge, then communicate this to your partner, and then they will know how to do what to do, show them, and then, you know, have fun together. It doesn't have to be that serious. Yeah.  Like you shouldn't be doing that, shouldn't be masturbating. It's not, it's not healthy, but actually it is healthy, right? So can we talk about a little bit about that? Well, I also met a lot of people, you know, in Hong Kong, there's lots of Christian and Catholic schools growing up. So this part of, this kind of religious narrative also plays a part in our sexuality as well. But I would say like, in terms of when it comes to sexology, masturbation is actually a super healthy thing in, if you do it in a, in a way that is not like overdoing it, right? Like, in terms of like, I guess everything in life, if you overdo it, it becomes something bad. Anything, yes. But yeah, so in a moderate sense, and in a sense that you are exploring your body, having a connection with your own body. And I don't, and I always say like, if, if pleasure is not something that is, that our body can provide, then how come there's this the mechanism inside our body that can do that, right? And why is it that the female anatomy has a higher sensitivity to climax than a man? And, and then back to historically why certain cultures want to deprive us of it, because they're afraid of this power, you know. Yeah. And, or maybe they feel like this is losing control, I don't know. Right, right, right. Nobody wants a woman out of control, right? Because they don't know what to do with us. So I, I still respect that people have their own religion. But also, I don't think learning about sexuality or learning about what your body likes or not like is going against their scripture, because I have seen so many people coming into their first, I think their first intimate time with their partner. It's usually like maybe they got married, and then they have their first sex.  That's why they don't know how to have sex. They've never seen another person's body. They don't know the anatomy, and they don't know their own anatomy. And they're just like the blindly supply.  So you don't see the anatomy. You don't know what your partner's body looks like. I had, I had, I've had, I met a couple, they're also, they're also like very religious. And they came to our store because it was like crying out for help. Okay, they could like, I'm married for like six months and they still couldn't successfully having their first in the course. So they came to us. And then I was like, so what's going on, you know? And then I asked them questions, I guess, like, and then of course, they didn't know about the anatomy. And I said, so how do you do this? Do you do this in the dark?  And they were like, oh, I owe it. And then there's a, I thought, having, having sex, you need to turn the lights off to have sex. I was like, why, why do you think that? And then they were like, but it's, it's how it is in movie. In movie, it's always like turning the lights off. In the bed, because they have never worn any pornography. So in the bed, well, that's probably better. Blanket on, lights off. Under the blanket. Oh my gosh, yeah. Of course they know they have to put some, put something inside another thing. But they didn't know how. And it becomes mechanical, right? Like they don't know the, the pleasure aspect is not in the equation. It's just about, it's scientific, it's medical, it's for the kids to produce children maybe, right? Basically, they want to mate and they don't know how to mate. Yes. The pleasure, like you say, we were gifted with these parts of our bodies to, to receive and enjoy and to explore pleasure. So how do we, you know, but I think another issue is Hong Kong's lack of space. We don't have privacy. Yeah, yeah. So it's kind of pushed us into a way to silence ourselves. We don't express. I mean, of course, culturally, we already don't express. But then if you have somebody in the next door, you're not going to allow yourself to scream out in your orgasm or whatever, right? So it's not. When I was bringing up, I was also like, oh my God, what will my neighbor hear me? You know, because the building in Hong Kong is so close. My neighbor's bathroom is just like, the window is just like, maybe. So technically, they could hear you if you were like doing it in the bathroom thing. And I think the way, I was like, oh, did they hear me? Yeah, so the lack of space, I think the lack of space is actually a very good term to summarize sexuality or pleasure in Hong Kong. The lack of space physically to do this, the lack of space to talk about this, to have conversation about this, and the lack of space to imagine and to create about this. So it really sums up, the lack of space, it really sums up how it is. Yeah, but it gives good context to understanding both cultural and social issues around pleasure in Hong Kong though, right? Because if in the West, we don't have those issues, we just say, oh, yeah, you know, why are so Asian so uptight about this? Why can't we talk about it? But they have to understand that there are these kind of historical and cultural reasons for the way we. Oh, have you seen the Netflix show called How to Build a Sex Room? No, is that a new one? Also, so, so they, they have a show. Okay. Showcase in America or in Canada? I don't know. What's a sex room? What do you mean by sex room? They basically, you know, a lot of people have like in the in the West, they have like a like a like a basement that they can't they don't use or they have an extra room that they don't use. So the the the whole of the show, then it's kind of like interior design, but making it like you're okay, okay, okay. And you can have your sexy moment in it. Is it kind of like equivalent to those motels in Kowloon Tong where people go for those those love motels? Like you just have a room that yeah, but but she styled it based on the couple's fantasy, you know, they have different fantasy or there's different things that they like or like to explore. So the room is really customized to that. So I was like, I was watching that show. I was like, oh, well, I really wish we could build a sex room.   What you can in Hong Kong, you got to adapt. And that's why Hong Kong people adapt so well, right? We the ability is very high.  There's like actually a lot of Airbnb's I've noticed people like young couples go there just for, you know, a little time and you have to find your space because what are you going to do? Let social society kind of close you off and deprive you of your pleasure, right? They just give the audience some more content. We have couples who like especially the younger generation, like maybe the 20s or 30 years old, they got married and they, they were, even after they got married, they were both still living with their parents separately. And they will only meet each other during the weekend. Yeah, like, you know, it's really hard to, it's very expensive to buy your own space in Hong Kong. And maybe they can, and also, you know, a 20 something or even 30 years old, they may not have enough money to afford the high rent. Yeah. Some people were still living separately after they got married. Wow. But so to the other extreme is like when you're all cramped into one household, right? And you have kids like yourself, have you ever had experiences with your kids running, coming into your room when you're doing it? I mean, well, I, whenever we do this, we do it when they are not here. Also, because, you know, how it's part of how desire works. So a desire works when you have the right context. Right. So everyone's context is different. Some people is environmental. Some people is mental. Some people is also psychological, emotional, things like that. But for us, especially for me and my husband, when we are in a space that the kids is around, we don't, it's not a safe space for us to explore. And both of us cannot go into the mood. Because then you always have this anxiety of maybe somebody disrupting your pleasure, right? Or even like, because we put their needs first. Yeah. Prioritize their needs. Okay. So when someone is outside crying out for mommy, we're like, oh, well, maybe she was just whining, but then we were like, oh, my God, did she hurt herself? Is she hungry? Does she need water?  And all of a sudden your kid comes in and says, no, we don't. So yeah, I mean, there's so many issues that we have that we don't, I think that is specific to Hong Kong. I love your metaphor of the space. I love that you have, it's a context to the mind space and the body space and their surrounding. So if you had to leave people with like maybe one takeaway of how to take back female pleasure on both sides on whatever couple, whatever relationship you have, what would it be? Well, start exploring because you'll never know until you start exploring what you like.  And one last thing is I know a lot of people when they start exploring pleasure, they're like, I don't know if I am doing it the right way or if it is really truly pleasure or climax. So I would say whatever you feel is good is good. But don't doubt it. If you find this pleasure, then that's your own pleasure. Listen to your body, right? It tells you. Yeah, it tells you and you trust your God. If you feel right, if it feels right, then it is right. You don't have to be like, oh, the other person is doing like this. And am I doing it the same? Don't think about that. So final final, now we're out of time. How do people look for you if they wanted any? Oh, if you come on our Instagram or Facebook, it's sallystoy, s-a-l-l-i-s-t-o-i. And also have a YouTube channel. It's the same name.  And on our Instagram as well, we have tons of funny reels that you can walk through. Yeah, I caught one about you talking about the shower head of my massage. I love that. So we're out of time and no one is going to cut off any moment. But I really, there's so much we can talk about with so much pleasure in talking about pleasure. I want to thank you so much. This is Vera Loy from Sally, Sally's Toys, Sally Coco. And keep it, keep all the wonderful, important stuff you're doing. And I want to end it to your husband next time on his next story. That's a great story. Thank you so much.