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

0

votes

1

answer

21

views

Are models of computation closed under composition?

formal-languages computability closure-properties

answered 18 hours ago Tom van der Zanden 9,533

0

votes

0

answers

10

views

How to apply the recursion theorem for this problem?

computability recursion

asked yesterday user700016 1

37

votes

4

answers

8k

views

Theoretical machines which are more powerful than Turing machines

computability turing-machines hypercomputation

modified Sep 17 at 18:40 Thomas Klimpel 3,968

0

votes

1

answer

16

views

Busy-Beaver-like question for WHILE-Programs (Theoretical CS)

computability halting-problem busy-beaver

answered Sep 15 at 20:06 Edmundo Del Gusto 18

3

votes

1

answer

68

views

Problem in downvote system

algorithms computability combinatorics

modified Sep 14 at 9:02 Community♦ 1

2

votes

1

answer

71

views

How strong is an oracle that avoid don't-halt

turing-machines computability oracle-machines

modified Sep 8 at 17:08 Noah Schweber 778

1

vote

1

answer

20

views

Expressing partial decidability using existential quantification

computability

modified Sep 8 at 14:44 Yuval Filmus 208k

3

votes

2

answers

6k

views

Is every subset of a decidable set, also decidable?

computability undecidability closure-properties sets

answered Sep 4 at 4:19 Yu Gu 111

1

vote

1

answer

40

views

What Is the Complexity Class of Deciding Whether a Problem Is in NP? Is It Decidable?

complexity-theory computability

modified Sep 3 at 18:29 Gavin Howard 108

0

votes

0

answers

26

views

What does B compute in Recursion theorem

computability

asked Aug 31 at 18:14 sachal 15

1

vote

1

answer

24

views

Does Types and Programming Languages use a recursive equation to define a recursive type or its generator?

computability programming-languages type-theory

modified Aug 30 at 19:31 jmite 23.8k

2

votes

1

answer

77

views

PCAs and Kleene's Recursion Theorem

computability

modified Aug 28 at 0:22 sdcvvc 2,540

1

vote

1

answer

12

views

Doubt in definition of closure under concatenation operation in Recursive Enumerative languages

turing-machines computability

modified Aug 25 at 21:30 Nascimento de Cos 27

0

votes

0

answers

28

views

A condition for $\emptyset \neq S\subset RE$ under which $L_S \notin RE$

turing-machines computability reference-request

modified Aug 22 at 7:37 dkaeae 4,535

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled