TM assembly: Design a TM to execute programs written in a simplified assembly-like language There are just four instructions: L, Mx, My, and A operating on three registers x, y, and z each holding a nonnegative integer L instructions load a certain constant number, represented in binary, into register z For example, the instruction L00000101 loads the integer 5 (represented by the bits 00000101) into z. Other bit strings can be specified. The number of bits may be arbitrary, but you may assume it is the same for all load instructions in the program. For instance, if the first instruction is L0011001100110011, then all remaining L instructions will be followed by exactly 16 bits Mx and My instructions move the value from z into x or y, respectively. (Actually, it's more like "copy" since the value in z is not erased, but "move" is the traditional assembly language name for this instruction.) A instructions add the values in registers x and y and store the result in register z. If the result overflows, the new most significant 1 is simply omitted; i.e., the result is taken mod 2k, where k is the number of bits specified in the first load instruction. For example, adding 11111111 (255) to 00000001 (1) results in 00000000 (0), and adding 11111010 (250) to 00001001 (9) results in 00000011 (3). (This might sound difficult, but actually the straightforward way to implement addition will automatically achieve this.) If an instruction needs to read a register (add must read x and y, and copy must read z), then you may assume that register has already had a value written to it The input will be a followed by a list of instructions, each followed by a :, such as 00000 1 1 0 :Mx : L00000 1 1 1 : My : A : Mx : L00001001: My :A: The above program does the following . load the value 6 into z and then move it into x . load the value 7 into z and then move it into y . add x and y and store the result (13) in z, move the value in z (13) into x, e load the value 9 into z and move it into y, . add x and y and store the result (22) in z Your TM should produce a string output equal to the value of register z (represented as a binary string) after the last instruction executes. So the correct output above is 00010110 Furthermore, your TM should halt in the accept state. You may assume only input strings matching the above description will be supplied. (Your TM does not have to detect syntax errors in the assembly language program.) Hint: It helps to use one worktape per register, and to write special marker symbols at the start of each of them to help identify when the tape head is scanning the left most tape cell It is also recommended to use wildcards in the transition rules; for detailed instructions on their use, see http://web.cs.ucdavis.edu/-doty/automata/help.html There will be 5 points extra credit for any correct TM with strictly fewer than 30 total transitions, with 10 points extra credit for the TM(s) with the smallest number of transitions. competition: This problem is due to be submitted on the same day as the rest of the home- work. However, there is an optional competition for the "most impressive/creative/elegantly implemented" additional instructions, (e.g., more arithmetic, conditional branching, subrou- tines) which will last until the end of the quarter. There is a $50 gift certificate to de Vere's for the winning entry. The winner will be determined by a vote among the students. You can work in groups (but you have to split the gift certificate if you win) To participate, email the following to me before (not on) the last day of lecture: . A .pdf file describing the instructions, along with example programs showing its capa- bilities. Give the programming language a name to use in the vote. . The .tm file, with the example programs included in comments at the top TM assembly: Design a TM to execute programs written in a simplified assembly-like language There are just four instructions: L, Mx, My, and A operating on three registers x, y, and z each holding a nonnegative integer L instructions load a certain constant number, represented in binary, into register z For example, the instruction L00000101 loads the integer 5 (represented by the bits 00000101) into z. Other bit strings can be specified. The number of bits may be arbitrary, but you may assume it is the same for all load instructions in the program. For instance, if the first instruction is L0011001100110011, then all remaining L instructions will be followed by exactly 16 bits Mx and My instructions move the value from z into x or y, respectively. (Actually, it's more like "copy" since the value in z is not erased, but "move" is the traditional assembly language name for this instruction.) A instructions add the values in registers x and y and store the result in register z. If the result overflows, the new most significant 1 is simply omitted; i.e., the result is taken mod 2k, where k is the number of bits specified in the first load instruction. For example, adding 11111111 (255) to 00000001 (1) results in 00000000 (0), and adding 11111010 (250) to 00001001 (9) results in 00000011 (3). (This might sound difficult, but actually the straightforward way to implement addition will automatically achieve this.) If an instruction needs to read a register (add must read x and y, and copy must read z), then you may assume that register has already had a value written to it The input will be a followed by a list of instructions, each followed by a :, such as 00000 1 1 0 :Mx : L00000 1 1 1 : My : A : Mx : L00001001: My :A: The above program does the following . load the value 6 into z and then move it into x . load the value 7 into z and then move it into y . add x and y and store the result (13) in z, move the value in z (13) into x, e load the value 9 into z and move it into y, . add x and y and store the result (22) in z Your TM should produce a string output equal to the value of register z (represented as a binary string) after the last instruction executes. So the correct output above is 00010110 Furthermore, your TM should halt in the accept state. You may assume only input strings matching the above description will be supplied. (Your TM does not have to detect syntax errors in the assembly language program.) Hint: It helps to use one worktape per register, and to write special marker symbols at the start of each of them to help identify when the tape head is scanning the left most tape cell It is also recommended to use wildcards in the transition rules; for detailed instructions on their use, see http://web.cs.ucdavis.edu/-doty/automata/help.html There will be 5 points extra credit for any correct TM with strictly fewer than 30 total transitions, with 10 points extra credit for the TM(s) with the smallest number of transitions. competition: This problem is due to be submitted on the same day as the rest of the home- work. However, there is an optional competition for the "most impressive/creative/elegantly implemented" additional instructions, (e.g., more arithmetic, conditional branching, subrou- tines) which will last until the end of the quarter. There is a $50 gift certificate to de Vere's for the winning entry. The winner will be determined by a vote among the students. You can work in groups (but you have to split the gift certificate if you win) To participate, email the following to me before (not on) the last day of lecture: . A .pdf file describing the instructions, along with example programs showing its capa- bilities. Give the programming language a name to use in the vote. . The .tm file, with the example programs included in comments at the top