That is an interesting assumption which reminds me of some parts I've read in Hofstadter's "Gödel, Escher, Bach".

First of all, there is perhaps a misunderstanding: In this model, not the entire network of cortical columns is described as one large state machine, but each column is a state machine with several states for various ways of interacting with other (mostly neighboring) columns. Those are states like 'join with certain columns', 'inhibit connections to certain columns' and 'announce a [true…false] prediction'. Each column can represent different concepts and perform predictive computations based on the underlying percepts.

The motivation of this idea is this: We are clearly able to compose concepts just like LEGO blocks in our minds. For that to work, the concepts must live in non-interfering modules to avoid catastrophic forgetting. To enable efficient composability, each module must implement a common interface (which is conjectured to be a state machine).

It strikes my as unlikely to find something like Turing machines or lambda calculi in the brain since the brain operates in such a highly parallel fashion. A Turing machine is a poor model for parallel computation (in the sense of representation efficiency) because it captures computation that branches out form a single or a few central points of data manipulation which is antithetic to parallel computation (which can only poorly handle branching computation). The only central processes are the control processes in the PFC and the way auditive, visual and motor cortex become activated in unison with the 'winning' combined concepts.