The computational power of M^

DOI10.1002/1521-3870(200201)48:1%3C117::AID-MALQ117%3E3.0.CO;2-JMaRDI QIDQ2776817zbMATH OpenOpenAlexFDO

Authors Christian Rørdam, Dag Normann

Publication date 16 September 2002

Published in Mathematical Logic Quarterly (MLQ) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/1521-3870(200201)48:1%3C117::aid-malq117%3E3.0.co;2-j

zbMATH Keywords

\(\mu\)-recursioncontinuous functionalsdomainsfan functionalhigher typestotal functionals

Mathematics Subject Classification ID

Higher-type and set recursion theory (03D65)

Review text

This is a comparison of the strengths of systems for computation with higher-type functionals. In a 1999 paper [Ann. Pure Appl. Logic 99, 73-92 (1999; Zbl 0932.03030)] \textit{K.-H. Niggl} introduced the system \({\mathcal M}^\omega\) and conjectured that it was strictly weaker than Plotkin's \(\text{PCF}+ \text{PA}\). The present paper confirms that conjecture by showing that the type-3 fan functional, known to be definable in PCF, is not definable in \({\mathcal M}^\omega\).

Recommendations

• Comparing Computational Power
• Computability in higher types, P and the completeness of type assignment
• \({\mathcal M}^\omega\) considered as a programming language
• scientific article; zbMATH DE number 3933051
• scientific article; zbMATH DE number 1497732

Cites work

• Computations in higher types
• scientific article; zbMATH DE number 1390018 (Why is no real title available?)

This page was built for publication: The computational power of \({\mathcal M}^\omega\)

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