Exercise 9.15(c) on page 356 of Hopcroft, Ullman, and Motwani. There are many solutions to this problem; I give one below, in detail. Designing a TM is much like writing a program in ths most primitive machine language. We care very little about efficiency (although we would like the machine to run in polynomial time if possible, just to prove that the problem is in the class P-TIME), but being able to prove correctness is very important. Thought Step 1. We use as are starting point the following C++ code: for (int i = 1; i <= length(w); i++) for (int j = 1; j <= length(w); j++) cout << "1"; Thought Step 2: We need to somehow keep track of the values of i and j, while writing 1's. Our machine will be designed to work in "macro-steps." At the beginning and at the end of each macrostep, the head will be on the leftmost cell, which shall be blank. The non-blank contents of the string will start at the second cell, and will be called the "working string." The machine will operate in six "phases," each of which will consists of a number of macrosteps. Phase 1 checks to see of the input is empty. If so, the machine halts; otherwise it proceeds with the next five phases. Phase 1 begins in the start state q0, and ends either at the halt-accept state, h, or in state q2. Phase 2 consists of one macrostep, and places an octotroph at the end of the working string. Phase 2 starts in state q2 and ends in state q6. Phase 3 consists of n+1 macrosteps, and changes the working string from 1^n# to 0^n#1^n. Phase 3 starts in state q6 and ends in state XXX. Phase 4 consists of 1 macrostep, and places an octotroph at the end of the working string. Phase 5 consists of n^2 + n steps. At the end of phase 5, the working string is 0^n#0^n#1^n^2. Phase 6 is the "clean-up" phase. It compresses out all symbols except 1's. The machine halts at the end of phase 6, with the working string 1^n^2. The start-up phase is relatively easy. The head passes back and forth, changing each 1 to a 0 and making a new 1 to the right at each pass. Transition table for phase 1, "Check for empty input." q sigma delta(q,sigma) q0 Blank q1 Blank R q1 Blank h Blank L q1 1 q2 1 L Transition table for phase 2, "Place octotroph at the end." q sigma delta(q,sigma) q2 Blank q3 Blank R q3 Blank h Blank L q3 1 q4 1 R q4 1 q4 1 R q4 Blank q5 # L q5 Blank q6 Blank S In subphase 1, if the input is empty, the machine halts, correctly computing that 0^2 = 0. Otherwise, the head moves right until it encounters a blank, an octotroph, then returns to the leftmost cell, ending in state q4. Transition table for phase 3, "Initialize factors." q sigma delta(q,sigma) q6 Blank q7 Blank R q7 0 q7 0 R q7 1 q8 0 R q8 1 q8 1 R q8 # q8 # R q8 Blank q9 1 L q9 0 q9 0 L q9 1 q9 1 L q9 # q9 # L q9 Blank q6 Blank S q7 # q10 # L q10 0 q10 0 L q10 Blank q11 Blank S Subphase 3 starts in state q6, and 1^n# is the working string. The phase consists of n+1 macrosteps. During each macrostep except the last, it changes one 1 to a 0. The state of the machine as the head is moving to the right is q7 until it encounters a 1, at which point it changes the 1 to 0 and continues moving to the right in state 6 until it encounters a blank, where it writes a 1. The machine then goes to state q9 and moves to the left until it encounters the leftmost cell, where it reverts to state q6 for the next macrostep. If the machine does not encounter a 0, that is the last macrostep. If it reads the first octotroph in state q7, it moves back to the leftmost cell in state q10, where it changes to state q11, ending the phase. The working string is finally 0^n#1^n. Transition table for phase 4, "Place second octotroph." q sigma delta(q,sigma) q11 Blank q12 Blank R q12 1 q12 1 R q12 0 q12 0 R q12 # q12 # R q12 Blank q13 # L q13 1 q13 1 L q13 0 q13 0 L q13 # q13 # L q13 Blank q14 Blank S Subphase 3 is very similar to subphase 1. It ends in state q14 with 0^n#1^n# as the working string. We now consider the working phase, which starts in state q14. It consists of n^2+n iterations of a loop. Before and after each iteration of the loop, the working string is of the form 1^i0^j#1^p0^q#1^m, where i,j,p,q, and m are non-negative integers. We define the "potential" of a string 0^i1^j#0^p1^q#1^m to be q*(i+j) + j + m. (For example, the potential of 00011#01111#111 is 25.) Each iteration of the look consists of one macrostep. The potential of the working string will be the same after each iteration as before the iteration, and each iteration increases the the value of m-q. Since the potential is n^2 before the first iteration, and since j = q = 0 after the last iteration, we are guaranteed that m = n^2 after the last iteration. Here is a high-level C++ model of the loop: while (i > 0 || p > 0) if (j > 0){ j--; i++; m++; } else{ p--; q++; i = j; j = 0; } Transition table for the phase 5, "multiply" q sigma delta(q,sigma) q14 Blank q15 Blank R q15 0 q15 0 R q15 1 q16 0 R q16 0 q16 0 R q16 1 q16 1 R q16 # q16 # R q16 Blank q17 1 L q17 0 q17 0 L q17 1 q17 1 L q17 # q17 # L q17 Blank q14 Blank S q15 # q18 # R q18 0 q18 0 R q18 1 q19 0 L q19 0 q19 0 L q19 # q20 # L q20 0 q20 1 L q20 Blank q14 Blank S q18 # q21 # L q21 0 q21 0 L q21 1 q21 1 L q20 Blank q22 Blank S The working string at the end of phase 5 is 0^n#0^n#1^{n^2}, and the state is q22. Phase 6 is very simple. The start state for phase 6 is q22, and it ends in the halt state. It repeatedly erases a 1 from the right end and overwrites a 0 or an octotroph with a 1. I'll leave the details to you. The final working string is 1^n^2, as required.