75 years ago this month, Alan Turing published a math paper that described a theoretical computer. This “computing machine” was capable of running a program constructed from simple state transitions, but performing complex calculations. This was the foundation of computer software as we know it today.

All of the capabilities and limitations of software are found in Turing’s first machine. Others have proven that any software written in our modern programming languages can be executed by a Turing Machine. And the converse is also true. So any limitation of the Turing Machine is a limitation of all software. This is a property known as Turing Completeness.

Dependency Tracking

The first Turing Machines were deterministic. The actions of a deterministic Turing Machine are based only upon the internal state of the machine and the symbol that it is scanning. If the machine never scans a symbol, then changing that symbol would have no impact on the behavior of the machine. Since this is true of a Turing Machine, it is true of all software.

If you flip this around, you can see how to track dependencies within a software system. If you need to calculate one number (say the balance of your checking account), you can write a program to scan a bunch of other numbers (the amounts of your checks) and come up with an answer. The behavior of the machine, and therefore the final outcome, depends upon the scanned values. If you were to change a value somewhere in the computer’s memory that it didn’t scan, it would still come up with the same value.

The balance of your checking account depends upon the amounts of all your checks. You can tell by keeping track of which symbols the machine scans while it’s making that calculation. If any of those symbols is changed, then the balance needs to be recalculated. What if the amount of a check is modified? The machine scanned the amount of that check while calculating the balance, so it needs to be recalculated. What if a new check is added? The machine at some point scanned a symbol that told it that it was done with the list of checks. To add a new check, you must have modified this symbol. So, again, the balance would need to be recalculated.

Dependency tracking systems keep a record of every symbol that a program scans while it is calculating a value. Then, when one of those scanned symbols changes, it knows that the value needs to be recalculated. I know of two such dependency tracking systems: Knockout.js for JavaScript, and Update Controls for .NET.

Determinism can always be converted into dependency. If it is true for a Turing Machine, then it is also true of any modern programming language. That’s the advantage of knowing that a language is Turing Complete.