Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top

Explore our questions

1 vote
1 answer
39 views

Turing Machine, UNLIMITED number of steps left or right on the tape?

1 vote
1 answer
241 views

How To Show That B is Semi-Decidable Given A

0 votes
0 answers
20 views

How to think about blank symbol when Turing Machine used as a function?

0 votes
0 answers
26 views

Equivalence for Turing Machines is not Recognizable - Reduction DOUBT

0 votes
1 answer
40 views

how to decide this language

0 votes
1 answer
36 views

Is a problem in NP if it runs in P time on a NDTM, verifiable in P on a DTM, but solution doesn’t halt on a DTM?

0 votes
1 answer
19 views

Decidability of the minimum number of states a Turing Machine needs to accept a language

0 votes
1 answer
68 views

Computation branches on NTM

0 votes
2 answers
462 views

Show that ALL DFA is decidable

0 votes
1 answer
100 views

Show that both set A and set B are Turing reducible to some mixture of A and B

0 votes
1 answer
726 views

Show that an instance of PCP or MPCP has no solutions

0 votes
1 answer
766 views

Determine if a language is Decidable or semi decidable

1 vote
1 answer
78 views

What are the differences between Oracle Turing Machine and PAC?

0 votes
0 answers
20 views

Are all languages determined in exponential time NP languages?

Browse more Questions