Flow diagrams, turing machines and languages with only two formation rules
Corrado Böhm, Giuseppe Jacopini · Communications of the ACM · 1966
In the first part of the paper, flow diagrams are introduced to represent inter ah mappings of a set into itself.Although not every diagram is decomposable into a finite numbm of given base diagrams, this becomes hue at a semantical level due to a suitable extension of the given set and of the basic mappings defined in it.Two normalization methods of flow diagrams are given.The first has |hree base diagrams; the second, only two.In the second part of the paper, the second method is applied to 'lhe theory of Turing machines.With every Turing maching provided with a two-way half-tape, ihere is associated a similar machine, doing essentially 'lhe same job, but working on a tape obtained from the first one by interspersing alternate blank squares.The new machine belongs to the family, elsewhere introduced, generated by composition and iteration from the two machines X and R.That family is a proper subfamily of the whole family of Turing machines.