Thinking Complete

I want to investigate the nature of and limits of mathematics. To do that, I'll explore logic, set theory, computability, information theory and philosophy. Be warned that this essay is rather long; it starts relatively easy and gets significantly harder. I hope everyone will get something out of it (including my tutors!) but if you're new to mathematics, that might not be much. If you're philosophically inclined, definitely look at the last section on Truth and Induction. Any discussion or errata are of course very welcome. Let's start with some historical background. Although the Babylonians were able to do some interesting calculations (particularly astronomical), mathematics in the sense of deductive arguments from premises to conclusions began with Thales, Pythagoras and their disciples. Greek maths was focused on geometry, which was formalised by Euclid into 5 axioms - foundational assertions - from which he proved many theorems. Euclidean geometry (as formalis...

I've just finished the bulk of a personal project, a C++ program which stores and manipulates regular expressions and finite automata. Clocking in at over 1000 lines of code in total, it was a bit more work than I thought it'd be, but I'm pretty happy with it overall (modulo a bit more debugging and refactoring). The biggest problem has been finding a way to explain the project to non-computer-scientists. If you're reading this blog, you've probably heard of Turing Machines, and the idea that they can do any calculation possible in this universe (as far as we know). What about simpler versions of Turing Machines? It turns out that you can define a number of different machines which are strictly less powerful. Near the bottom of this hierarchy are finite automata, which consist only of a finite number of states, with transitions between them. A finite automaton - they come in two varieties, deterministic (DFA) and non-deterministic (NFA) - "accepts" a str...