user avatar
user avatar
user avatar
Ben
  • Member for 10 years, 5 months
  • Last seen more than a week ago
18 votes
Accepted

Infinite alphabet Turing Machine

12 votes

How do you check if two algorithms return the same result for any input?

11 votes
Accepted

Why isn't this undecidable problem in NP?

10 votes

Can a dynamic language like Ruby/Python reach C/C++ like performance?

9 votes

Can constraint satisfaction problems be solved with Prolog?

8 votes

Is interaction more powerful than algorithms?

8 votes

Proving the regularity of a certain language

7 votes

Can all languages have semantic and logical errors?

7 votes

What approaches are most useful when proving uncomputability of a given function?

5 votes
Accepted

What is the amount of programs for which we can solve the halting problem?

4 votes
Accepted

NP-complete reductions

4 votes

Length of mid part of the string in Pumping Lemma

4 votes

What is meant by interrupts in the context of operating systems?

3 votes
Accepted

Non-trivial tractable properties of triples

3 votes

What is the significance of context-sensitive (Type 1) languages?

3 votes
Accepted

A concrete example about string w and string x used in the proof of Rice's Theorem

3 votes

Length of the certificate in complexity classes

3 votes

Automatic Downcasting by Inferring the Type

3 votes

Are there problems in NP that do not reduce in polynomial time to any problem in NP?

2 votes

Undecidability of the following language

2 votes

Input to make worst case on big O not possible?

2 votes

Is there an undecidable finite language of finite words?

1 vote

Difference between reductions in algebraic problems versus reductions in computational intractability