246 votes

Why is writing down mathematical proofs more fault-proof than writing computer code?

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 ...
user avatar
91 votes
Accepted

How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

A common error I think is to use greedy algorithms, which is not always the correct approach, but might work in most test cases. Example: Coin denominations, $d_1,\dots,d_k$ and a number $n$, express ...
user avatar
86 votes

Why is writing down mathematical proofs more fault-proof than writing computer code?

(I am probably risking a few downvotes here, as I have no time/interest to make this a proper answer, but I find the text quoted (and the rest of the article cited) below to be quite insightful, also ...
user avatar
  • 1,116
73 votes

How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

I immediately recalled an example from R. Backhouse (this might have been in one of his books). Apparently, he had assigned a programming assignment where the students had to write a Pascal program to ...
user avatar
  • 22.1k
62 votes

Why is writing down mathematical proofs more fault-proof than writing computer code?

Allow me to start by quoting E. W. Dijkstra: "Programming is one of the most difficult branches of applied mathematics; the poorer mathematicians had better remain pure mathematicians." (...
user avatar
  • 6,978
53 votes

Why is writing down mathematical proofs more fault-proof than writing computer code?

Lamport provides some ground for disagreement on prevalence of errors in proofs in How to write a proof (pages 8-9): Some twenty years ago, I decided to write a proof of the Schroeder-Bernstein ...
user avatar
50 votes

Example of an algorithm that lacks a proof of correctness

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 ...
user avatar
42 votes

Why is writing down mathematical proofs more fault-proof than writing computer code?

One big difference is that programs typically are written to operate on inputs, whereas mathematical proofs generally start from a set of axioms and prior-known theorems. Sometimes you have to cover ...
user avatar
36 votes

How to prove greedy algorithm is correct

Ultimately, you'll need a mathematical proof of correctness. I'll get to some proof techniques for that below, but first, before diving into that, let me save you some time: before you look for a ...
user avatar
  • 141k
34 votes

How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

The best example I ever came across is primality testing: input: natural number p, p != 2 output: is p a prime or not? algorithm: compute 2**(p-1) mod p. If result = 1 then p is prime else p is not. ...
user avatar
  • 349
29 votes

Why is writing down mathematical proofs more fault-proof than writing computer code?

They say the problem with computers is that they do exactly what you tell them. I think this might be one of the many reasons. Notice that, with a computer program, the writer (you) is smart but the ...
user avatar
  • 1,177
25 votes

How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

Here's one that was thrown at me by google reps at a convention I went to. It was coded in C, but it works in other languages that use references. Sorry for having to code on [cs.se], but it's the ...
user avatar
25 votes

Why is writing down mathematical proofs more fault-proof than writing computer code?

One issue that I think was not addressed in Yuval's answer, is that it seems you are comparing different animals. Saying "the code is correct" is a semantic statement, you mean to say that the object ...
user avatar
  • 13.2k
23 votes

Are there programs that never halt and have no non-termination proof?

There are indeed programs like this. To prove this, let's suppose to the contrary that for every machine that doesn't halt, there is a proof it doesn't halt. These proofs are strings of finite length,...
user avatar
  • 29.1k
20 votes

How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

There is a whole class of algorithms that is inherently hard to test: pseudo-random number generators. You can not test a single output but have to investigate (many) series of outputs with means of ...
user avatar
  • 70.9k
20 votes

Why is writing down mathematical proofs more fault-proof than writing computer code?

What is so different about writing faultless mathematical proofs and writing faultless computer code that makes it so that the former is so much more tractable than the latter? I believe that the ...
user avatar
  • 301
16 votes
Accepted

Can I use the following method to prove an algorithm is correct?

I am rather surprised that you raised this question since the meticulous and enlightening answers you have written to some math questions demonstrate sufficiently that you are capable of rigorous ...
user avatar
  • 34.1k
15 votes

What are the flaws in this encryption algorithm?

This is not a secure encryption scheme. It is similar to a Hill cipher, and vulnerable to similar attacks. For instance, it is vulnerable to known-plaintext attacks: an attacker who observes a ...
user avatar
  • 141k
14 votes

How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

2D local maximum input: 2-dimensional $n \times n$ array $A$ output: a local maximum -- a pair $(i,j)$ such that $A[i,j]$ has no neighboring cell in the array that contains a strictly larger value. ...
user avatar
14 votes

How to prove greedy algorithm is correct

I will use the following simple sorting algorithm as an example: ...
user avatar
  • 5,900
14 votes
Accepted

Trying to understand this Quicksort Correctness proof

We are indeed assuming $P(k)$ holds for all $k < n$. This is a generalization of the "From $P(n-1)$, we prove $P(n)$" style of proof you're familiar with. The proof you describe is known as the ...
user avatar
  • 14.6k
12 votes
Accepted

Why does this sort algorithm work?

It is a variant of bubble sort, however the endpoints of the array shift throughout the progress of the algorithm. In particular it maintains the following invariant: at the end of the $i$-th ...
user avatar
  • 20.4k
12 votes

Why is writing down mathematical proofs more fault-proof than writing computer code?

I agree with what Yuval has written. But also have a much simpler answer: In practice softwares engineers typically don't even try to check for correctness of their programs, they simply don't, they ...
user avatar
  • 21.7k
12 votes

Why is writing down mathematical proofs more fault-proof than writing computer code?

There are a lot of good answers already but there are still more reasons math and programming aren't the same. 1 Mathematical proofs tend to be much simpler than computer programs. Consider the first ...
user avatar
  • 221
11 votes
Accepted

Proof of correctness of algorithm to determine whether the elements of an array are repeated an equal number of times

No, your algorithm doesn't work. Consider if the array A is A = [1 1 1 1 1 2 2 3 3 3 3 3 3]. Then the array B will be B = [5 5 5 5 5 2 2 6 6 6 6 6 6]. The sum of B will be 65, and the length of B ...
user avatar
  • 141k
11 votes

Why is writing down mathematical proofs more fault-proof than writing computer code?

I like Yuval's answer, but I wanted to riff off of it for a bit. One reason you might find it easier to write Math proofs might boil down to how platonic Math ontology is. To see what I mean, consider ...
user avatar
10 votes

How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

Fisher-Yates-Knuth shuffling algorithm is an (practical) example and one on which one of the the authors of this site has commented about. The algorithm generates a random permutation of a given ...
user avatar
  • 929
10 votes

How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

These are primality examples, because they're common. (1) Primality in SymPy. Issue 1789. There was an incorrect test put on a well-known web site that didn't fail until after 10^14. While the fix ...
user avatar
  • 574
10 votes

Proof of an Optimal substructure in Dynammic Programming?

There is no (one) formal definition of "optimal substructure" (or the Bellman optimality criterion) so you can not possibly hope to (formally) prove you have it. You should do the following: Set up ...
user avatar
  • 70.9k
10 votes

Why do these recurrences determine the number of ways of tiling a 3xN rectangle with 2x1 dominoes?

The picture should say more than words.
user avatar
  • 27.6k

Only top scored, non community-wiki answers of a minimum length are eligible