We consider computable functionals mapping the Baire space into the set of integers. By continuity, the value of the functional on a given function depends only on a "critical" finite part of this function. Care: there is in general no way to compute this critical finite part without querying the function on an arbitrarily larger finite part! Nevertheless, things are different in case there is a uniform bound on the size of the domain of this critical finite part. We prove that, modulo a quadratic blow-up of the bound, one can compute the value of the functional by an algorithm which queries the input function on a uniformly bounded finite part. Up to a constant factor, this quadratic blow-up is optimal. We also characterize such functionals in topological terms using uniformities. As an application of these results, we get a topological characterization of the dynamics of algorithms as modeled by Gurevich's Abstract State Machines.

We formalize the algorithms computing primitive recursive (PR) functions as the abstract state machines (ASMs) whose running length is computable by a PR function. Then we show that there exists a programming language (implementing only PR functions) by which it is possible to implement any one of the previously defined algorithms for the PR functions in such a way that their complexity is preserved.

It is well-known that Abstract State Machines (ASMs) can simulate ``step-by-step" any type of machines (Turing machines, RAMs, etc.). We aim to overcome two facts: 1) simulation is not identification, 2) the ASMs simulating machines of some type do not constitute a natural class among all ASMs. We modify Gurevich's notion of ASM to that of EMA (``Evolving MultiAlgebra") by replacing the program (which is a syntactic object) by a semantic object: a functional which has to be very simply definable over the static part of the ASM. We prove that very natural classes of EMAs correspond via ``literal identifications'' to slight extensions of the usual machine models and also to grammar models. Though we modify these models,we keep their computation approach: only some contingencies are modified. Thus, EMAs appear as the mathematical model unifying all kinds of sequential computation paradigms.

We extend Meyer and Ritchie's Loop language with higher-order procedures and procedural variables and we show that the resulting programming language (called Loop ω ) is a natural imperative counterpart of Gödel System T. The argument is two-fold: (1) we define a translation of the Loop ω language into System T and we prove that this translation actually provides a lock-step simulation, (2) using a converse translation, we show that Loop ω is expressive enough to encode any term of System T. Moreover, we define the “iteration rank” of a Loop ω program, which corresponds to the classical notion of “recursion rank” in System T, and we show that both translations preserve ranks. Two applications of these results in the area of implicit complexity are described.