Title : 
There is no recursive axiomatization for feasible functionals of type 2
         
        
        
            Author_Institution : 
Comput. Sci. Group, Tata Inst. of Fundamental Res., Bombay, India
         
        
        
        
        
        
            Abstract : 
The author shows a class of type-two feasible functionals, C 2, that satisfies Cook´s conditions, (1990) and cannot be expressed as the lambda closure of type-one poly-time functions and any recursively enumerable set of type-two feasible functionals. Further, no class of total type-two functionals containing this class is representable as the lambda closure of a recursively enumerable set of type-two total computable functionals and type-one poly-time functions. The definition of C2 provides a clear computational procedure for functionals of C2. Using functionals of class C2 a more general notion of polynomial-time reducibility between two arbitrary type-one functions can be introduced
         
        
            Keywords : 
Turing machines; computational complexity; recursive functions; Turing machines; computational procedure; feasible functionals; lambda closure; polynomial-time reducibility; recursive axiomatization; recursively enumerable set; time complexity; type-one poly-time functions; type-two feasible functionals; Calculus; Computer science; Polynomials; Turing machines;
         
        
        
        
            Conference_Titel : 
Logic in Computer Science, 1992. LICS '92., Proceedings of the Seventh Annual IEEE Symposium on
         
        
            Conference_Location : 
Santa Cruz, CA
         
        
            Print_ISBN : 
0-8186-2735-2
         
        
        
            DOI : 
10.1109/LICS.1992.185541