We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Turing Universality of Recursive Patterns for Parallel Programming.
- Authors
Fischer, Jörg; Gorlatch, Sergei
- Abstract
Dijkstra's famous thesis "goto considered harmful", which paved the way for structured programming, was formally substantiated by the result of Böhm and Jacopini on the Turing universality of the three well-known basic programming constructs. We argue for a similar idea in parallel programming -- "send-receive considered harmful" -- i.e. abandoning explicit send-receive statements between processors and expressing programs using a restricted set of parallel constructs. We deal with recursive patterns of parallelism, represented formally as morphisms in a suitable calculus. The aim of this paper is to study the expressive power of two morphisms -- catamorphisms and anamorphisms. For a restricted program calculus based on these morphisms, we constructively prove two formal results, whose pragmatic message is: (1) A programming language based on catamorphisms is computationally equivalent to the class of primitive recursive functions; (2) A programming language based on both catamorphisms and anamorphisms is equivalent to the class of partial recursive functions and is therefore Turing-universal. We present a case study on numerical integration, demonstrating the expressive power of ana- and catamorphisms for parallel programming.
- Subjects
PARALLEL processing; STRUCTURED programming; RECURSIVE functions
- Publication
Parallel Processing Letters, 2002, Vol 12, Issue 2, p229
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S012962640200094X