Skip to main content
Share Your Experience: Take the 2024 Developer Survey
Link L's user avatar
Link L's user avatar
Link L's user avatar
Link L
  • Member for 6 years, 8 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
177 views

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

3 votes
1 answer
55 views

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

3 votes
1 answer
1k views

CFG that generates $1^*$ is decidable

2 votes
1 answer
542 views

Understanding definition of NP and co-NP

2 votes
1 answer
67 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
115 views

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

1 vote
0 answers
396 views

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

1 vote
2 answers
509 views

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

1 vote
2 answers
80 views

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

1 vote
1 answer
212 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
322 views

Is it decidable for a NPDA to halt?

1 vote
2 answers
336 views

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

1 vote
1 answer
97 views

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

1 vote
1 answer
145 views

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

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
0 answers
126 views

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

0 votes
1 answer
464 views

Show that for every language there exists a harder language

0 votes
1 answer
160 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
115 views

show that this decidable set $C$ exists

0 votes
1 answer
815 views

Enumerators and recognizers

0 votes
1 answer
52 views

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

-1 votes
1 answer
244 views

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