Volume 9 / Number 5 / May, 1966 | Corrado BÖHM and Giuseppe JACOPINI
The paper introduces flow diagrams as a two-dimensional programming language and explores their normalization methods. It presents two normalization techniques for flow diagrams, one using three base diagrams and the other using only two. The second method is then applied to the theory of Turing machines, demonstrating that every Turing machine can be reduced to a program written in a language with only composition and iteration as formation rules. The authors define new functional and predicative boxes (T, F, K, and ω) to extend the language and prove that any flow diagram can be decomposed into these new base diagrams. They also show that every Turing machine can be associated with a similar machine that operates on a tape with alternate blank squares, and this new machine belongs to a subfamily of Turing machines generated by composition and iteration. The paper concludes with a detailed mathematical proof of these results.The paper introduces flow diagrams as a two-dimensional programming language and explores their normalization methods. It presents two normalization techniques for flow diagrams, one using three base diagrams and the other using only two. The second method is then applied to the theory of Turing machines, demonstrating that every Turing machine can be reduced to a program written in a language with only composition and iteration as formation rules. The authors define new functional and predicative boxes (T, F, K, and ω) to extend the language and prove that any flow diagram can be decomposed into these new base diagrams. They also show that every Turing machine can be associated with a similar machine that operates on a tape with alternate blank squares, and this new machine belongs to a subfamily of Turing machines generated by composition and iteration. The paper concludes with a detailed mathematical proof of these results.