lo.logic - computation, algebra, logic

From this description it is not hard to see the connection of classical computation to discrete dynamical systems and classical logic, the operations provide the dynamics by flipping bits around in a controlled fashion and since we restrict the operations to a certain subset we get classical logic.

Careful -- this observation only works for purely finite-state systems! If your idealized model of a digital computer can handle potentially unbounded quantities of input, then the connection to classical logic is lost. Happily, it fails in a way that reveals connections to topology, and explains why topological models of intuitionistic logic exist.

The basic idea is that we view a computer as realizing a function $f$. Then for any input value (from the input set $A$), if it returns an answer in a finite amount of time, it can have observed at most a finite amount of information about the input. This means that we can equip our input set with a topology in the following way: suppose our basic observations are a collection of predicates on $A$. Then we get the topological structure from the following fact: we can only take finite intersections because we can only make finitely many observations, and so can only conclude the conjunction of finitely many predicates. We can take infinite unions (i.e., existentials) because we can "get lucky" and guess the correct branch of the union (i.e., witness to the existential).

Then, amazingly, we can use continuity as a stand-in for computability! This is pretty much the idea Dana Scott had when he invented domain theory (which gets a different name because the topologies that we get this way are "weird" -- e.g., they're typically not Hausdorff -- and so the theorems you want develop a bit differently).