# Recent questions tagged turing-recognizable-languages 1
The collection of Turing recognizable languages are closed under: Union Intersection Complement Concatenation Star Closure (i) Only Both (i),(iv) (i),(ii),(iv)and(v) All of the options
2
Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CFG}\}$. Show that $MIN_{CFG}$ is $T-$recognizable. Show that $MIN_{CFG}$ is undecidable.
1 vote
3
Say that a variable $A$ in $CFG \:G$ is necessary if it appears in every derivation of some string $w \in G$. Let $NECESSARY_{CFG} = \{\langle G, A\rangle \mid \text{A is a necessary variable in G}\}$. Show that $NECESSARY_{CFG}$ is Turing-recognizable. Show that $NECESSARY_{CFG}$is undecidable.
4
Let $J = \{w \mid \text{either$w = 0x$for some$x \in A_{TM},$or$w = 1y\:$for some$y \in \overline{A_{TM}}\:\:$}\}$. Show that neither $J$ nor $\overline{J}$ is Turing-recognizable.
5
Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.
6
Show that if $A$ is Turing-recognizable and $A\leq_{m} \overline{A},$ then $A$ is decidable.
7
Show that $EQ_{CFG}$ is co-Turing-recognizable.
8
Let $A$ be a Turing-recognizable language consisting of descriptions of Turing machines, $\{ \langle M_{1}\rangle,\langle M_{2}\rangle,\dots\}$, where every $M_{i}$ is a decider. Prove that some decidable language $D$ is not decided by any decider $M_{i}$ whose description appears in $A$. (Hint: You may find it helpful to consider an enumerator for $A$.)
9
Let $A$ and $B$ be two disjoint languages. Say that language $C$ separates $A$ and $B$ if $A \subseteq C$ and $B \subseteq \overline{C}$. Show that any two disjoint co-Turing-recognizable languages are separable by some decidable language.
10
Let $C$ be a language. Prove that $C$ is Turing-recognizable iff a decidable language $D$ exists such that $C = \{x \mid \exists y (\langle{ x, y \rangle} \in D)\}$.
11
Let $E_{TM} = \{\langle{ M \rangle } \mid M\: \text{is a TM}\: \text{and}\: L(M) = \phi\}$. Show that $E_{TM}$, the complement of $E_{TM}$, is Turing-recognizable.
12
Show that single-tape $TMs$ that cannot write on the portion of the tape containing the input string recognize only regular languages.
13
Show that every infinite Turing-recognizable language has an infinite decidable subset.
14
Let $B = \{\langle {M_{1}\rangle},\langle{ M_{1}\rangle} , \dots \}$ be a Turing-recognizable language consisting of $TM$ descriptions. Show that there is a decidable language $C$ consisting of $TM$ descriptions such that every machine described in $B$ has an equivalent machine in $C$ and vice versa.
15
Show that the collection of Turing-recognizable languages is closed under the operation of union. concatenation. star. intersection. homomorphism.
16
A queue automaton is like a push-down automaton except that the stack is replaced by a queue. A queue is a tape allowing symbols to be written only on the left-hand end and read only at the right-hand end. Each write operation (we'll call it a ... a special accept state at any time. Show that a language can be recognized by a deterministic queue automaton iff the language is Turing-recognizable.
17
A Turing machine with stay put instead of left is similar to an ordinary Turing machine, but the transition function has the form $\delta: Q\times \Gamma \rightarrow Q\times \Gamma \times \{R,S\}$ At each point, the machine can move its head ... the same position. Show that this Turing machine variant is not equivalent to the usual version. What class of languages do these machines recognize?
A Turing machine with left reset is similar to an ordinary Turing machine, but the transition function has the form $\delta: Q\times \Gamma \rightarrow Q\times \Gamma \times \{R,RESET\}$ If $\delta(q, a) = (r, b, RESET),$ when the machine ... not have the usual ability to move the head one symbol left. Show that Turing machines with left reset recognize the class of Turing-recognizable languages.
Consider the following language $L$: $L=\{<M,x,k> \mid M \text{ is a Turing Machine and M does not halt on x within k steps} \}$ The language family to which $L$ belongs is not closed under? Intersection Homomorphism Set Difference Complementation