Joezer's user avatar
Joezer's user avatar
Joezer's user avatar
Joezer
  • Member for 6 years, 6 months
  • Last seen more than 2 years ago
2 votes
2 answers
785 views

A reduction of $HALT_{TM}$ to $A_{TM}$

1 vote
1 answer
1k views

Closure of Turing-recognizable languages under homomorphism

0 votes
0 answers
115 views

Polynomial time verifier for $\overline { EQ_{CFG}}$

2 votes
2 answers
1k views

An infinite decidable language that is a subset of $\overline { A_{TM}}$

0 votes
1 answer
810 views

Is $E_{LBA}$ turing-recognizable?

4 votes
2 answers
5k views

Are all finite strings over some infinite alphabet countable?

0 votes
2 answers
729 views

Is it possible to prove closure of decidable languages under union and intersection, using enumerators?

0 votes
1 answer
89 views

What are all the decidable languages that can be constructed using a turing machine with only the Reject and Accept states?

2 votes
1 answer
742 views

Is a non-deterministic turing machine that both accepts and rejects the same input valid?

2 votes
1 answer
1k views

Is an infinite tape alphabet for TM valid? [duplicate]

2 votes
1 answer
854 views

TM that finds the middle of an input string in O(n) time

1 vote
1 answer
5k views

Are the undecidable languages closed under complement?