Skip to main content
Link L's user avatar
Link L's user avatar
Link L's user avatar
Link L
  • Member for 6 years, 10 months
  • Last seen more than a month ago
3 votes
1 answer
1k views

CFG that generates $1^*$ is decidable

0 votes
1 answer
58 views

Is there a way to map the concatenation operation over strings to the addition operation over $\mathbb{N}$

0 votes
1 answer
3k views

What undecidable language $B$ is reducible to its complement?

1 vote
1 answer
146 views

Why is this language Turing recognizable and not not-Turing recognizable

2 votes
0 answers
100 views

How to show that these two disjoint sets $A$ and $B$ exist

0 votes
1 answer
466 views

Show that for every language there exists a harder language

0 votes
0 answers
134 views

proof that $NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$

1 vote
1 answer
98 views

Is $NSPACE(S(n)) \subseteq DSPACE(S(n))$ if $S(n)$ is time-constructible?

2 votes
1 answer
69 views

How to understand definition of $\Pi_k$ in arithmetical heirarchy

2 votes
1 answer
551 views

Understanding definition of NP and co-NP

3 votes
1 answer
56 views

How to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages

1 vote
2 answers
338 views

Difference between regular grammar and CFG in generating computation histories and $\Sigma^*$

0 votes
1 answer
164 views

Help in understanding 'reasonable' encoding of inputs

1 vote
2 answers
326 views

Is it decidable for a NPDA to halt?

0 votes
0 answers
77 views

Find decidable sets such that $A$ reduces to $B$ but not vice versa

1 vote
1 answer
65 views

Why is this function computable in polynomial time?

4 votes
2 answers
1k views

show that in every infinite computably enumerable set, there exists an infinite decidable set

0 votes
1 answer
116 views

show that this decidable set $C$ exists

0 votes
1 answer
54 views

Is this correct : whether or not a type 3 grammar generates $\Sigma^*$ is not c.e

0 votes
1 answer
824 views

Enumerators and recognizers

1 vote
0 answers
408 views

Can a CFG generate an accepting configuration? - or is there a turing-recognizable CFG language that is not decidable

2 votes
1 answer
116 views

Recursion Theorem : why does $SELF$ need $A$ and $B$ parts?

4 votes
1 answer
119 views

What is an example of set $A$, that is decidable if $AA$, but which is not decidable if it is $A$ alone

1 vote
1 answer
213 views

Show that for A and B, a language J exists such that A $\leq_T$ J, B $\leq_T$ J

1 vote
2 answers
81 views

Why is $A \leq_T \bar{A}$?

1 vote
2 answers
510 views

Many to one reductions from undecidable Turing Machine to a decidable language

3 votes
2 answers
178 views

Examples of sets $A$ and $B$ such that $A \leq_m B$ but not $B \leq_m A$

-1 votes
1 answer
245 views

What is the range of a universal turing machine (partial function)?

4 votes
1 answer
1k views

Pumping Lemma for single character language [duplicate]