“Blum’s axioms”的概念、定义、翻译、参考文献-科学参考

Blum’s axioms

Computer

单词	Blum’s axioms
释义	Blum’s axioms Computer Two axioms in complexity theory, formulated by M. Blum. Let $M_{1}, M_{2}, \dots, M_{n}, \dots$ be an effective enumeration of the Turing machines and let f_i be the partial recursive function of a single variable that is computed by M_i. (For technical reasons it is simpler to think in terms of partial recursive functions than set (or language) recognizers.) if $F_{1}, F_{2}, \dots, F_{n}, \dots$ is a sequence of partial recursive functions satisfying axiom 1: f_i(n) is defined if and only if F_i(n) is defined, and axiom 2: F_i(x) ≤ y is a recursive predicate of i, x, and y, then F_i(n) is a computational complexity measure and can be thought of as the amount of some ‘resource’ consumed by M_i in computing f_i(n). This notion represents a useful abstraction of the basic resources—time and space. Several remarkable theorems about computational complexity have been proved for any measure of resources satisfying the two axioms (see gap theorem, speedup theorem).
随便看	Prévost’s theory of exchanges ps PS/2 keyboard/mouse interface PSA PSAC Psamathe psammite PSC PSD PSDS PSE psephite pseudo pseudoaromatic pseudoautosomal region pseudo-axial pseudobreccia pseudocarp Pseudociliata pseudocode pseudocoelomate pseudocomponent pseudocritical properties Pseudo-Dionysius pseudoephedrine