Structured turing machines

A structured decomposition theorem for Turing machines is given. The nature of the building blocks and the form of the connections allowed suggest a parallel to the Bohm-Jacopini theorem on structured flowcharts. Thus in a broadest sense, there is obtained an independent machine-theoretic restatement of the fundamental precepts of structured programming. At the same time, the characteristics of the decomposition offer several obvious advantages over known results of this type. In particular, the building blocks (the “simple” machines) are seen to perform total and regular word functions. Furthermore, the connections themselves should prove to be useful as pedagogical tools in the Turing machine theory and as a theoretical framework for top-down machine (or algorithmic) design