The intrinsic difficulty of recursive functions (Q1919986): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q290243 |
||
| Property / reviewed by | |||
| Property / reviewed by: Marius Zimand / rank | |||
Revision as of 16:53, 12 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The intrinsic difficulty of recursive functions |
scientific article |
Statements
The intrinsic difficulty of recursive functions (English)
0 references
28 July 1996
0 references
The paper attempts to offer a robust definition of the notion of an intrinsic (i.e., independent of the computational model) natural complexity measure. The main concept is obtained by using abstract (Blum) complexity measures and smear monoids, a type of monoid introduced here that allows some slack in the comparison of the complexity of recursive functions. Various mathematical and philosophical arguments stress the merits of the concepts introduced in the paper.
0 references
subrecursive hierarchies
0 references
intrinsic natural complexity measure
0 references
complexity of recursive functions
0 references
