Problem 1: Stay-Put Turing Machine (6 points) A Stay-Put Tur…
Problem 1: Stay-Put Turing Machine (6 points) A Stay-Put Turing machine is a variant where the tape head has an additional option to stay in the same position. Its transition function is \(\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R, S\}\), where S denotes the ‘Stay’ move. Prove that every Stay-Put TM \(M_S\) can be simulated by an equivalent ordinary TM \(M\) (whose head can only move Left or Right). Problem 2: Swap Statement (4 points) Let us extend the IMP language with a swap statement. This command takes two variable names and swaps their integer values in the program state. $$ \text{Stmt} \ ::=\ \dots \mid \textbf{swap}(Var, Var) $$ Add the swap statement to the original big-step operational semantics by providing its inference rule. Congratulations, you are almost done with this quiz. You must submit your work before the exam timer runs out and Honorlock must remain running until you finish submitting your work to Gradescope. To submit your work: Use your smartphone to scan your answer sheets and save the scan as a PDF. Email the PDF to yourself. Submit your work to Gradescope: Quiz 1 Click below to agree to the honor pledge, and then click Submit Quiz.