Yuval Filmus
  • Member for 9 years, 10 months
  • Last seen this week
Why is writing down mathematical proofs more fault-proof than writing computer code?
243 votes

Let me offer one reason and one misconception as an answer to your question. The main reason that it is easier to write (seemingly) correct mathematical proofs is that they are written at a very high ...

View answer
Keeping a String Secret in (Open) Source Code
Accepted answer
85 votes

You have at least two options, depending on what problem you want to solve. If you want innocent readers of your code to not get the answers inadvertently, or you at least want to make it a bit ...

View answer
Can a computer determine whether a mathematical statement is true or not?
Accepted answer
77 votes

The claim is not that a computer cannot determine the validity of some mathematical statements. Rather, the claim is that there is a class $\mathcal{C}$ of mathematical statements such that no ...

View answer
Does $\mathsf{P} \ne \mathsf{NP}$ imply that $|\mathsf{NP}| > |\mathsf{P}|$?
76 votes

It is known that P$\subseteq$NP$\subset$R, where R is the set of recursive languages. Since R is countable and P is infinite (e.g. the languages $\{n\}$ for $n \in \mathbb{N}$ are in P), we get that P ...

View answer
Boolean search explained
Accepted answer
63 votes

Hint: The search x AND y will result in 10 000 hits.

View answer
Why is the Turing Machine a popular model of computation?
58 votes

You are asking several different questions. Let me briefly answer them one by one. What is so important about the Turing machine model? During the infancy of computability theory, several models of ...

View answer
Why are ambiguous grammars bad?
Accepted answer
56 votes

Consider the following grammar for arithmetic expressions: $$ X \to X + X \mid X - X \mid X * X \mid X / X \mid \texttt{var} \mid \texttt{const} $$ Consider the following expression: $$ a - b - c $$ ...

View answer
Minimum spanning tree vs Shortest path
55 votes

Consider the triangle graph with unit weights - it has three vertices $x,y,z$, and all three edges $\{x,y\},\{x,z\},\{y,z\}$ have weight $1$. The shortest path between any two vertices is the direct ...

View answer
Time complexity of an algorithm: Is it important to state the base of the logarithm?
50 votes

Because asymptotic notation is oblivious of constant factors, and any two logarithms differ by a constant factor, the base makes no difference: $\log_a n = \Theta(\log_b n)$ for all $a,b > 1$. So ...

View answer
Example of an algorithm that lacks a proof of correctness
50 votes

Here is an algorithm for the identity function: Input: $n$ Check if the $n$th binary string encodes a proof of $0 > 1$ in ZFC, and if so, output $n+1$ Otherwise, output $n$ Most people suspect ...

View answer
Why is $A \lor (A \land \neg B) \equiv A$?
48 votes

There are many ways to see this. One is a truth table. Another is to use the distributive rule: $$ A \lor (A \land \lnot B) = (A \land \top) \lor (A \land \lnot B) = A \land (\top \lor \lnot B) = A \...

View answer
Why is SAT so important in theoretical computer science?
Accepted answer
46 votes

SAT was the first problem shown to be NP-complete, in Stephen Cook's seminal paper. Even nowadays, when introducing the theory of NP-completeness, the starting point is usually the NP-completeness of ...

View answer
Quantum Computing and Turing Machines: Are Turing Machines still an Accurate Measure?
Accepted answer
44 votes

You're mixing up computability theory (also known as recursion theory) and complexity theory (or computational complexity). Computability theory is a vast mathematical subject which studies the ...

View answer
What exactly is polynomial time?
Accepted answer
43 votes

An algorithm is polynomial (has polynomial running time) if for some $k,C>0$, its running time on inputs of size $n$ is at most $Cn^k$. Equivalently, an algorithm is polynomial if for some $k>0$,...

View answer
Simple (non-mathematical) definition of polynomial time?
41 votes

Polynomial time algorithms are algorithms whose running time increases by a constant factor when the input is doubled in size. Exponential time algorithms are algorithms whose running time increases ...

View answer
How does a computer determine the data type of a byte?
Accepted answer
41 votes

Your suspicion is correct. The CPU doesn't care about the semantics of your data. Sometimes, though, it does make a difference. For example, some arithmetic operations produce different results when ...

View answer
Would the P vs. NP problem become trivial as a result of the development of universal quantum computers?
40 votes

No, there will be absolutely no implication, for several reasons: The P vs. NP problem is about classical computation rather than quantum computation. Even if quantum computers could solve NP-hard ...

View answer
Can Quantum Computing solve Problems not even a Turing Machine can solve?
40 votes

While it is true that the computation of a quantum Turing machine is vastly different from that of a classical one, nevertheless quantum Turing machines can be simulated on a classical Turing machine, ...

View answer
Are all pseudo-random number generators ultimately periodic?
39 votes

All pseudorandom generators that don't rely on outside randomness and use a bounded amount of memory are necessarily ultimately periodic since they have finite state. You can think of them as huge ...

View answer
What is the definition of Computer Science, and what is the Science within Computer Science?
Accepted answer
39 votes

Computer science is a misnomer - there is actually no "science" in computer science, since computer science is not about observing nature. Rather, parts of computer science are engineering, and parts ...

View answer
How can a computer deal with real numbers
Accepted answer
37 votes

Sage is an open source computer algebra system. Let's see if it can handle your basic example: sage: sqrt(3) * (4/sqrt(3) - sqrt(3)) 1 What is happening under the hood? Sage is storing everything as ...

View answer
Are there any functions with Big O (Busy Beaver(n))?
Accepted answer
36 votes

The usual meaning of algorithm is a program that always halts. Under this definition, no algorithm has a running time of $\Theta(\mathit{BB}(n))$, or indeed $\Omega(\mathit{BB}(n))$. Indeed, such an ...

View answer
Are algorithms (and efficiency in general) getting less important?
36 votes

On the contrary. At the same time that hardware is getting cheaper, several other developments take place. First, the amount of data to be processed is growing exponentially. This has led to the ...

View answer
Planar regular languages
Accepted answer
35 votes

It isn't true that every DFA for this language is non-planar: Here is a language that is truly non-planar: $$ \left\{ x \in \{\sigma_1,\ldots,\sigma_6\}^* \middle| \sum_{i=1}^6 i\#_{\sigma_i}(x) \...

View answer
Can the sorting of a list be verified without comparing neighbors?
Accepted answer
35 votes

It is impossible. Suppose that you have the result of all comparisons except for the pair $(i,i+1)$. Then you wouldn't be able to distinguish between the following two cases: $$ 1,2,\ldots,i-1,i,i+1,i+...

View answer
Is there a known maximum for how much a string of 0's and 1's can be compressed?
35 votes

For any given string there is a compression scheme that compresses it to the empty string. Hence it is not meaningful to ask how much a single string can be compressed, but rather how much a ...

View answer
"Dense" regular expressions generate $\Sigma^*$?
Accepted answer
35 votes

Your conjecture is disproved by Keith Ellul, Bryan Krawetz, Jeffrey Shallit and Ming-wei Wang in their paper "Regular Expressions: New Results and Open Problems". While the paper is not available on-...

View answer
Is busy beaver the fastest growing function known to man?
35 votes

There is no such thing as "the fastest growing function". In fact, there is even no sequence of fastest growing functions. This was already shown by Hausdorff. Given two functions $f,g\colon \mathbb{N}...

View answer
Iteration can replace Recursion?
34 votes

Every recursion can be converted to iteration, as witnessed by your CPU, which executes arbitrary programs using a fetch-execute infinite iteration. This is a form of the Böhm-Jacopini theorem. ...

View answer
What would be the real-world implications of a constructive $P=NP$ proof?
32 votes

We won't necessarily see any effects. Suppose that somebody finds an algorithm that solves 3SAT on $n$ variables in $2^{100} n$ basic operations. You won't be able to run this algorithm on any ...

View answer
1
2 3 4 5
226