Turing-Completeness Totally Free

DOI10.1007/978-3-319-19797-5_13MaRDI QIDQ2941179zbMATH OpenOpenAlexFDO

Authors Conor McBride

Publication date 27 August 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://strathprints.strath.ac.uk/60166/

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18)

Recommendations

• Parameter free induction and provably total computable functions
• Banishing robust Turing completeness
• BANISHING ROBUST TURING COMPLETENESS
• Turing reducibility in the fine hierarchy
• scientific article; zbMATH DE number 4033092
• Complementation in the Turing degrees
• Complexity, decidability and completeness
• Turing computability: structural theory
• Combinatory completeness without classical equality
• scientific article; zbMATH DE number 1909819

Cites work

• A finite axiomatization of inductive-recursive definitions
• Algebraic operations and generic effects
• Algebras, coalgebras, monads and comonads
• Codifying guarded definitions with recursive schemes
• Containers, monads and induction recursion
• Copatterns, programming infinite structures by observations
• General Recursion via Coinductive Types
• scientific article; zbMATH DE number 4179333 (Why is no real title available?)
• scientific article; zbMATH DE number 3859117 (Why is no real title available?)
• scientific article; zbMATH DE number 2006633 (Why is no real title available?)
• scientific article; zbMATH DE number 7362470 (Why is no real title available?)
• Monadic presentations of lambda terms using generalized inductive types
• Monads need not be endofunctors
• Nested general recursion and partiality in type theory
• Notions of computation and monads
• Programming with algebraic effects and handlers
• Simple general recursion in type theory
• Small induction recursion
• Types for Proofs and Programs

Cited in

(7)

• Turing Tumble is Turing-complete
• Linear Recursive Functions
• Combining predicate transformer semantics for effects: a case study in parsing regular languages
• Doo bee doo bee doo
• A sound strategy to compile general recursion into finite depth pattern matching
• What does it take to certify a conversion checker?
• Functoriality of enriched data types

This page was built for publication: Turing-Completeness Totally Free

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941179)