AS TOC 4

Problem 1

Let the language $\{⟨M⟩:L(M)\text{ is regular}\}$ be denoted by $\text{REG}$. I will show that $\text{FIN}⩽\text{REG}$. Since $\text{FIN}\notin \text{RE}$ and $\text{FIN}\notin \text{co-RE}$, it will follow that $\text{REG}\notin \text{RE}$ and $\text{REG}\notin \text{co-RE}$.

Suppose $⟨M⟩\in \text{FIN}$. Let $\phi (⟨M⟩)$ be as described:

$$\begin{array}{rl}& \text{read }x\\ & \text{For }w\in {\Sigma }^{\ast }:\\ & \text{if }{2}^{|w|}>|x|:\text{reject}\\ & \text{if }{2}^{|w|}=|x|\text{ and }w\in L(M):\text{accept}\end{array}$$

Note that ${\Sigma }^{\ast }$ is enumerated above in lex order. The language of $\phi (⟨M⟩)$ is given by

$$\bigcup _{s\in S}{\Sigma }^{2^s},$$

where $S$ is a fixed subset of $\mathbb{N}$. If $L(M)$ is finite, $S$ is a finite subset, in which case the above language is finite, and hence regular. If $L(M)$ is infinite, $S$ is an infinite subset of $\mathbb{N}$. It is easily seen that this is not regular - the pumping lemma for regular languages tells us that the lengths of the words in the language must have an arithmetic subsequence, which contradicts the fact that the lengths of the words in the language must be a subsequence of the exponential sequence $\{2^n:n\in \mathbb{N}\}$.

---

Problem 2

Part a

A deterministic linearly bounded automaton is a 9-tuple

$$M=(Q,\Sigma ,\Gamma ,⊢,⊣,\delta ,s,t,r),$$

where $Q$ is a finite set of states, $\Sigma$ is the input alphabet, $\Gamma \supseteq \Sigma$ is the tape alphabet, $⊢\in \Gamma$ is the left endmarker, $⊣\in \Gamma$ is the right endmarker, $s\in Q$ is the start state, $t\in Q$ is the accept state, and $r\in Q$ is the reject state.

Initially, $M$ receives its input $w=w_1{w}_2\dots w_n\in {\Sigma }^{\ast }$ delimited by endmarkers on the tape as $⊢w⊣$. The head starts on the leftmost square of the tape, that is, on $⊢$. Note that $\Sigma$ does not contain the endmarker symbols. Once $M$ has started, the computation proceeds according to the transition function $\delta$.

$\delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ is constrained as follows: for all $q\in Q$,

$$\begin{array}{r}\delta (q,⊢)=(p_1,⊢,R),\\ \delta (q,⊣)=(p_2,⊣,L),\end{array}$$

for some $p_1,p_2\in Q$. $M$ cannot write $⊢$ or $⊣$ to the tape in any other circumstance.

The computation continues until $M$ enters either the accept or reject states. If neither occurs, $M$ foes on forever.

A configuration of $M$ is represented by $⊢uqv⊣$: $⊢uv⊣$ is the tape content, $q$ is the current state, and the head location is the first symbol of $v⊣$.

Part b

The number of possible configurations is given by $\alpha (n):=(m-2{)}^n\cdot (n+2)\cdot k$. There are $(m-2{)}^n$ strings of length $n$ over an alphabet of size $m-2$, after discounting the endmarkers. For each such string, the head can be in any of $n+2$ locations, inclusive of the endmarkers, and the machine could be in any of its $k$ states.

Part c

If the LBA doesn’t halt within $\alpha (n)$ steps given an input of size $n$, there must be a configuration $\mathbf{c}$ which the machine occupies twice by the pigeonhole principle. Moreover, if $\mathbf{c},{\mathbf{c}}_1,{\mathbf{c}}_2,\dots ,\mathbf{c}$ is the sequence of configurations the machine occupies between occupying $\mathbf{c}$ for the first and second time, it follows that the machine is not in a accept state in any of these configurations, since it would have halted if that were the case. Since the current configuration completely determines the sequence of future configurations the machine will attain, it follows that the machine will loop forever through the configurations $\mathbf{c},{\mathbf{c}}_1,{\mathbf{c}}_2,\dots ,\mathbf{c},{\mathbf{c}}_1,{\mathbf{c}}_2,\dots$. Thus, we only need to simulate an LBA for $\alpha (n)$ steps for an input of size $n$ to determine if it halts.

Part d

Let $\Sigma$ be any alphabet. Fix an enumeration $\{w_i{\}}_{i=1}^{\infty }$ of ${\Sigma }^{\ast }$ and $\{M_i{\}}_{i=1}^{\infty }$ of LBAs with input alphabet $\Sigma$. Let $\overline{\text{DIAG-LBA}}=\{w_i:w_i\notin L(M_i)\}$.

$\overline{\text{DIAG-LBA}}$ is recursive. Here’s a total Turing machine which accepts $\overline{\text{DIAG-LBA}}$:

$$\begin{array}{rl}& \text{read }w\\ & \text{compute }i\text{ such that }w=w_i,M_i\\ & \text{if }{M}_i\text{ halts on }{w}_i:\\ & \text{if }{M}_i\text{ accepts }{w}_i:\\ & \text{reject}\\ & \text{else}\\ & \text{accept}\\ & \text{else}\\ & \text{accept}\end{array}$$

Suppose an LBA $M$ recognizes $\overline{\text{DIAG-LBA}}$. Let $M=M_k\in \{M_i{\}}_{i=1}^{\infty }$. If $w_k\notin L(M_k)$, $w_k\in \overline{\text{DIAG-LBA}}$, so $M$ must accept $w_k$. However, that implies $w_k\in L(M)=L(M_k)$, a contradiction. On the other hand, if $w_k\in L(M_k)$, we have $w_k\in L(M)$, so $w_k\in \overline{\text{DIAG-LBA}}$ and $w_k\notin L(M_k)$, also a contradiction. Thus, we conclude that $\overline{\text{DIAG-LBA}}$ is not accepted by any LBA.