Flow Diagrams, Turing Machines And
Languages With Only Two Formation Rules

In the first part of the paper, flow diagrams
are introduced to represent inter al. mappings 
of a set into itself.  Although not every diagram is
decomposable into a finite number of given base 
diagrams, this becomes true 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 
three base diagrams; the second, only two.  In the second
part of the paper, the second method is applied 
to the theory of Turing machines.  With every Turing
machine provided with a two-way half-tape, there 
is associated a similar machine, doing essentially
the 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 L and R.  That family is a proper 
subfamily of the whole family of Turing machines.

CACM May, 1966

Bohm, C.
Jacopini, G.

CA660512 JB March 3, 1978  9:35 AM

1425	4	1425
1781	4	1425
438	4	1425
762	4	1425
249	5	1425
1425	5	1425
1425	5	1425
1425	5	1425
2709	5	1425
2802	5	1425
3004	5	1425
1425	6	1425
1425	6	1425
1425	6	1425
2138	6	1425
2204	6	1425
2247	6	1425
2356	6	1425
2456	6	1425
2456	6	1425
2477	6	1425
3186	6	1425