We saw Monday now to design a Turing Machine that emulates a Turing Machine with a two-track tape: the tape has an upper character and a lower character. We emulated that by just using a regular turing machine with an expanded alphabet. Each letter of the TM alphabet is an ordered pair (a,b) with a being a character of the upper alphabet and b being a character of the lower alphabet, so that we are essentially now writing two characters in each square of our regular Turing Machine, making it work just like a two-track Turing Machine. Now, here's a more interesting problem. Suppose we have a two-tape TM, not just a two-track Turing Machine. This Turing Machine has two heads. Each head can move left or right independently of the other. How would you design a regular TM to emulate that one? If it makes it easier, you could envision your TM to have multiple tracks or a finite control or both. But how do you get it emulate two moving heads? Let's do something a little more basic first. Let's suppose we have an input string delimited by . Call it S. How can we copy it? How can we make the input tape become SS? Start at the first character. Store it in the finite control. Put a space where that character used to be. Move right to one past the space. Put the finite control character into that location. Write a space to the right of it. Move left to the second space you see. Write the finite control character into that space and then move right. Do this until you get to the space between copies. DOG_ _OG_D DOG_D D_G_DO DOG_DO DO__DOG DOG_DOG_ BATMAN_BA How would you design a Turing Machine that given this input string S# Where S is a string and # is a base-ten number. results in S#c where S and # are unchanged and c is the #th. character of string S. Googol, googolplex, mega, and the megiston. Googol is 10^100. Googolplex is 10^googol. Triangle n is defined as n^n. Triangle 1 is 1. Triangle 2 is 4. Triangle 3 is 27. Triangle 4 is 256 and so on. Square n is defined as n inside n triangles. Square 1 is triangle 1 = 1. Square 2 is triangle triangle 2 = triangle 4 = 256. Circle n is defined as n inside n squares. Circle 1 is square 1 = triangle 1= 1. Circle 2 = square square 2 = square 256 = triangle triangle triangle triangle...256 triangles 256= <255 triangles> 256^256 = mega Megiston is circle 10. SIMPSON_4_4 _IMPSON_4_3 S_MPSON_4_2 SI_PSON_4_1 SIM_SON_4_P SIMPSON_4_P So far, we can increment or decrement numbers. We can store things in finite control. We can shift right and shift left. We can copy stuff. Now how can we emulate a 2-tape turing machine? With two heads, each moving left and right independent of the other? tape 1 contentstape 2 contentshead 1 positionhead 2 position Finite control can contain the state you're presently emulating in the multitrack TM (there are a finite number of states so a state can be held in the finite control) You can find where the head 1 is pointing (and it's the same for head 2): Much like what did to find the nth character of a substring: we make a copy of the head 1 position (shifting stuff to the right as necessary to make room for it). Then we start decrementing the copy as we move forward in the tape 1 contents. When we decrement the copy to zero, the finite control should have that specific character. We then shift everything back. We do the same thing with the head 2 position so now we have in the finite control the character of tape 1 and the character of tape 2. We also have in our finite control the current state of the multi-tape TM we are emulating. Since we are emulating one specific multitape TM, we have that machine "hardcoded" in our own states. So, since we know the state we're emulating, and the two characters our heads are looking at, we now know the new state we're moving to. We replace the old state in the finite control with the new state. (And the new state might be halt). We may have to change one or both of the tape characters, and we may have to move one or both heads to the left or right. If we have to change a tape character, same deal. Make a copy of the position, decrement the copy down to zero while moving forward in that tape's contents. When you get to the correct character, change it. Moving a head is straightforward: Moving a head right is simply incrementing the position. Moving left is decrementing the position. If you move right past the end of the contents, you should increase the contents by one space, shifting everything else to the right. CAT_4 If you move beyond the left border, then add one space to the left of that tape, shifting everything to the right, but make sure the tape head is still at the beginning _CAT1 How would we design a TM so that given two strings ST the TM writes YES if S and T are equal, NO if S and T are not equal. STYES or STNO so S and T end up unmolested but with YES or NO written afterward. Store first character in S in finite control. Replace with space. Move forward to first character in T. Put that in finite control. Replace with space. See if they match. If they do, go back to beginning. Put first character of S back. Put next character of S in finite control and replace with space. Move to second space to the right, but first character of T back. Move to next character. put that in finite control and replace with space and so forth and so on. If you make it all the way through the string, the answer is yes. If you do not, the answer is no. We can now test for string equality. UNIVERSAL TURING MACHINE. Suppose our tape begins with a printed listed of states of some other TM. <...> <...> ... followed by a border character followed by the input string that TM. What your TM must do is append to the input the output that the printed TM would have given on that input. In other words, how can you design a TM that will emulate any TM on that tape with respect to a specific input also on that tape. For example, <...> <...> ... <...> 5 The above is a printed definition of a Turing Machine that squares it input. Then MY Turing Machine would have to end up with: <...> <...> ... <...> 5 25 Imagine the start state is always the first one listed. First we can copy the input so that we can emulate the other TM on that input, while leaving the original input pristine. Set the head position to be 1 and set the current state to be a copy of the first state id in the printed turing machine. Now we go through the printed turing machine one state at a time to see if the state id matches the state id we're supposed to be at (because we now have a way to compare strings) AND does the character our emulated head is pointed to (and stored in the finite control) match the character in this printed state. If it does, then this is the state we're interested in. Get the new character, store that in the finite control and replace that character in the emulated output tape. (Or move L or R if necessary by incrementing or decrementing the head position...just like we did in the multi-tape simulation.) Get the new state and copy that into the position on the tape. If it's halt, we're done. Otherwise, continue the emulation;