I felt like venting a bit. Let's take a brief stroll through computability land.

The difference is computability.

Computability is important to a programmer. It's fundamental to the act, even. Let's just say it's basically everything. Why waste cycles trying to compute the uncomputable! Or better yet, why introduce bugs trying to compute a problem using an insufficient computation model!

Computation models

You already know about these, even if you don't realize it. There are three we encounter frequently:

1. DFAs
2. PDAs
3. Turing Machines

Deterministic Finite Automata

DFAs can be specified using regular expressions. Yes, a regular expression is just a convenient DSL for specifying a state machine. The regex engine in your favorite programming language adds on more power than a vanilla regular expression, but there are still some fundamental limitations to consider.

For instance, whenever you have to count, dynamically, you'll need something more powerful. You'll need some memory to go along with that state.

Say, you want to match all strings with the same number of leading 0s as trailing 1s. Informally specified as:

0ⁿ1ⁿ

Remember, n is dynamic, it depends on the string. Now, think of a simple regular expression to match that. No, DFAs are not powerful enough to recognize this pattern.

It also can't recognize HTML or XML, for this same reason. You can get away with a limited subset of HTML or XML, but not the full language.

For that, you need at least a PDA.

Push-Down Automata

A PDA is like a DFA, but it can track where it's been using a stack. The stack, along with the string input, is used to determine the next transition. A stack machine!

PDAs can be specified using a Context-free Grammer.

Okay, maybe you don't encounter these frequently. That's because a more powerful model is usually available.

Turing Machines

If you're using a programming language, one that is Turing complete, well, you're building Turing machines. A Turing Machine is an algorithm. A program is just a big (or little) algorithm. This is the most sophisticated level of computation you'll encounter.

Turing machines can be specified using, well, Turing-complete programming languages.

Compilers

The stages of a compiler require progressively higher levels of computation:

• Lexer: DFA
• Parser: PDA
• Type Checker, Code Gen: Turing Machine

Of course, you'd only actually need a TM to implement all stages, but as good software engineering principles hold, less is more.

I'll work on writing more coherent blog posts in the future. Not saying that's my new years resolution though.