Browse Prior Art Database

THE EQUIVALENCE OF R.E. PROGRAMS AND DATA FLOW SCHEMES

IP.com Disclosure Number: IPCOM000149198D
Original Publication Date: 1899-Dec-30
Included in the Prior Art Database: 2007-Apr-12
Document File: 76 page(s) / 2M

Publishing Venue

Software Patent Institute

Related People

Jaffe, Jeffrey: AUTHOR [+2]

Abstract

THE EQUIVALENCE OF R. E. PROGRAMS AND DATA FLOW SCHEMES Jeffrey Jaffe

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 5% of the total text.

Page 1 of 76

THE EQUIVALENCE OF R. E. PROGRAMS AND DATA FLOW SCHEMES

Jeffrey Jaffe

MASSACHUSETTS INSTITUTE OF TECHNOLOGY

LABORATORY FOR COMPUTER SCIENCE

MASSACHUSETTS 02139

CAMBRIDGE

[This page contains 1 picture or other non-text object]

Page 2 of 76

[This page contains 1 picture or other non-text object]

Page 3 of 76

The equivalen~ce
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.

[This page contains 1 picture or other non-text object]

Page 4 of 76

(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 [3] 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...