Turing machines and bimachines

摘要

We associate the iterated block product of a bimachine with a deterministic Turing machine. This allows us to introduce new algebraic notions to study the behavior of the Turing machine. Namely, we introduce double semidirect products through matrix multiplication of upper triangular matrices with coefficients in certain semigroups, which leads in turn to the study of the iterations of bimachines. By passing to the profinite (or projective) limit, we obtain an algebraic profinite description of the limit behavior of the Turing machine. Finally, we analyze the proof that all languages in NP can be reduced to CIRCUIT SAT from this viewpoint.