Axiomas de Bloom

En la teoría de la complejidad computacional, los axiomas de Bloom son axiomas que definen las propiedades de las medidas de complejidad en un conjunto de funciones computables . Estos axiomas fueron formulados por primera vez por Manuel Blum en 1967.

Es importante que tanto el teorema de la aceleración de Blum como el teorema de la brecha sean ciertos para cualquier medida de complejidad que satisfaga estos axiomas. Los ejemplos más conocidos de tales medidas son el tiempo de ejecución (TIEMPO) y la cantidad de memoria utilizada (ESPACIO).

Definiciones

La medida de complejidad de Bloom es el par formado por la enumeración de Gödel de funciones computables y la función computable ${\ estilo de visualización (\ varphi, \ phi)}$ $\varphi$ ${\displaystyle \mathbf {P} ^{(1)))$

\Phi:\mathbb {N} \to \mathbf {P} ^{(1)},

satisfaciendo los siguientes axiomas de Bloom . Denotamos por la i - ésima función computable según la numeración de Gödel , y por — la función computable . $\varphi _{i}$ $\varphi$ ${\ estilo de visualización \ Phi _ {i}}$ ${\ estilo de visualización \ Phi (yo)}$

los dominios de y coinciden. $\varphi _{i}$ ${\ estilo de visualización \ Phi _ {i}}$
el conjunto es solucionable . ${\displaystyle \{(i,x,t)\in \mathbb {N} ^{3}|\Phi _{i}(x)=t\))$