# Tag Info

## Hot answers tagged correctness-proof

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 ...
• 270k
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 ...
• 1,074
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 ...
• 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 ...
• 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." (...
• 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 ...
• 3,107
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 ...
• 270k
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 ...
• 694
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 ...
• 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. ...
• 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 ...
• 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 ...
• 760
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 ...
• 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,...
• 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 ...
• 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 ...
• 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 ...
• 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 ...
• 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. ...
• 481
14 votes

### How to prove greedy algorithm is correct

I will use the following simple sorting algorithm as an example: ...
• 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 ...
• 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 ...
• 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 ...
• 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 ...
• 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 ...
• 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 ...
• 210
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 ...
• 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 ...
• 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 ...
• 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.
• 27.6k

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