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

1

vote

1

answer

14

views

How to prove that the reduction relation is not symmetric

complexity-theory computability reductions

answered yesterday Yuval Filmus 252k

0

votes

2

answers

206

views

Why is there no “traditional”-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm?

algorithms computability recursion loops iteration

answered May 12 at 18:46 jmite 28.5k

0

votes

1

answer

80

views

A question on decidability

computability undecidability decision-problem rice-theorem

modified May 11 at 12:35 standrewsstudent 1

50

votes

14

answers

15k

views

Is C actually Turing-complete?

computability turing-completeness c

modified May 7 at 22:58 polcott 159

0

votes

1

answer

13

views

SAT and Polytime Reductions

complexity-theory computability

modified May 6 at 17:57 Inuyasha Yagami 1,437

0

votes

0

answers

22

views

Karp's reduction strategy

complexity-theory computability

asked May 6 at 14:40 user3300185 1

0

votes

0

answers

19

views

Algorithmically find a formal grammar for a recursively enumerable formal language

formal-languages computability formal-grammars

asked May 4 at 20:54 omd2 1

3

votes

1

answer

136

views

Is there a formal way of defining a Zeno Machine?

turing-machines computability hypercomputation

modified May 1 at 23:55 Sriotchilism O'Zaic 321

-2

votes

0

answers

43

views

Can $A_{TM}$ be mapping reduced to an unrecognizable language?

turing-machines computability finite-automata undecidability halting-problem

modified May 1 at 5:50 D.W.♦ 131k

169

votes

13

answers

56k

views

Why, really, is the Halting Problem so important?

computability halting-problem

modified Apr 28 at 23:54 jmoreno 291

0

votes

1

answer

41

views

IS SUBSET-SUM in P if b(the sum) is given in unary and a1,…,an is in binary?

complexity-theory computability np decision-problem polynomial-time

answered Apr 27 at 17:50 yosho27 1

0

votes

1

answer

148

views

Undecidability of the language of PDAs that accept some ww

computability undecidability

modified Apr 26 at 0:07 Community♦ 1

1

vote

4

answers

2k

views

Existence of non-context free but decidable languages

formal-languages computability

answered Apr 25 at 10:49 Arno 1,524

0

votes

1

answer

96

views

Could the empty language be NP-Complete?

complexity-theory computability np-complete

modified Apr 23 at 17:21 nir shahar 4,433

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled