The intrinsic difficulty of recursive functions (Q1919986)
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: Publication:1919986 |
scientific article; zbMATH DE number 910394
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The intrinsic difficulty of recursive functions |
scientific article; zbMATH DE number 910394 |
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
0.7264651656150818
0 references
0.7203199863433838
0 references
0.7192736268043518
0 references
