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

2

votes

1

answer

30

views

How should we interpret a transition rule $\epsilon,b\to c$ in a Pushdown Automata as Sipser defined in his book?

computability pushdown-automata

modified 2 days ago AmHsnSharafi 23

80

votes

6

answers

13k

views

Is there any concrete relation between Gödel's incompleteness theorem, the halting problem and universal Turing machines?

computability logic halting-problem incompleteness

modified Mar 27 at 21:06 Julius Kunze 121

0

votes

0

answers

21

views

Is this a computable function? Is the reduction correct?

computability

asked Mar 27 at 11:57 Linpeng Zhang 1

1

vote

1

answer

47

views

Use 2SAT to show that an implication graphs must have a cycle if it's not satisfiable

graphs computability satisfiability 2-sat

modified Mar 22 at 16:17 Yuval Filmus 220k

1

vote

3

answers

47

views

NP-complete problem 3-SAT, is there a difference in complexity between just providing yes/no without exact solution

complexity-theory time-complexity computability np-complete p-vs-np

modified Mar 19 at 10:51 vonbrand 11k

3

votes

2

answers

234

views

show that in every infinite computably enumerable set, there exists an infinite decidable set

turing-machines computability undecidability

modified Mar 19 at 3:03 vonbrand 11k

0

votes

1

answer

27

views

simple question about epsilon and estimation turing machines

complexity-theory turing-machines computability optimization

modified Mar 18 at 15:00 Community♦ 1

0

votes

0

answers

26

views

Improving binary recursion calculation

computability

modified Mar 18 at 7:22 shanylong 101

0

votes

1

answer

46

views

How can i solve a recursion equation with square root using recursion tree method?

algorithms data-structures computability recurrence-relation

modified Mar 16 at 2:01 Community♦ 1

0

votes

1

answer

65

views

show that this decidable set $C$ exists

turing-machines computability undecidability

modified Mar 14 at 1:34 Link L 309

41

votes

9

answers

12k

views

Is C actually Turing-complete?

computability turing-completeness c

modified Mar 12 at 23:20 polcott 99

3

votes

1

answer

256

views

What does the exact $\mu$-recursive program for minimization look like?

computability primitive-recursion mu-recursion

modified Mar 12 at 19:06 Community♦ 1

2

votes

1

answer

1k

views

Proof of decidability of determining whether a DFA accepts a string

turing-machines computability finite-automata

modified Mar 10 at 15:58 xskxzr 6,140

2

votes

1

answer

47

views

Concise Way To Specify The Space Of All Python Programs Under A Certain Size And Running Time?

computability enumeration

modified Mar 9 at 6:29 Raphael♦ 67.4k

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled