The computational power of \({\mathcal M}^\omega\) (Q2776817)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The computational power of \({\mathcal M}^\omega\) |
scientific article; zbMATH DE number 1716773
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The computational power of \({\mathcal M}^\omega\) |
scientific article; zbMATH DE number 1716773 |
Statements
16 September 2002
0 references
\(\mu\)-recursion
0 references
higher types
0 references
continuous functionals
0 references
total functionals
0 references
domains
0 references
fan functional
0 references
The computational power of \({\mathcal M}^\omega\) (English)
0 references
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\).
0 references
0.7218881249427795
0 references
0.7215165495872498
0 references
0.7204985022544861
0 references
