THE EQUIVALENCE OF R.E. PROGRAMS AND DATA FLOW SCHEMES
Original Publication Date: 1899-Dec-30
Included in the Prior Art Database: 2007-Apr-12
Software Patent Institute
Jaffe, Jeffrey: AUTHOR [+2]
AbstractTHE EQUIVALENCE OF R. E. PROGRAMS AND DATA FLOW SCHEMES Jeffrey Jaffe
THE EQUIVALENCE OF R. E. PROGRAMS AND DATA FLOW SCHEMES
MASSACHUSETTS INSTITUTE OF TECHNOLOGY
LABORATORY FOR COMPUTER SCIENCE
sf r.e. parogram~ schemes and data flow schemes
Jeffrey Jaffe, NllT *
Abstract. T11~2 ~xpr~ssive
power of the data flow schemes of Dennis is
evaluated. It is shown that data flow schemes have the power to express an
arbitrary def er~n
tnate functional. The proof involves a demonstration that
"restricterl data flow sch@nies'"aaln simulate Turing Machines. This provides a new, simpl~
basjs for conipu tability.
Keywords. data flow schemes, r.e. program schemes, effective functionals, Turlng Machines, computability
Early res3archers investigatmg %he relative "pswer'~or
"expressiveness" of d j f ferent prograrnrning eonst ructs quickly determined that a
comparison of t h ~
s ~ t
of partial recursive funct.ions computed did not
adequately capturtl t h ~
diZferea'lces between the different programming styles.
Any reasosiable se': of constructs computes all partial recursive functicpns, and thus all constrl~ct:; are equival~nt.
A differel-it technique has evolved for casmparing pregrammi~ constructs.
The notion of a sc,ht?~ne
has bwn introdtaced [$,I 0,11), which enables one to
discern differences between the classes of functiolnals computable by different constructs. Esse~~Eially,
in a scheme there are ncr defined operations and thus
" This l-eport was prepared with the support of a PJatio~aaH Science Fourndatisns
graduate Kclllorvship, a11rl Natioamal Scicncc Foundation grant no, MCS.77-19754.
(for @sample) variables can not be used as counters. Rather, a11 function and pbrresicate symbols are unintergreted, and a "scheme" is a functionali over the symbols. This approach turned oit to be quite successful, as it provided e rigorous interpretation to intuitive ideas such as "recursion is more powerful than iteration'" C12,%5].
A hierarchy of program construkts has been developed ['Q,2]. It turns
out that just as there is a notion of "all primitive recursive functionsq",
there is an analogous thesis ahout a construct being equivalent to "a11 effective determinate functionals" oor "all recursively enumerable (r.e,) program schemes" [ 141.
Data flow schemes were introduced by Dennis  to serve as a model of
progranlnaing constructs to be ansed for highly parallel, data driven computer architectures. The power of this basic construct has never been fully explored. Early researchers in this area felt that it would be worthwhile to sacrifice the Pull power 0% this const~uct in order to enforce programming disciplines that arc similar to those f...