David Richerby's user avatar
David Richerby's user avatar
David Richerby's user avatar
David Richerby
  • Member for 10 years, 7 months
  • Last seen more than 2 years ago
  • UK
239 votes

Why is the unit of image size not Pixel²?

165 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?

101 votes

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

87 votes
Accepted

Why don't compilers automatically insert deallocations?

78 votes
Accepted

Order of growth definition from Reynolds & Tymann

77 votes
Accepted

Why is the Turing Machine a popular model of computation?

54 votes
Accepted

Why do we believe that PSPACE ≠ EXPTIME?

53 votes
Accepted

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

49 votes

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

40 votes
Accepted

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

40 votes

What exactly is a logic?

39 votes

What does being Turing complete mean?

39 votes
Accepted

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

37 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

Why does a Turing machine recognise exactly one language?

30 votes

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

29 votes
Accepted

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

29 votes

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

28 votes
Accepted

Cardinality of the set of algorithms

26 votes
Accepted

Are there any countable sets that are not computably enumerable?

25 votes
Accepted

Does space complexity analysis usually include output space?

25 votes

Church-Turing Thesis and computational power of neural networks

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
Accepted

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

24 votes
Accepted

Why aren't P and P/poly trivially the same?

24 votes
Accepted

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

1
2 3 4 5
51