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

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

May, 1966 | Corrado Böhm and Giuseppe Jacopini
This paper introduces flow diagrams as a two-dimensional programming language for representing mappings of a set into itself. It discusses two normalization methods for flow diagrams: one with three base diagrams and another with only two. The second method is applied to the theory of Turing machines, showing that every Turing machine can be reduced to or is equivalent to a program using only composition and iteration as formation rules. Flow diagrams are decomposable into base diagrams, but not all diagrams can be decomposed into a finite number of given base diagrams. However, by extending the set and mappings, decomposition becomes possible at a semantical level. The paper also introduces new functional and predicative boxes to enhance decomposability. It demonstrates that any mapping representable by a flow diagram can be expressed using a formula involving diagrams Π, Φ, and Δ, along with new boxes T, F, K, and ω. The paper further shows that Turing machines can be transformed into a subfamily of Turing machines using composition and iteration, proving that every Turing machine is reducible to a program in a language with only two formation rules. The paper concludes with a discussion on the implications of these results for programming and computation theory.This paper introduces flow diagrams as a two-dimensional programming language for representing mappings of a set into itself. It discusses two normalization methods for flow diagrams: one with three base diagrams and another with only two. The second method is applied to the theory of Turing machines, showing that every Turing machine can be reduced to or is equivalent to a program using only composition and iteration as formation rules. Flow diagrams are decomposable into base diagrams, but not all diagrams can be decomposed into a finite number of given base diagrams. However, by extending the set and mappings, decomposition becomes possible at a semantical level. The paper also introduces new functional and predicative boxes to enhance decomposability. It demonstrates that any mapping representable by a flow diagram can be expressed using a formula involving diagrams Π, Φ, and Δ, along with new boxes T, F, K, and ω. The paper further shows that Turing machines can be transformed into a subfamily of Turing machines using composition and iteration, proving that every Turing machine is reducible to a program in a language with only two formation rules. The paper concludes with a discussion on the implications of these results for programming and computation theory.
Reach us at info@study.space