Turing Machines
The Turing Machine is a theoretical abstraction for the discussion of computability problems, and one of the absolutely key fundamental ideas in computer science. They were introduced by Alan Turing in a paper titled On Computable Numbers, with an Application to the Entscheidungsproblem, which was published in 1936. Any algorithm that can be represented as a Turing machine can be processed by a computer, and vice versa. Turing machines are the simplest abstraction for computability there is. Notably, there are Turing machines that describe Turing machines, proving they're, well, computable.
Any programming language that is Turing complete can be used to express any possible algorithm. Elegance is not implied, just sheer possibility. Thus, considerable sophistication, such as in languages like Haskell, isn't needed. A simple language like Brainfuck is Turing complete as well. Arguably, the "hello, world" source code in Brainfuck is not readily intelligible, but that's not the point.
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.Turing machines are such a fascinating idea that people have even built Lego versions of them.
Anyway. I wanted to point to a really interesting book. Turing's seminal paper, while groundbreaking, is a bit hard to access because of its mathematical style. Charles Petzold has thankfully set out to take the paper and write a book around it that explains everything in great detail for a much broader audience. The Annotated Turing is a really fun read.
Tags: the-nerdy-bit, books