CS637 - Quiz 3

Instructions

Attempt all questions.
For Q1 and Q2, use only the given primitive TM operations.
For Q3 and all Rice-theorem questions, explicitly justify semanticity and non-triviality.

Primitive P1: MOVE_LEFT (move one cell left)
Primitive P2: MOVE_RIGHT_UNTIL_END (move right until first blank symbol B)
Primitive P3: REPLACE_CURRENT_SYMBOL(s) (overwrite current cell with symbol s)
Primitive P4: IS_CURRENT_SYMBOL(s) (boolean test for current tape symbol)
Primitive P5: IS_CURRENT_BLANK (boolean test; true iff current symbol is B)
Primitive P6: READ_CURRENT_SYMBOL (returns current symbol for branching)
Primitive P7: IF <condition> THEN ... ELSE ...
Primitive P8: WHILE <condition> DO ...

Example (primitive style):
          MOVE_RIGHT_UNTIL_END
          MOVE_LEFT
          WHILE IS_CURRENT_SYMBOL(0) OR IS_CURRENT_SYMBOL(1) DO
          IF IS_CURRENT_SYMBOL(0) THEN REPLACE_CURRENT_SYMBOL(1)
          ELSE REPLACE_CURRENT_SYMBOL(0)
          MOVE_LEFT

Q1 TM Design Using Only Primitives: Bitwise Complement 10 pts

Design a single-tape TM that transforms a non-empty binary string \(w\in\{0,1\}^+\) into its bitwise complement in-place (every \(0\) becomes \(1\), every \(1\) becomes \(0\)). The head starts on the leftmost symbol of \(w\). Use only the primitives listed above.

Solution Idea: jump to the right end once, then sweep left and flip symbols.

Algorithm Complement(w)
            1. P2 // now on first blank B after input
            2. P1 // now on rightmost symbol of w
            3. While current symbol is 0 or 1:
            If current symbol = 0: P3(1)
            Else (current symbol = 1): P3(0)
            P1
            4. Halt (head has moved left of the original string onto B).

Why correct: each symbol is visited exactly once in the right-to-left sweep and is replaced by its complement. Why halts: finite string length; loop executes exactly \(|w|\) times.

Q2 TM Design Using Only Primitives: First Symbol Equals Last Symbol 10 pts

Design a TM for language \[ L=\{w\in\{0,1\}^+\mid \text{the first symbol of }w\text{ equals the last symbol of }w\}. \] Use only the primitives listed above.

Solution Save the first symbol in the state, then jump to the end and compare with the last symbol.

Algorithm FirstEqualsLast(w)
            1. Read first symbol:
            If 0, go to state qFirst0.
            If 1, go to state qFirst1.
            2. P2 // go to first blank after input
            3. P1 // step to last symbol of w
            4. If in qFirst0 and current symbol is 0: ACCEPT else REJECT.
            5. If in qFirst1 and current symbol is 1: ACCEPT else REJECT.

Correctness: machine compares exactly the first and last symbols, so it accepts iff they are equal. Halting: fixed finite sequence of operations with one comparison at the end.

Q3 Lamport-Style Fill in the Blanks (Rice's Theorem) 5 pts

Complete the following Lamport-style proof outline to show undecidability of \[ L_{\text{prefix}}=\{\langle M\rangle \mid \exists x,y\in L(M),\ x \text{ is a proper prefix of } y\}. \] Fill each blank.

Define property \(\mathcal{P}(L)\): [Blank A].
\(\mathcal{P}\) is semantic because [Blank B].
Witness language in \(\mathcal{P}\): [Blank C].
Witness language not in \(\mathcal{P}\): [Blank D].
Therefore \(\mathcal{P}\) is [Blank E].
By Rice's theorem, \(L_{\text{prefix}}\) is [Blank F].

Solution

Blank A: “\(L\) contains two strings where one is a proper prefix of the other.”
Blank B: it depends only on \(L(M)\), not on the encoding/syntax of \(M\).
Blank C: \(\{0,01\}\) (since \(0\) is a proper prefix of \(01\)).
Blank D: \(\{00,11\}\) (neither is a proper prefix of the other).
Blank E: non-trivial semantic property of RE languages.
Blank F: undecidable.

Q4 Undecidability via Rice: Language Has Exactly Two Strings 5 pts

Prove that \[ L_{=2}=\{\langle M\rangle\mid |L(M)|=2\} \] is undecidable.

Solution Let \(\mathcal{Q}(L)\) be property “\(|L|=2\)”.

Semantic: truth of \(\mathcal{Q}\) depends only on the set \(L(M)\).
Non-trivial:
- Witness in property: TM accepting exactly \(\{0,1\}\) (size 2).
- Witness out of property: TM accepting exactly \(\{0\}\) (size 1).
Hence \(\mathcal{Q}\) is a non-trivial semantic property of RE languages.
By Rice's theorem, \(L_{=2}\) is undecidable.

So deciding whether an arbitrary TM recognizes exactly two strings is impossible.

Q5 Undecidability via Rice: Language is Closed Under Reversal 5 pts

Prove that \[ L_{\text{rev}}=\{\langle M\rangle\mid \forall x\ (x\in L(M)\Rightarrow x^R\in L(M))\} \] is undecidable.

Solution Let \(\mathcal{R}(L)\) be: “\(L\) is closed under reversal”.

Semantic: depends only on \(L(M)\).
Non-trivial:
- In property: \(L=\Sigma^*\) is closed under reversal.
- Out of property: \(L=\{01\}\) is not closed under reversal since \(10\notin L\).
So \(\mathcal{R}\) is a non-trivial semantic property of RE languages.
By Rice's theorem, \(L_{\text{rev}}\) is undecidable.

Q6 Undecidability via Rice: Contains Exactly One Palindrome 5 pts

Prove that \[ L_{\text{1pal}}=\{\langle M\rangle\mid L(M)\text{ contains exactly one palindrome}\} \] is undecidable.

Solution Define \(\mathcal{S}(L)\): “\(L\) contains exactly one palindrome”.

Semantic: determined solely by \(L\).
Non-trivial:
- In property: \(L=\{00,01\}\) has exactly one palindrome (\(00\)).
- Out of property: \(L=\{00,11\}\) has two palindromes.
Hence \(\mathcal{S}\) is non-trivial and semantic over RE languages.
By Rice's theorem, \(L_{\text{1pal}}\) is undecidable.

Q7 Undecidability by Reduction: Non-Empty Intersection 10 pts

Prove that \[ INTERSECT_{TM}=\{\langle M_1,M_2\rangle\mid L(M_1)\cap L(M_2)\neq\emptyset\} \] is undecidable by reducing \(HALT_{TM}\) to it.

Solution Reduce from \(HALT_{TM}=\{\langle M,w\rangle\mid M\text{ halts on }w\}\). Given \(\langle M,w\rangle\), build \(\langle M_1,M_2\rangle\):

\(M_1\): accepts exactly one fixed string, say \(0\).
\(M_2\) on input \(x\): ignore \(x\), simulate \(M(w)\); if \(M\) halts on \(w\), accept; otherwise loop.

Then:

If \(M\) halts on \(w\), \(M_2\) accepts every input, so \(0\in L(M_1)\cap L(M_2)\), intersection non-empty.
If \(M\) does not halt on \(w\), \(M_2\) accepts nothing, so intersection is empty.

Therefore \[ \langle M,w\rangle\in HALT_{TM}\iff \langle M_1,M_2\rangle\in INTERSECT_{TM}. \] So \(HALT_{TM}\le_m INTERSECT_{TM}\). Since \(HALT_{TM}\) is undecidable, \(INTERSECT_{TM}\) is undecidable.