Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Hartley Rogers in his "Theory of recursive functions and effective computability" (page 55 in the first edition) writes

"What resemblance types are also isomorphism types? A final answer to this question has not been given. The only cases presently known are the type of the empty partial functions, the type of all constant functions, and the type of all universal partial functions.^1

1 A proof that these are the only cases possible could lead to an interesting algebraic axiomatizations of the partial recursive functions."

What did he mean by "algebraic axiomatization of the partial recursive functions"?

share|improve this question
    
There is a technical definition of algebraic theory: it is a first-order theory with a fixed number (usually finite, sometimes infinite) of finitary operations with all its axioms expressed as universally quantified equations. For example, the theories of groups, rings, and Lie algebras are all algebraic, while the theory of fields is not. –  Zhen Lin Jan 7 '12 at 1:21
    
Thank you for the reply. Am I right to assume that, so far at least, there is no algebraic theory of partial recursive functions? –  Peter Percival Jan 25 '12 at 14:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.