On the Structural Simplicity of Machines and Languages

We employ an algebraic method for comparing the structural simplicity of families of abstract machines. We associate with each family of machines a first-order structure that includes machines as objects, composition operations, which construct larger machines from smaller ones, as functions, and a set of semantic relations. We then compare families of machines by studying the existence of homomorphisms between the associated structures. Given families of machines L, L 0 with associated structures S, S 0 , we say that L is simpler than L 0 if there is a homomorphism of S into S 0 , but not vice versa. We show that across several abstract machine models --- finite automata, Turing machines, and logic programs --- deterministic machines are simpler than nondeterministic machines and nondeterministic machines are simpler than alternating machines. Our results cross computational complexity boundaries. We show that for Turing machines, finite automata and logic programs every non..