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 2 Bountied Hot Week Month

0

votes

0

answers

12

views

AMBIG_NFA decidability problem

computability

modified 18 hours ago Macrophage 101

2

votes

2

answers

124

views

how does Kleene-Post show two languages that are not Turing reducible to each other?

turing-machines computability reductions undecidability oracle-machines

modified yesterday xdavidliu 590

0

votes

0

answers

40

views

Is this set Recursive or Recursively Enumerable?

computability undecidability sets

modified 2 days ago Hybrid_Thinker 1

-1

votes

0

answers

33

views

How can we tell a busy beaver candidate can halt?

computability

asked Nov 23 at 8:10 user1792389 1

164

votes

12

answers

54k

views

Why, really, is the Halting Problem so important?

computability halting-problem

modified Nov 21 at 20:21 D.W.♦ 126k

-3

votes

0

answers

18

views

finitely many distinct partially n-computable unary functions

computability

asked Nov 21 at 14:04 dr.knowNothing 1

-1

votes

1

answer

15

views

Use the diagonal method to prove that there is a total function from N to N which is not computable

computability

answered Nov 19 at 7:59 kutschkem 266

4

votes

1

answer

98

views

What does it mean for something to be $\prod_x^y$-complete or $\sum_x^y$-complete?

complexity-theory recursion-theory

modified Nov 17 at 21:59 TeamBright 443

61

votes

11

answers

11k

views

Human computing power: Can humans decide the halting problem on Turing Machines?

computability turing-machines halting-problem human-computing

answered Nov 17 at 17:59 Mr. Minty Fresh 572

0

votes

0

answers

30

views

Prove that $A \oplus B$ is recursive if $A$ and $B$ are recursive

computability

asked Nov 17 at 2:16 Anh Vo Nguyen Nhat 3

-2

votes

0

answers

12

views

Turing Machine Encoding Legth

complexity-theory turing-machines computability

asked Nov 14 at 12:32 Novice_researcher 11

1

vote

1

answer

29

views

All total functions form a PRC class

computability

modified Nov 14 at 10:37 Thom Fifield 1

0

votes

1

answer

36

views

simple question about epsilon and estimation turing machines

complexity-theory turing-machines computability optimization

modified Nov 13 at 16:02 Community♦ 1

-1

votes

0

answers

27

views

How to generally solve a graph problem with closed semiring?

algorithms graphs data-structures computability

asked Nov 12 at 6:31 J Kim 23

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled