In:
ACM SIGACT News, Association for Computing Machinery (ACM), Vol. 20, No. 4 ( 1989-11), p. 87-91
Abstract:
The primitive recursive functions are the least class of functions on the natural numbers containing the constant, successor, and projection functions, and closed under composition and the rule of primitive recursion. A weakened rule of primitive recursion, lacking implicit predecessor, is shown nevertheless to be adequate for defining all of the primitive recursive functions. However, it is conjectured that the still weaker rule of iteration is not adequate, and it is shown that an easily characterized class of 1-Place functions that includes predecessor cannot be defined when only 0- and 1-place intermediate functions are allowed.
Type of Medium:
Online Resource
ISSN:
0163-5700
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
1989
detail.hit.zdb_id:
1133944-5
detail.hit.zdb_id:
243806-9
detail.hit.zdb_id:
2043299-9
Bookmarklink