user avatar
user avatar
user avatar
David Richerby
  • Member for 9 years
  • Last seen more than a month ago
  • UK
237 votes

Why is the unit of image size not Pixel²?

166 votes
Accepted

Is zero allowed as an edge's weight, in a weighted graph?

143 votes

Is a Turing Machine "by definition" the most powerful machine?

101 votes

Is von Neumann's randomness in sin quote no longer applicable?

100 votes

How can a language whose compiler is written in C ever be faster than C?

86 votes
Accepted

Why don't compilers automatically insert deallocations?

78 votes
Accepted

Order of growth definition from Reynolds & Tymann

76 votes
Accepted

Why is the Turing Machine a popular model of computation?

53 votes
Accepted

Huffman encoding: why is there no need for a separator?

51 votes
Accepted

Why do we believe that PSPACE ≠ EXPTIME?

49 votes

Can we generate random numbers using irrational numbers like π and e?

40 votes
Accepted

Does an Operating System inject its own machine code when you open a program?

40 votes

What exactly is a logic?

39 votes
Accepted

Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)

39 votes

What does being Turing complete mean?

38 votes

Simple (non-mathematical) definition of polynomial time?

36 votes
Accepted

How is the traveling salesman problem verifiable in polynomial time?

30 votes
Accepted

How to prove P$\neq$NP?

30 votes

What did Turing mean when saying that "machines cannot give rise to surprises" is due to a fallacy?

29 votes

Why does a Turing machine recognise exactly one language?

29 votes

Does a polynomial solution for an NP-complete problem that can only be implemented for small N *still* imply P=NP?

29 votes
Accepted

Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm?

28 votes
Accepted

Cardinality of the set of algorithms

25 votes
Accepted

Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive?

25 votes

Church-Turing Thesis and computational power of neural networks

24 votes
Accepted

How can I teach computer science without using computers?

24 votes
Accepted

What is an asymptotically tight upper bound?

24 votes
Accepted

Why is the blank symbol not considered part of the input alphabet of a Turing machine?

24 votes
Accepted

Are there any countable sets that are not computably enumerable?

24 votes
Accepted

Why is a (collision-less) hashtable lookup really O(1)?

1
2 3 4 5
51