search
Log In

Recent questions tagged turing-recognizable-languages

0 votes
4 answers
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
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 84 views
3 votes
0 answers
2
1 vote
0 answers
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.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 70 views
0 votes
0 answers
4
0 votes
0 answers
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$.)
asked Oct 17, 2019 in Theory of Computation Lakshman Patel RJIT 26 views
0 votes
0 answers
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.
asked Oct 17, 2019 in Theory of Computation Lakshman Patel RJIT 64 views
0 votes
0 answers
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.
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 11 views
0 votes
0 answers
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.
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 32 views
0 votes
0 answers
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?
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 34 views
0 votes
0 answers
18
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.
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 131 views
0 votes
0 answers
19
A Turing machine with doubly infinite tape is similar to an ordinary Turing machine, but its tape is infinite to the left as well as to the right. The tape is initially filled with blanks except for the portion that contains the input. Computation is defined as ... an end to the tape as it moves leftward. Show that this type of Turing machine recognizes the class of Turing-recognizable languages.
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 22 views
3 votes
1 answer
20
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
asked Dec 27, 2018 in Theory of Computation Ruturaj Mohanty 272 views
To see more, click for the full list of questions or popular tags.
...