Methods of Proof — Diagonalization


Very clear presentation on the uncountability of the real numbers, and the halting problem.

Originally posted on Math ∩ Programming:

A while back we featured a post about why learning mathematics can be hard for programmers, and I claimed a major issue was not understanding the basic methods of proof (the lingua franca between intuition and rigorous mathematics). I boiled these down to the “basic four,” direct implication, contrapositive, contradiction, and induction. But in mathematics there is an ever growing supply of proof methods. There are books written about the “probabilistic method,” and I recently went to a lecture where the “linear algebra method” was displayed. There has been recent talk of a “quantum method” for proving theorems unrelated to quantum mechanics, and many more.

So in continuing our series of methods of proof, we’ll move up to some of the more advanced methods of proof. And in keeping with the spirit of the series, we’ll spend most of our time discussing the structural form of the proofs…

View original 1,841 more words

Commuting to Work with an E-Bike

My current workplace in Frankfurt is 20 km from my home. In the past years I used the train to go there. Unfortunately the train became more and more unreliable. Sometimes the train had lots of delays, sometimes the train just didn’t arrive, sometimes the train was heavily crowded, often the information you receive during delays is wrong or misleading. Add to this the strike of the railway drivers, then you really question whether it is justified to pay ca. 130 EUR per month for the train. So in one year I pay roughly 1,500 EUR for public transport.

Continue reading

Speeding-Up Software Builds: Parallelizing Make and Compiler Cache

1. Problem statement

Compiling source code with a compiler usually employs the make command which keeps track of dependencies. Additionally GNU make can parallelize your build using the j-parameter. Often you also want a so called clean build, i.e., compile all source code files, just in case make missed some files when recompiling. Instead of deleting all previous effort one can use a cache of previous compilations.

I had two questions where I wanted quantitative answers:

  1. What is the best j for parallel make, i.e., how many parallel make’s should one fire?
  2. What effect does a compiler cache have?

Continue reading