ELEMENTARY

El término elementary fue introducido originalmente por László Kalmár en el contexto de la teoría de la computabilidad. Él definió la clase de las funciones recursivas elementales como un subconjunto de las funciones recursivas primitivas — específicamente, aquellas que pueden computarse usando un conjunto limitado de operaciones como la composición, las sumas acotadas y los productos acotados. Estas funciones no crecen más rápido que una torre de exponenciación de altura fija. No todas las funciones recursivas primitivas son elementales; por ejemplo, la tetración crece demasiado rápido para ser incluida en la clase elemental. Las funciones recursivas elementales corresponden a la clase de la jerarquía de Grzegorczyk.