Out: Tuesday, 9-Jan
Due: Tuesday, 16-Jan before class
Warmup: Sipser (3rd ed.): Exercise 3.2
[This problem should have parts (a)-(e) with the strings '11', '1#1', '1##1', etc.]
Implementation in imaginary hardware
Give a full description of a Turing machine that decides the following language over the alphabet \(\{0,1\}\):
\(\{ w : w \) contains more 0s than 1s \(\}\)Your description should use a finite-state machine to describe the transition function. Try to be as succinct and clean as possible.
[Please give a brief explanation of how your TM works and/or label the states / collections of states in a suggestive way.]
Universality: Two-dimensional Turing machines
Our standard Turing machine model is equipped with a 1-dimensional infinite tape. Suppose we allow ourselves to use a 2-dimensional TM. Such a Turing machine has an infinite grid of tape cells, one for every pair \((x,y)\) of integers. The tape head always starts at position \((0,0)\).
The 2D TM operates just like a 1D Turing machine, except that at each step, the tape head can move up, down, left, or right. Show that this type of Turing machine recognizes exactly the class of Turing-recognizable languages.
[Hint: You may use the fact, already established in class, that multi-tape TMs can be simulated by a single tape TM. But our multi-tape machine was not allowed infinitely many tapes!]
[Also: You are allowed to write your TM description using pseudocode.]
Ordered enumeration
Consider the alphabet \(\Sigma = \{1,2,3,4,5,6,7,8,9\}\).
Show that a language \( \mathcal{L} \subseteq \Sigma^* \) is Turing-decidable if and only if \(\mathcal{L}\) can be enumerated by a Turing machine in an order \(x_1, x_2, x_3, \ldots\) such that each string appears at most once, and the sum of the decimal digits in \(x_{i+1}\) is always at least the sum of the decimal digits in \(x_{i}\) for each \(i=1,2,3,\ldots\).
[For example, such an enumerator could output the sequence \(112, 123, 11212, 19, ...\) but for instance, \(123\) cannot be followed by \(112\).]
Prove that if we add \(0\) to the alphabet in Problem (4), then there is a language \(\mathcal{L} \subseteq \Sigma^*\) that can be enumerated so that every string appears at most once and the sum-of-digits is never decreasing, but such that \(\mathcal{L}\) is not Turing-decidable.
[Hint: For this problem, you only need to know that there exists a language that is Turing-recognizable but not Turing-decidable. For instance, the \(A_{\mathrm{TM}}\) language.]
Suppose we change the Turing machine model so that it cannot alter the input (attempting to overwrite the input symbols does nothing), but it can write anywhere else on the tape. Prove that such a Turing machine cannot recognize the very first language we studied: \(\{ w \# w : w \in \{0,1\}^* \}\).
[Hint: Think first about why a DFA cannot recognize this language. Remember the method from CSE 311.]