Linear recursive functions

• Type: Article in International Conference Proceedings Book
• Date: 2007

Authors

Sandra Alves (Author) FCUP; Maribel Fernandez (Author) Other; Mario Florido (Author) FCUP; Ian Mackie (Author) Other

Conference proceedings International

Title: Rewriting, Computation and Proof: ESSAYS DEDICATED TO JEAN-PIERRE JOUANNAUD ON THE OCCASION OF HIS 60TH BIRTHDAY

Pages: 182-195

Festschrift held in Honor of Jean-Pierre Jouannauds 60th Birthday on Rewriting, Computation and Proof

Cachan, FRANCE, JUN 21-22, 2007

Indexing

ISI Web of Knowledge - 6 Citations

Scopus - 8 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-004-EJP

DOI: 10.1007/978-3-540-73147-4_9

Abstract (EN): With the recent trend of analysing the process of computation through the linear logic looking glass, it is well understood that the ability to copy and erase data is essential in order to obtain a Turing-complete computation model. However, erasing and copying don't need to be explicitly included in Turing-complete computation models: in this paper we show that the class of partial recursive functions that are syntactically linear (that is, partial recursive functions where no argument is erased or copied) is Turing-complete.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14