Link L's user avatar
Link L's user avatar
Link L's user avatar
Link L
  • Member for 6 years, 7 months
  • Last seen more than a month ago
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

4 votes
1 answer
1k views

Pumping Lemma for single character language [duplicate]

4 votes
2 answers
1k views

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

3 votes
2 answers
176 views

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

3 votes
1 answer
54 views

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

2 votes
1 answer
539 views

Understanding definition of NP and co-NP

2 votes
1 answer
65 views

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

2 votes
0 answers
98 views

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

2 votes
1 answer
1k views

CFG that generates $1^*$ is decidable

2 votes
1 answer
113 views

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

1 vote
0 answers
327 views

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

1 vote
2 answers
508 views

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

1 vote
2 answers
79 views

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

1 vote
1 answer
209 views

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

1 vote
1 answer
65 views

Why is this function computable in polynomial time?

1 vote
2 answers
316 views

Is it decidable for a NPDA to halt?

1 vote
2 answers
332 views

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

1 vote
1 answer
144 views

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

1 vote
1 answer
95 views

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

0 votes
0 answers
115 views

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

0 votes
1 answer
461 views

Show that for every language there exists a harder language

0 votes
1 answer
2k views

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

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
159 views

Help in understanding 'reasonable' encoding of inputs

0 votes
0 answers
77 views

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

0 votes
1 answer
112 views

show that this decidable set $C$ exists

0 votes
1 answer
800 views

Enumerators and recognizers

0 votes
1 answer
49 views

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

-1 votes
1 answer
243 views

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