Idempotencia

On/Fuera. botones del panel de control de señalización de destino de un tren. Prensando On botón (verde) es una operación idempotente, ya que tiene el mismo efecto si se hace una o varias veces. Asimismo, presionando Fuera. es idempotente.

Idempotencia (,) es la propiedad de ciertas operaciones en matemáticas e informática por la que se pueden aplicar varias veces sin cambiar el resultado más allá de la aplicación inicial. El concepto de idempotencia surge en varios lugares del álgebra abstracta (en particular, en la teoría de los proyectores y operadores de cierre) y la programación funcional (en la que está conectado con la propiedad de transparencia referencial).

El término fue introducido por el matemático estadounidense Benjamin Peirce en 1870 en el contexto de elementos de álgebras que permanecen invariables cuando se elevan a una potencia entera positiva, y literalmente significa "(la cualidad de tener) la misma potencia", de idem + potencia (mismo + poder).

Definición

Un elemento ${displaystyle x}$ de un conjunto ${displaystyle S.$ equipado con un operador binario ${displaystyle cdot }$ se dice que idempotente menores ${displaystyle cdot }$ si

${displaystyle xcdot x=x}$.

El operación binaria ${displaystyle cdot }$ se dice que idempotente si

${displaystyle xcdot x=x}$ para todos ${displaystyle xin S}$.

Ejemplos

• En el monoide ${displaystyle (mathbb {N}times)}$ de los números naturales con multiplicación, sólo 0 y 1 son idempotente. De hecho, ${displaystyle 0times 0=0}$ y ${displaystyle 1times 1=1}$.
• En el monoide ${displaystyle (mathbb {N}$ +) de los números naturales con adición, sólo 0 es idempotente. De hecho, 0 + 0 = 0.
• En un magma ${displaystyle (M,cdot)}$, un elemento de identidad ${displaystyle e}$ o un elemento absorbente ${displaystyle a}$, si existe, es idempotente. De hecho, ${displaystyle ecdot e=e}$ y ${displaystyle acdot a=a}$.
• En un grupo ${displaystyle (G,cdot)}$, el elemento de identidad ${displaystyle e}$ es el único elemento idempotente. De hecho, si ${displaystyle x}$ es un elemento ${displaystyle G.$ tales que ${displaystyle xcdot x=x}$, entonces ${displaystyle xcdot x=xcdot e}$ y finalmente ${displaystyle x=e}$ multiplicando a la izquierda por el elemento inverso ${displaystyle x}$.
• En los monoides ${displaystyle ({mathcal {}(E),cup)}$ y ${displaystyle ({mathcal {}(E),cap)}$ del conjunto de poder ${displaystyle {mathcal {}(E)}$ del conjunto ${displaystyle E}$ con sindicato establecido ${displaystyle cup }$ y la intersección del conjunto ${displaystyle cap }$ respectivamente ${displaystyle cup }$ y ${displaystyle cap }$ son idempotentes. De hecho, ${displaystyle xcup x=x}$ para todos ${displaystyle xin {fnMithcal}(E)}$, y ${displaystyle xcap x=x}$ para todos ${displaystyle xin {fnMithcal}(E)}$.
• En los monoides ${displaystyle ({0,1},vee)}$ y ${displaystyle ({0,1},wedge)}$ del dominio booleano con disyunción lógica ${displaystyle vee }$ y lógica conjunción ${displaystyle wedge }$ respectivamente ${displaystyle vee }$ y ${displaystyle wedge }$ son idempotentes. De hecho, ${displaystyle xvee x=x}$ para todos ${displaystyle xin {0,1}$, y ${displaystyle xwedge x=x}$ para todos ${displaystyle xin {0,1}$.
• En un anillo booleano, la multiplicación es idempotente.
• En una semiringe tropical, la adición es idempotente.
• En un anillo de matrices cuadráticas, el determinante de una matriz idempotente es de 0 o 1. Si el determinante es 1, la matriz es innecesariamente la matriz de identidad.

Funciones idempotentes

En el monoide ${displaystyle (E^{E},circ)}$ de las funciones de un conjunto ${displaystyle E}$ a sí mismo (ver exponentiation set) con composición de función ${displaystyle circ }$, elementos idempotentes son las funciones ${displaystyle fcolon Eto E}$ tales que ${displaystyle fcirc f=f}$, eso es tal ${displaystyle f(f(x)=f(x)}$ para todos ${displaystyle xin E}$ (en otras palabras, la imagen ${displaystyle f(x)}$ de cada elemento ${displaystyle xin E}$ es un punto fijo ${displaystyle f}$). Por ejemplo:

• el valor absoluto es idempotente. De hecho, ${displaystyle operatorname {abs} circ operatorname {abs} =operatorname {abs}$, eso es ${displaystyle operatorname {abs} (operatorname {abs} (x)=operatorname {abs} (x)}$ para todos ${displaystyle x}$;
• las funciones constantes son idempotentes;
• la función de identidad es idempotente;
• las funciones de piso, techo y parte fraccional son idempotentes;
• el subgrupo generado función del conjunto de poder de un grupo a sí mismo es idempotent;
• la función de casco convexo del conjunto de poder de un espacio afinal sobre los reinos a sí mismo es idempotente;
• el cierre y las funciones interiores del conjunto de energía de un espacio topológico a sí mismo son idempotentes;
• la estrella Kleene y Kleene más funciones del conjunto de poder de un monoide a sí mismo son idempotent;
• las endomorfismos idempotentes de un espacio vectorial son sus proyecciones.

Si el set ${displaystyle E}$ tiene ${displaystyle n}$ elementos, podemos dividirlo en ${displaystyle k}$ puntos fijos elegidos y ${displaystyle No.$ puntos no fijos bajo ${displaystyle f}$, y luego ${displaystyle k^{n-k}$ es el número de diferentes funciones idempotent. Por lo tanto, teniendo en cuenta todas las particiones posibles,

${displaystyle sum _{k=0} {n}{n}{n} {cHFF}$

es el número total de posibles funciones idempotentes en el conjunto. La secuencia entera del número de funciones idempotentes dada por la suma anterior para n = 0, 1, 2, 3, 4, 5, 6, 7, 8,... comienza con 1, 1, 3, 10, 41, 196, 1057, 6322, 41393,... (secuencia A000248 en el OEIS).

Ni la propiedad de ser idempotente ni la de no ser se conserva bajo la composición de la función. Como ejemplo para el primero, ${displaystyle f(x)=x}$ mod 3 y ${displaystyle g(x)=max(x,5)}$ son ambos idempotente, pero ${displaystyle fcirc g}$ no es, aunque ${displaystyle gcirc f}$ sucede que sí. Como ejemplo para este último, la función de negación ${displaystyle neg }$ en el dominio booleano no es idempotente, pero ${displaystyle neg circ neg }$ Lo es. Análogamente, negación siniestra ${displaystyle -(cdot)}$ de números reales no es idempotente, pero ${displaystyle -(cdot)circ -(cdot)}$ Lo es. En ambos casos, la composición es simplemente la función de identidad, que es idempotente.

Significado de informática

En informática, el término idempotencia puede tener un significado diferente según el contexto en el que se aplique:

• en programación imperativa, una subrutina con efectos secundarios es idempotente si múltiples llamadas a la subrutina tienen el mismo efecto en el estado del sistema como una sola llamada, en otras palabras si la función del espacio del estado del sistema a sí misma asociada con la subrutina es idempotente en el sentido matemático dado en la definición;
• en programación funcional, una función pura es idempotente si es idempotente en el sentido matemático dado en la definición.

Esta es una propiedad muy útil en muchas situaciones, ya que significa que una operación se puede repetir o reintentar tantas veces como sea necesario sin causar efectos no deseados. Con operaciones no idempotentes, el algoritmo puede tener que realizar un seguimiento de si la operación ya se realizó o no.

Ejemplos de informática

Una función que busca el nombre y la dirección de un cliente en una base de datos suele ser idempotente, ya que esto no hará que la base de datos cambie. De manera similar, una solicitud para cambiar la dirección de un cliente a XYZ normalmente es idempotente, porque la dirección final será la misma sin importar cuántas veces se envíe la solicitud. Sin embargo, la solicitud de un cliente para realizar un pedido normalmente no es idempotente, ya que varias solicitudes darán lugar a que se realicen varios pedidos. Una solicitud de cancelación de un pedido en particular es idempotente porque no importa cuántas solicitudes se realicen, el pedido permanece cancelado.

Una secuencia de subrutinas idempotentes donde al menos una subrutina es diferente de las demás, sin embargo, no es necesariamente idempotente si una subrutina posterior en la secuencia cambia un valor del que depende una subrutina anterior—la idempotencia no está cerrada bajo composición secuencial. Por ejemplo, suponga que el valor inicial de una variable es 3 y hay una secuencia de subrutinas que lee la variable, luego la cambia a 5 y luego la vuelve a leer. Cada paso en la secuencia es idempotente: ambos pasos que leen la variable no tienen efectos secundarios y el paso que cambia la variable a 5 siempre tendrá el mismo efecto sin importar cuántas veces se ejecute. No obstante, ejecutar la secuencia completa una vez produce la salida (3, 5), pero ejecutarla por segunda vez produce la salida (5, 5), por lo que la secuencia no es idempotente.

int x = 3;vacío leído() {} printf()"n", x); }vacío cambio() {} x = 5; }vacío secuencia() {} leído(); cambio(); leído(); }int principal() {} secuencia(); // impresiones "3n5n" secuencia(); // impresiones "5n5n" retorno 0;}

En el Protocolo de transferencia de hipertexto (HTTP), la idempotencia y la seguridad son los principales atributos que separan los métodos HTTP. De los principales métodos HTTP, GET, PUT y DELETE deben implementarse de manera idempotente de acuerdo con el estándar, pero POST no necesita serlo. GET recupera el estado de un recurso; PUT actualiza el estado de un recurso; y DELETE elimina un recurso. Como en el ejemplo anterior, la lectura de datos generalmente no tiene efectos secundarios, por lo que es idempotente (de hecho, nulipotente). La actualización y la eliminación de datos dados suelen ser idempotentes siempre que la solicitud identifique de forma única el recurso y solo ese recurso nuevamente en el futuro. PUT y DELETE con identificadores únicos se reducen al caso simple de asignación a una variable de un valor o un valor nulo, respectivamente, y son idempotentes por la misma razón; el resultado final es siempre el mismo que el resultado de la ejecución inicial, incluso si la respuesta difiere.

La violación del requisito de identificación única en el almacenamiento o la eliminación generalmente provoca la violación de la idempotencia. Por ejemplo, almacenar o eliminar un conjunto determinado de contenido sin especificar un identificador único: las solicitudes POST, que no necesitan ser idempotentes, a menudo no contienen identificadores únicos, por lo que la creación del identificador se delega al sistema receptor que luego crea un nuevo registro correspondiente. De manera similar, las solicitudes PUT y DELETE con criterios no específicos pueden generar diferentes resultados según el estado del sistema; por ejemplo, una solicitud para eliminar el registro más reciente. En cada caso, las ejecuciones posteriores modificarán aún más el estado del sistema, por lo que no son idempotentes.

En el procesamiento de flujo de eventos, la idempotencia se refiere a la capacidad de un sistema para producir el mismo resultado, incluso si el mismo archivo, evento o mensaje se recibe más de una vez.

En una arquitectura de carga-almacenamiento, las instrucciones que podrían causar una falla de página son idempotentes. Entonces, si ocurre una falla de página, el sistema operativo puede cargar la página desde el disco y luego simplemente volver a ejecutar la instrucción fallida. En un procesador en el que tales instrucciones no son idempotentes, tratar con errores de página es mucho más complejo.

Al reformatear la salida, se espera que la impresión bonita sea idempotente. En otras palabras, si la salida ya es "bonita", no debería haber nada que hacer con la impresora bonita.

En la arquitectura orientada a servicios (SOA), un proceso de orquestación de varios pasos compuesto en su totalidad por pasos idempotentes se puede reproducir sin efectos secundarios si alguna parte de ese proceso falla.

Muchas operaciones que son idempotentes a menudo tienen formas de "reanudar" un proceso si se interrumpe: formas que terminan mucho más rápido que comenzar todo desde el principio. Por ejemplo, reanudar una transferencia de archivos, sincronizar archivos, crear una compilación de software, instalar una aplicación y todas sus dependencias con un administrador de paquetes, etc.

Ejemplos aplicados

Un típico botón transversal es un ejemplo de un sistema idempotente

Ejemplos aplicados que muchas personas podrían encontrar en su vida cotidiana incluyen botones de llamada de ascensor y botones de paso de peatones. La activación inicial del botón mueve el sistema a un estado de solicitud, hasta que se satisface la solicitud. Las activaciones posteriores del botón entre la activación inicial y la satisfacción de la solicitud no tienen efecto, a menos que el sistema esté diseñado para ajustar el tiempo para satisfacer la solicitud en función del número de activaciones.