# Tag Info

### 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 ...
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 ...

### 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 ...

### 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 ...

### 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." (...

### 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 ...

### 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 ...

### 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 ...

### 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 ...

### 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. ...

### 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 ...

### 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 ...

### 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 ...

### 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,...

### 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 ...

### 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 ...
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 ...

### 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 ...

### 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. ...

### How to prove greedy algorithm is correct

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

### 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 ...

### 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 ...
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 ...

### 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 ...

### 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 ...

### 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 ...