Explore our questions

8 votes
3 answers
9k views

Show that it is undecidable if two Turing Machines accept the same language

0 votes
1 answer
76 views

Decidability of whether a Turing machine accepts all even-length words

2 votes
0 answers
45 views

Can remainder mod 2 be efficiently computed from addition and equality?

3 votes
1 answer
590 views

Can the minimisation operation be seen from a programming language perspective?

5 votes
1 answer
319 views

Is every non-recursively-enumerable language RE-hard?

1 vote
1 answer
55 views

Why is $RP \subseteq BPP$?

-2 votes
2 answers
68 views

Is there a well-defined bijection between an undecidable language and the set of natural numbers?

6 votes
1 answer
1k views

Where am I wrong?: "countability" and "recursive enumerability"

-1 votes
0 answers
19 views

Recognizability of PFTM

3 votes
1 answer
42 views

Are Primitive recursive functions (with bounded $\mu$ operator) equivalent to other known computational model?

0 votes
1 answer
322 views

Can a PDA guess more than once? L = {aⁿ bⁱ aⁿ | i,n > 0 }

5 votes
1 answer
145 views

Self referential hash function possible?

0 votes
1 answer
86 views

Mapping Reduction from HALT?

4 votes
1 answer
697 views

Are there infinite state machines, and how do their computational power relate to turing machines?

Browse more Questions