A Machine-Independent Theory of the Complexity of Recursive Functions
作者： Manuel Blum
关键词:
摘要: The number of steps required to compute a function depends, in general, on the type computer that is used, choice program, and input-output code. Nevertheless, results obtained this paper are so general as be nearly independent these considerations.A exhibited requires an enormous computed, yet has “nearly quickest” program: Any other program for function, no matter how ingeniously designed it may be, takes practically many quickest program.A different with property fast computing another exists very much faster.
acm.org
sci-hub.se 参考文章(7)
S. Winograd, On the Time Required to Perform Multiplication Journal of the ACM. ,vol. 14, pp. 793- 802 ,(1967) , 10.1145/321420.321438
Michael Arbib, Manuel Blum, Machine dependence of degrees of difficulty. Proceedings of the American Mathematical Society. ,vol. 16, pp. 442- 447 ,(1965) , 10.1090/S0002-9939-1965-0181538-0
Robert W. Ritchie, CLASSES OF PREDICTABLY COMPUTABLE FUNCTIONS Transactions of the American Mathematical Society. ,vol. 106, pp. 139- 173 ,(1963) , 10.1090/S0002-9947-1963-0158822-2
Michael O. Rabin, Real time computation Israel Journal of Mathematics. ,vol. 1, pp. 203- 211 ,(1963) , 10.1007/BF02759719
M. O. Rabin, Degree of difficulty of computing a function and a partial ordering of recursive sets CTIT technical reports series. ,(1960)
J. Hartmanis, R. E. Stearns, On the computational complexity of algorithms Transactions of the American Mathematical Society. ,vol. 117, pp. 285- 306 ,(1965) , 10.1090/S0002-9947-1965-0170805-7
Hisao Yamada, Real-Time Computation and Recursive Functions Not Real-Time Computable IEEE Transactions on Electronic Computers. ,vol. EC-11, pp. 753- 760 ,(1962) , 10.1109/TEC.1962.5219459