Turing-completeness totally free

McBride, Conor; Hinze, Ralf and Voigtländer, Janis, eds. (2015) Turing-completeness totally free. In: Mathematics of Program Construction. Lecture Notes in Computer Science, 9129 . Springer, DEU, pp. 257-275. ISBN 9783319197968 (https://doi.org/10.1007/978-3-319-19797-5_13)

Preview

Text. Filename: McBride_LNCS2015_Turing_completeness_totally_free.pdf Accepted Author Manuscript Download (287kB)| Preview

Abstract

In this paper, I show that general recursive definitions can be represented in the free monad which supports the ‘effect’ of making a recursive call, without saying how these calls should be executed. Diverse semantics can be given within a total framework by suitable monad morphisms. The Bove-Capretta construction of the domain of a general recursive function can be presented datatype-generically as an instance of this technique. The paper is literate Agda, but its key ideas are more broadly transferable.

ORCID iDs

McBride, Conor ORCID: https://orcid.org/0000-0003-1487-0886

• Share and Export
  

  RDF+XMLBibTeXRIOXX2 XMLRDF+N-TriplesJSONDublin CoreAtomSimple MetadataReferMETSHTML CitationASCII CitationOpenURL ContextObjectEndNoteOpenURL ContextObject in SpanMODSMPEG-21 DIDLEP3 XMLData Cite XMLRIS (EndNote Online, Zotero, Ref manager, etc)RDF+N3Multiline CSV
• Citations and altmetrics
• Item metadata

  Item type:	Book Section
  ID code:	60166
  Dates:	Date Event 9 June 2015 Published 16 March 2015 Accepted
  Keywords:	monad morphisms, total functional programming, monads, general recursion, Electronic computers. Computer science, Computer Science(all)
  Subjects:	Science > Mathematics > Electronic computers. Computer science
  Department:	Faculty of Science > Computer and Information Sciences
  Depositing user:	Pure Administrator
  Date deposited:	13 Mar 2017 16:26
  Last modified:	08 Aug 2023 08:30
  Related URLs:	Event
  URI:	https://strathprints.strath.ac.uk/id/eprint/60166