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

more tags

Active 4 Bountied Hot Week Month

5

votes

3

answers

137

views

Is there any other computation theory besides the one in automata theory?

complexity-theory formal-languages computability formal-grammars computation-models

modified yesterday Yos 11

0

votes

0

answers

30

views

Restriction: polynomial time decision of instance is why needed to “decision Problem”?

complexity-theory computability decision-problem

asked yesterday y y 1

0

votes

1

answer

25

views

On the computable function of a problem that halts

turing-machines computability halting-problem

modified yesterday Community♦ 1

0

votes

0

answers

10

views

Proving the existence of a $\Pi_1$-sentence in True Arithmetic that is independent of Peano Arithmetic

computability logic

asked Nov 28 at 19:56 Ziyad Edher 157

4

votes

1

answer

59

views

Is there a model of ZF¬C where some program always terminates but has no loop variant?

computability logic loop-invariants termination

modified Nov 27 at 19:31 cody 7,236

1

vote

2

answers

39

views

Why can't we prove decidability of $L= \{ \langle M \rangle : M$ accepts $ \epsilon \}$ with a configurations graph?

turing-machines computability undecidability

modified Nov 27 at 15:53 Aaron Rotenberg 480

5

votes

0

answers

39

views

Analogue of the topology-computability correspondence for computational complexity

complexity-theory turing-machines computability semantics topology

asked Nov 25 at 22:11 helianthus 51

6

votes

3

answers

882

views

How many decidable decision problems are there?

computability decision-problem

modified Nov 25 at 6:29 pkwssis 175

-1

votes

0

answers

12

views

Recursive definition character counter

computability recurrence-relation discrete-mathematics correctness-proof

asked Nov 23 at 16:46 Scb 1

46

votes

4

answers

8k

views

Why can humans solve certain “undecidable” problems?

computability philosophy computer-vs-human

answered Nov 19 at 20:03 gnasher729 16k

0

votes

1

answer

78

views

Modified Linear Bounded Automata Language

computability automata computation-models linear-bounded-automata

answered Nov 18 at 15:32 sayan chandra 11

1

vote

1

answer

25

views

Reductions from non decision problems

complexity-theory computability np-complete reductions approximation

answered Nov 17 at 7:29 D.W.♦ 112k

1

vote

0

answers

22

views

Turing machine that can read and write simultaneously equivalence proof

computability

asked Nov 13 at 17:11 computersciencenewbie 11

2

votes

1

answer

59

views

How undecidable is it whether a given Turing machine runs in polynomial time?

computability undecidability polynomial-time

answered Nov 12 at 17:33 Noah Schweber 1,144

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled