A note on arbitrarily complex recursive functions

DOI10.1305/NDJFL/1093637869MaRDI QIDQ1106201zbMATH OpenOpenAlexFDO

Authors Carl H. Smith

Publication date 1988

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1305/ndjfl/1093637869

zbMATH Keywords

arbitrarily complex recursive functions

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Recommendations

• A note on A.E. h-complex functions
• Embedding recursive functions in universal algorithms
• Comparison between the complexity of a function and the complexity of its graph
• scientific article; zbMATH DE number 1222608

Cited in

(9)

• scientific article; zbMATH DE number 1354146 (Why is no real title available?)
• The intrinsic difficulty of recursive functions
• A characterisation of multiply recursive functions with Higman's lemma.
• A note on A.E. h-complex functions
• Embedding recursive functions in universal algorithms
• ‘Golomb-like’ nested recursions with Beatty function solutions
• Almost-everywhere complexity hierarchies for nondeterministic time
• Generating some classes of recursive functions by superpositions of simple arithmetic functions
• A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes

This page was built for publication: A note on arbitrarily complex recursive functions

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