CS 637: Mathematics-II

Solution: Input format is \(x\#y\) where \(x,y\in\{0,1\}^*\).

Tape alphabet: \(\Gamma=\{0,1,\#,\square\}\) (and optionally a marker symbol \(X\)).

Goal/output convention: overwrite the tape so that, when the machine halts, the tape contains \(x\#(x+y)\) (sum written to the right of #).

Small, well-defined steps (single-tape).

1. Go to separator. From the left end, move right until reading #.
2. Go to end of \(y\). Move right until reading \(\square\); step left (now on the least significant bit of \(y\)).
3. Main loop (add one column). Keep the carry in the state (\(c\in\{0,1\}\)). Repeat:
   1. Read \(y\)-bit. If on \(0\) or \(1\), remember it in the state and overwrite it with \(\square\) (consuming it). If you are already on # (i.e., no more \(y\) bits), treat the \(y\)-bit as \(0\).
   2. Move to matching \(x\)-bit. Move left across # into \(x\); then move left until either (i) you reach \(\square\) (no more \(x\) bits) or (ii) you are on the rightmost remaining \(0/1\) of \(x\).
   3. Read \(x\)-bit. If on \(0\) or \(1\), remember it and overwrite it with \(\square\) (consuming it). If on \(\square\) (past the left end of \(x\)), treat the \(x\)-bit as \(0\).
   4. Compute sum bit. Compute \(s = x_i \oplus y_i \oplus c\) and new carry \(c'\in\{0,1\}\) (standard full-adder).
   5. Write output bit. Move right to #, then move right until the first \(\square\) cell; write \(s\) there.
   6. Return to next \(y\) position. Move left back to #, then move right to the rightmost remaining bit of \(y\) (i.e., move right until \(\square\), then step left).
   7. Set \(c\leftarrow c'\).
4. Stop condition. When both \(x\) and \(y\) are exhausted (you encounter \(\square\) to the left of # when searching for \(x\), and you are on # when searching for \(y\)), if \(c=1\) write a final \(1\) at the end of the output; then halt.

Solution: The addition is performed from the least significant bits:

1. \(1+0+0=1\).
2. \(0+1+0=1\).
3. \(1+1+0=0\) with carry \(1\).
4. No bits left in \(x\): \(0+0+1=1\).

So the sum is \(1011\) (since \(5+6=11\)).

Solution: Each main iteration marks at least one previously unmarked input symbol (in \(x\) or in \(y\)). Since there are finitely many symbols, only finitely many iterations occur. After both halves are exhausted and the final carry is handled, the machine transitions to \(q_{accept}\) and halts.

Solution: On a single tape, producing each output bit typically requires scanning back and forth across the input, giving \(O(n^2)\) time for input length \(n\).

Solution: Use markers \(A\) (for "this \(a\) has been matched") and \(B\) (for "this \(b\) has been matched").

Small, well-defined steps. Repeat the following procedure:

1. Find leftmost unmarked symbol. Move the head to the left end of the input; scan right until you see an unmarked \(a\) or \(b\).
2. If none found. If you reach \(\square\) without finding an unmarked symbol, accept.
3. Mark it and remember which.
   • If you see \(a\), overwrite it with \(A\) and enter a state "looking for matching \(a\)".
   • If you see \(b\), overwrite it with \(B\) and enter a state "looking for matching \(b\)".
4. Go to right end. Move right until you see \(\square\); then move left (now on the rightmost symbol).
5. Find rightmost unmarked symbol. Scan left skipping markers \(A,B\) until you see an unmarked \(a\) or \(b\) (or until you hit \(\square\) on the left).
6. Compare and mark.
   • If you are in "matching \(a\)" state: if symbol is \(a\), overwrite with \(A\); otherwise reject.
   • If you are in "matching \(b\)" state: if symbol is \(b\), overwrite with \(B\); otherwise reject.
7. Return. Move left to the left end and repeat.

Solution: One valid formalization is: \[ M=(Q,\Sigma,\Gamma,\delta,q_0,q_{accept},q_{reject}),\qquad \Sigma=\{a,b\},\quad \Gamma=\{a,b,A,B,\square\}. \] Let \[ Q=\{q_0,q_{seekR_a},q_{seekR_b},q_{match_a},q_{match_b},q_{back},q_{accept},q_{reject}\}. \] \(\delta\) implements the algorithm in part (a): from \(q_0\) it finds the leftmost unmarked symbol and branches to \(q_{seekR_a}\) or \(q_{seekR_b}\); those go right to \(\square\) then step left to \(q_{match_a}/q_{match_b}\); those verify/mark the rightmost symbol and go to \(q_{back}\); \(q_{back}\) returns to the left end and then to \(q_0\).

Solution: The machine marks outer pairs, then inner pairs:

1. Mark leftmost \(a\) and rightmost \(a\): \(AbaabA\).
2. Mark next leftmost \(b\) and next rightmost \(b\): \(ABaaBA\).
3. Mark next \(a\) and next \(a\): \(ABAABA\).
4. No unmarked symbols remain \(\Rightarrow\) accept.

Solution: Copy the input onto tape 2 while moving right on tape 1; then move left on tape 2 and compare tape 1 (left-to-right) with tape 2 (right-to-left). This reduces repeated rescans and yields \(O(n)\) time (up to constant factors) on a 2-tape TM.

Solution: Let tape 1 start with input \(x\); tape 2 starts blank.

Small, well-defined steps (2 tapes).

1. Check even length (tape 1). Place head 1 at the left end and scan right, toggling a parity bit in the state for each symbol read. If you stop on \(\square\) with odd parity, reject.
2. Copy first half to tape 2. Return head 1 to the left end. Move head 1 two steps right at a time; for each such 2-step, copy the first of the two symbols onto tape 2 (write it, then move head 2 right). When head 1 reaches \(\square\), tape 2 contains the first half \(w\).
3. Position to start of second half. Return head 1 to the left end again; move head 1 right exactly \(|w|\) steps (this can be done by rewinding tape 2 to its left end, then for each symbol on tape 2, move head 1 right once).
4. Compare. Rewind tape 2 to its left end. While head 2 reads \(0\) or \(1\):
   1. If the symbol under head 1 differs from the symbol under head 2, reject.
   2. Otherwise move both heads right by one.
5. Accept. If tape 2 ends exactly when head 1 also ends the string (hits \(\square\)), accept; otherwise reject.

Solution: With tape 2 holding a clean copy of the first half, the comparison is a single pass. A single-tape TM typically needs many back-and-forth passes to "remember" positions, adding an extra linear factor.

Solution: Represent the \(k\) tapes on one tape separated by delimiters, and mark the simulated head positions (e.g. using dotted symbols). Each simulated step scans to collect the \(k\) symbols under the head markers, applies the \(k\)-tape transition, writes updated symbols, and moves the markers (shifting as needed when moving onto new blank cells).

Solution: The standard simulation incurs at most a quadratic slowdown: if the \(k\)-tape machine runs in \(T(n)\) time, the 1-tape simulation runs in \(O(T(n)^2)\) time.

Solution:

• Decidable (recursive): some TM halts on every input and accepts exactly the strings in \(L\).
• Recognizable (recursively enumerable, RE): some TM accepts exactly the strings in \(L\) (it may loop forever on \(x\notin L\)).
• Co-recognizable: \(\overline{L}\) is recognizable.

Solution: Example: \[ HALT=\{\langle M,w\rangle \mid M\text{ halts on input }w\}. \] It is recognizable by simulating \(M\) on \(w\) and accepting if it halts. It is not decidable by the standard halting problem argument (diagonalization/reduction).

Solution: Let \(M_1\) recognize \(L\) and \(M_2\) recognize \(\overline{L}\). On input \(x\), dovetail simulations of \(M_1(x)\) and \(M_2(x)\) step-by-step in parallel. Exactly one of them must eventually accept; accept if \(M_1\) accepts, otherwise reject. This halts on all inputs and decides \(L\).

Solution: \[ L_{empty}=\{\langle M\rangle\mid L(M)=\emptyset\} \] is undecidable by Rice's theorem ("emptiness" is a nontrivial semantic property). It is neither recognizable nor co-recognizable.

Solution: An NTM has a transition relation \(\delta:Q\times\Gamma\to \mathcal{P}(Q\times\Gamma\times\{L,R,S\})\); a string is accepted if some computation branch reaches \(q_{accept}\). A DTM has at most one move for each \((q,\gamma)\).

Solution: On input \(w\):

1. Repeatedly nondeterministically choose a pair consisting of one unmarked \(0\) and one unmarked \(1\) anywhere on the tape; mark both (e.g. \(0\mapsto X\), \(1\mapsto Y\)).
2. If no unmarked symbols remain, accept.
3. If one of \(\{0,1\}\) is exhausted while the other still has unmarked symbols, reject.

Solution: A DTM can simulate the NTM by exploring its computation tree in breadth-first order (dovetailing over all branches). If an accepting branch exists, the BFS simulation eventually reaches it and accepts.

Solution: Savitch's theorem states that for space-constructible \(s(n)\ge \log n\), \[ NSPACE(s(n))\subseteq SPACE(s(n)^2). \] So nondeterminism yields at most a quadratic savings in space.

Solution: A semi-infinite tape TM can simulate a two-way-infinite tape by encoding the left and right halves on separate "tracks" (or separate regions) of its tape; cells left of the origin are stored reversed. Moves across the origin correspond to switching tracks. Conversely, a standard TM can simulate a semi-infinite tape TM by reserving a left-end marker and never moving left of it.

Solution: Dovetail over all \((i,j)\in\mathbb{N}_{\ge1}^2\): for \(s=2,3,4,\dots\) enumerate all pairs with \(i+j=s\), and for each output \(a^i b^j c^{ij}\). This enumerates exactly the language.

Solution: (\(\Rightarrow\)) If \(L\) is recognizable by \(M\), enumerate all \(x\in\Sigma^*\) and dovetail simulations of \(M(x)\); whenever a simulation accepts, print \(x\).

(\(\Leftarrow\)) If an enumerator prints exactly \(L\), then to recognize \(L\) on input \(w\), simulate the enumerator until it prints \(w\), then accept.

Solution: All three are Turing-complete: they recognize/decide exactly the Turing-recognizable/decidable languages (under standard encodings).

Solution: If \(M_1\) recognizes \(L_1\) and \(M_2\) recognizes \(L_2\), then on input \(x\) dovetail simulations of \(M_1(x)\) and \(M_2(x)\) in parallel; accept if either accepts. This recognizes \(L_1\cup L_2\).

Solution: For concatenation, on input \(x\) enumerate all splits \(x=uv\) and dovetail runs of \(M_1(u)\) and \(M_2(v)\); accept if some split makes both accept.

For Kleene star, enumerate all decompositions \(x=w_1\cdots w_m\) and dovetail runs of \(M\) on each \(w_i\); accept if some decomposition makes all pieces accept.

Solution: If RE were closed under complement, then for any RE language \(L\), both \(L\) and \(\overline{L}\) would be RE, implying \(L\) decidable (by dovetailing). But \(HALT\) is RE and not decidable, contradiction.

Solution: If \(M\) decides \(L\), swapping accept/reject decides \(\overline{L}\). If \(M_1,M_2\) decide \(L_1,L_2\), run both (they halt) and accept according to Boolean logic for union/intersection.

Solution: Use \(1+3+5+\cdots+(2n-1)=n^2\).

Tape symbols: \(a\) (unmarked), \(X\) (marked/removed \(a\)), \(|\) (unary counter in a work zone), and \(\square\).

Small, well-defined steps (single tape).

1. Initialize. If the first cell is \(\square\), accept. Otherwise, go to the first \(\square\) to the right of the input and write one \(|\) (this represents \(t=1\)).
2. Subtract \(t\) from the number of \(a\)'s. Repeat the following until all \(|\)'s have been "used":
   1. Move right to the work zone; find the leftmost unused \(|\).
   2. Mark it temporarily (e.g. by deleting it and remembering in the state that one \(|\) was consumed).
   3. Move left into the input region; scan right to find the leftmost unmarked \(a\). If found, overwrite it with \(X\).
   4. If no unmarked \(a\) exists when you still need to consume some \(|\), reject.
3. Check for exact exhaustion. Scan the input region: if there is no unmarked \(a\), accept.
4. Increase odd counter by 2. Move to the end of the work zone and append two \(|\) symbols (so \(t\leftarrow t+2\)).
5. Repeat. Restore the used-marker convention for the \(|\)'s (so the next subtraction will use all \(|\)'s) and go back to step 2.

Solution: A compact state sketch:

• \(q_{init}\): handle empty input / initialize counter.
• \(q_{sub}\): perform one subtraction pass by marking \(t\) unmarked \(a\)'s.
• \(q_{check}\): check whether any unmarked \(a\) remains.
• \(q_{inc}\): increase the odd counter by \(2\) and return to \(q_{sub}\).
• \(q_{accept},q_{reject}\).

Tape alphabet can be \(\{a,X,\square,|\}\) where \(|\) is the unary counter symbol.

Solution:

• \(aaaa\) (\(m=4\)): subtract \(1\) \(\Rightarrow\) 3 left; subtract \(3\) \(\Rightarrow\) 0 left \(\Rightarrow\) accept.
• \(aaaaa\) (\(m=5\)): subtract \(1\) \(\Rightarrow\) 4 left; subtract \(3\) \(\Rightarrow\) 1 left; next odd is \(5\) but only 1 remains \(\Rightarrow\) reject.

Solution: There are \(\Theta(\sqrt{m})\) subtraction rounds, each costing \(\Theta(m)\) time due to scanning/marking, so the total time is \(\Theta(m^{3/2})\) (up to constant factors). Space is \(O(m)\) for the input plus \(O(\sqrt{m})\) for the counter. A more efficient multi-tape design can approach \(O(m)\) time by keeping counters on separate tapes and avoiding full rescans.

Solution: Use the identity \[ ( k+1 )^3 - k^3 = 3k^2 + 3k + 1. \] So starting at \(k=0\), we can repeatedly subtract the next "cube increment" \(3k^2+3k+1\); the input length is a perfect cube iff we reach exactly \(0\).

Tape symbols: \(a\) (unmarked), \(X\) (marked/removed \(a\)), \(|\) (unary counter), separators \(\#\), and \(\square\). We maintain three unary counters in a work zone to the right of the input: \[ \#K\#S\#T\# \] where \(K\) encodes \(k\), \(S\) encodes \(k^2\) (so \(|S|=k^2\)), and \(T\) is a scratch area.

Small, well-defined steps (single tape).

1. Initialize work zone.
   1. Scan right to the first \(\square\) after the input and write the delimiters \(\#K\#S\#T\#\).
   2. Set \(K\) empty (so \(k=0\)) and set \(S\) empty (so \(k^2=0\)).
2. Main loop (subtract \(d=3k^2+3k+1\)). Repeat:
   1. Build \(d\) in scratch area \(T\).
      1. Erase all \(|\) in \(T\) (scan within \(T\) and write \(\square\)).
      2. Copy \(S\) three times into \(T\). For \(i=1,2,3\) do:
         1. Scan \(S\) left-to-right; for each \(|\) in \(S\), move to the end of \(T\) and append one \(|\); return to continue scanning \(S\).
      3. Copy \(K\) three times into \(T\). For \(i=1,2,3\) do:
         1. Scan \(K\) left-to-right; for each \(|\) in \(K\), move to the end of \(T\) and append one \(|\); return to continue scanning \(K\).
      4. Append one extra \(|\) to \(T\) (this is the "+1").
   2. Subtract \(|T|\) many \(a\)'s. For each \(|\) in \(T\) (scan \(T\) left-to-right):
      1. Move left into the input region.
      2. Scan right to find the leftmost unmarked \(a\); if found, overwrite it by \(X\).
      3. If no unmarked \(a\) exists, reject (cannot subtract the next increment).
      4. Return right to the next \(|\) in \(T\).
   3. Check for exact exhaustion. Scan the input: if there is no unmarked \(a\), accept.
   4. Update counters: \(k\leftarrow k+1\) and \(k^2\leftarrow (k+1)^2\).
      1. Increment \(K\). Move to the end of \(K\) and append one \(|\).
      2. Update \(S\) by adding \(2k-1\) (using the new \(K\)).
         1. Erase \(T\).
         2. Copy \(K\) twice into \(T\) (same copy procedure as above), then delete one \(|\) from \(T\).
         3. For each \(|\) in \(T\), append one \(|\) to the end of \(S\).

Solution: Use markers \(X\) for "paired/removed" \(a\) and \(Y\) for "kept representative" \(a\).

Small, well-defined steps (single tape).

1. If input is empty, reject. (This language starts at \(a^{2^0}=a\).)
2. Main loop (halve).
   1. Check if exactly one \(a\) remains. Scan the tape: if there is exactly one unmarked \(a\) and no other unmarked \(a\)'s, accept.
   2. Pairing pass. Return to the left end. While you can find two unmarked \(a\)'s:
      1. Scan right to the first unmarked \(a\); change it to \(X\).
      2. Continue right to the next unmarked \(a\); change it to \(Y\) (this represents one \(a\) in the halved string).
   3. Oddness test. After the pairing pass, scan again: if there exists an unmarked \(a\) (unpaired) then reject.
   4. Compress. Replace each \(Y\) by \(a\) (these are the new unmarked \(a\)'s for the next round) and erase all \(X\)'s (write \(\square\)). Then return to the left end.

Solution: Use markers \(A\) for marked \(a\) and \(B\) for marked \(b\).

Small, well-defined steps (single tape).

1. Format check. Scan left-to-right: once you see a \(b\), if you later see an \(a\), reject. (So the string is \(a^*b^*\).)
2. Special case \(n=0\). If the tape is empty, accept.
3. Outer loop (do \(n\) rounds). Repeat until all \(a\)'s are marked:
   1. Mark one \(a\). Move to the left end; scan right to the first unmarked \(a\); overwrite it with \(A\). If none exists, stop the outer loop.
   2. Inner loop (mark \(n\) many \(b\)'s). To mark exactly \(n\) \(b\)'s, do the following "counting by the \(a\)-block":
      1. Move to the left end.
      2. Scan right over the \(a\)-block; for each \(a\) or \(A\) encountered, do:
         1. Move right into the \(b\)-block; scan right to the first unmarked \(b\); overwrite it with \(B\).
         2. If no unmarked \(b\) exists when one is required, reject.
         3. Return left to the start of the tape to continue scanning the \(a\)-block.
4. Final check. After the outer loop, scan the \(b\)-block: if any unmarked \(b\) remains, reject; otherwise accept.