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

Ask Question

more tags

Active Hot Week Month

1

vote

1

answer

37

views

Prove a language is not recursive enumerable

turing-machines computability rice-theorem

modified 4 hours ago Community♦ 1

0

votes

2

answers

26

views

Can the intersection two non-recursive sets be recursive? Prove it

turing-machines computability

answered 21 hours ago Dmitry 1,287

0

votes

1

answer

170

views

Create a Turing-machine that decides $A=\{0^{3^n} | n\ge 0\}$

turing-machines computability

modified 21 hours ago Community♦ 1

9

votes

2

answers

10k

views

Why are CFLs not closed under intersection?

formal-languages computability context-free

modified 2 days ago John L. 24.8k

1

vote

1

answer

509

views

How to convert regular expression to CFG?

computability context-free

modified Feb 28 at 22:03 Community♦ 1

0

votes

1

answer

35

views

Vertex cover of minimal graph

complexity-theory graphs computability vertex-cover

answered Feb 25 at 23:38 Steven 13.1k

0

votes

1

answer

449

views

A language which is neither r.e. nor co-r.e

turing-machines computability undecidability

modified Feb 25 at 14:01 Community♦ 1

-2

votes

0

answers

44

views

$\forall A\notin RE$ prove that $L_A =\{\langle M\rangle : |A\cap L(M)|\ge10 \}\notin RE $

complexity-theory formal-languages computability reductions

modified Feb 24 at 21:38 ChaosPredictor 341

42

votes

11

answers

9k

views

Can a computer determine whether a mathematical statement is true or not?

complexity-theory computability

modified Feb 24 at 11:04 Clive Tooth 3

-1

votes

1

answer

63

views

For every Non Deterministic polynomial Turing Machine $M$ exists $L(\overline{M})\in P \Leftrightarrow P=NP$

complexity-theory formal-languages turing-machines computability

modified Feb 22 at 13:46 nir shahar 2,071

1

vote

4

answers

105

views

If $A$ reduces to $B$ and $B$ is NP-hard, is $A$ NP-hard?

algorithms complexity-theory turing-machines computability np-complete

answered Feb 21 at 22:57 gnasher729 21.6k

0

votes

1

answer

23

views

Is there a non-deterministic polynomial by time Turing machine such that: $L(M)\in NPC$ and $L(\overline{M})\in P$

complexity-theory formal-languages turing-machines computability

answered Feb 21 at 21:09 Nathaniel 675

1

vote

1

answer

69

views

Why is $\forall x \in \mathbb{N}\ \Phi(x,x)$ unary but $\Phi$ is binary?

computability

modified Feb 21 at 14:26 Andrej Bauer 26.5k

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled