## Basics: Binary Search

For the basics, I wrote a bunch of stuff about sorting. It seems worth taking a moment
to talk about something related: binary search. Binary search is one of the most important
and fundamental algorithms, and it shows up in sorts of places.

It also has the amazing property that despite being simple and ubiquitous, it's virtually
always written wrong. There's a bit of subtlety in implementing it correctly, and virtually
everyone manages to put off-by-one indexing errors into their implementations. (Including me; last time I implemented a binary search, the first version included one of the classic errors.) The errors are so ubiquitous that even in a textbook that discusses the fact that most programmers get it wrong, they got it wrong in their example code!

## Basics: Parallel, Concurrent, and Distributed

This came up in a question in the post where I started to talk about π-calculus, but I thought it was an interesting enough topic to promote it up to a top-level post. If you listen to anyone talking about computers or software, there are three worlds you'll constantly hear: parallel, concurrent, and distributed. At first glance, it sounds like they mean the same thing, but in fact, they're three different things, and the differences are important.

## Basics: Tautology (with a free bonus rant!)

Today's bit of basics is inspired by that bastion of shitheaded ignorance, Dr. Michael Egnor. In part of his latest screed (a podcast with Casey Luskin of the Discovery Institute), Egnor discusses antibiotic resistance, and along the way, asserts that the theory of evolution has no relevance to antibiotic resistance, because what evolution says about the subject is just
a tautology. (I'm deliberately not linking to the podcast; I will not help increase the hit-count that DI will use to promote it's agenda of willful ignorance.)

So what is a tautology?

A tautology is a logical statement which is universally true, by nature of its fundamental structure. That is, even without knowing anything about what the statement means,
you can infer that it must be true.

## Theories, Theorems, Lemmas, and Corollaries

I've been getting so many requests for "basics" posts that I'm having trouble keeping up! There are so many basic things in math that non-mathematicians are confused about. I'm doing my best to keep up: if you've requested a "basics" topic and I haven't gotten around to it, rest assured, I'm doing my best, and I will get to it eventually!

One of the things that multiple people have written to be about is confusion about what a mathematician means by a theory; and what the difference is between a theory and a theorem?

## Basics: Modal Logic

I've received a request from a long-time reader to write a basics post on modal logics. In particular, what is a modal logic, and why did Gödel believe that a proof for the existence of God was more compelling in modal logic than in standard predicate logic.

The first part is the easy one. Modal logics are logics that assign values to statements that go beyond "This statement is true" or "This statement is false". Modal logics add the concepts of possibility and necessity. Modal logic allows statements like "It is necessary for X to be true", "It is possible for X to be true", etc.

## Basics: Going Meta

In math and computer science, we have a tendency to talk about "going meta". It's actually a
pretty simple idea, which tends to crop up in other places, as well. It's also one of my favorite concepts - the idea of going meta is just plain cool. (Not to mention useful. There's a running joke among computer scientists that the solution to any problem is to add a level of indirection - which is programmer-speak for going meta on constructs inside of a programming language. Object-orientation is, in some sense, just an example of how to go meta on procedures. Haskell type-classes are an example of going meta on types.)

## Basics: Axioms

Today's basics topic was suggested to me by reading a crackpot rant sent to me by a reader. I'll deal with said crackpot in a different post when I have time. But in the meantime, let's take a look at axioms.

## Basics: Discrete vs Continuous

One thing that I frequently touch on casually as I'm writing this blog is the distinction between continuous mathematics, and discrete mathematics. As people who've been watching some of my mistakes in the topology posts can attest, I'm much more comfortable with discrete math than continuous.

## Not Quite Basics: Sorting Algorithms

Multiple people have written to me, after seeing yesterday's algorithms basics post, asking me to say more about sorting algorithms. I have to say that it's not my favorite topic - sorting is one of those old bugaboos that you can't avoid, but which gets really dull after a while. But there is a kernel of interest to it - sorting can be used to demonstrate a lot of interesting ideas about
computational complexity.