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

5 votes
6 answers
15k views

Prove if $L = \{0^m1^n \mid m \neq n\}$ is regular or not

0 votes
2 answers
1k views

In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?

0 votes
1 answer
37 views

How to show that the following function $F$ is primitive recursive?

0 votes
1 answer
57 views

Computation branches on NTM

0 votes
2 answers
156 views

Show that ALL DFA is decidable

0 votes
1 answer
195 views

Are these functions computable?

0 votes
1 answer
62 views

How to build a DFA that recognizes a language

0 votes
1 answer
638 views

Show that an instance of PCP or MPCP has no solutions

0 votes
1 answer
27 views

Infinite loops and the computability of mapping reductions

0 votes
0 answers
18 views

Equivalence between Lambda Calculus [Church] and Computable Partial Functions [Godel]

0 votes
2 answers
226 views

IS SUBSET-SUM in P if b(the sum) is given in unary and a1,...,an is in binary?

1 vote
0 answers
29 views

"Reasonable" requirements for a computation model to be equivalent in power to a Turing machine

12 votes
2 answers
2k views

Halting problem without self-reference

1 vote
1 answer
69 views

A decidable language that can't be decided by a circuit ensemble of linear size

Browse more Questions