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

1

vote

1

answer

121

views

A computable language with a non-computable language that is prefix-free

formal-languages computability

modified 22 hours ago Addem 227

0

votes

1

answer

759

views

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

turing-machines computability undecidability

modified 2 days ago CommunityBot 1

0

votes

0

answers

14

views

Is it possible to build a linear bound automata that decides A(NFA)?

complexity-theory turing-machines computability

modified Oct 22 at 15:26 Niv 113

0

votes

1

answer

43

views

How to prove that this language is not recursive enumerable?

turing-machines computability recursion

modified Oct 20 at 16:04 CommunityBot 1

0

votes

1

answer

31

views

How to prove that $L_{D}\leq L_{U}$?

computability reductions

modified Oct 19 at 0:14 CommunityBot 1

0

votes

1

answer

14

views

complement of concatenate languages equal to complements concatenated?

formal-languages computability

answered Oct 17 at 16:28 rici 10.2k

0

votes

1

answer

41

views

Reduction of RE and Rec languages

complexity-theory turing-machines computability reductions polynomial-time-reductions

answered Oct 17 at 13:48 Steven 19.5k

52

votes

14

answers

16k

views

Is C actually Turing-complete?

computability turing-completeness c

modified Oct 17 at 5:54 user3840170 111

0

votes

1

answer

51

views

Reduction of Turing-machine language

turing-machines computability undecidability semi-decidability

modified Oct 16 at 23:00 CommunityBot 1

-1

votes

1

answer

30

views

Does Turing machine move left on particular input?

turing-machines computability undecidability decidability

modified Oct 16 at 17:21 nir shahar 9,317

0

votes

1

answer

37

views

Difference between Counter-machine and stack machine

formal-languages computability automata context-free pushdown-automata

answered Oct 15 at 17:41 rici 10.2k

0

votes

1

answer

37

views

Karp's reduction strategy

complexity-theory computability np-complete np

modified Oct 14 at 8:04 CommunityBot 1

0

votes

1

answer

39

views

How to prove that the set of recursive primitive functions is closed under

computability primitive-recursion

modified Oct 13 at 15:24 Andrej Bauer 27.2k

0

votes

0

answers

11

views

Need literature on First order logic definibility through Automata

complexity-theory computability automata finite-automata computation-models

asked Oct 13 at 6:11 Soumyajit Pyne 1

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled