Means-fit effectivity

Abstract

Historically, the notion of effective algorithm is closely related to the Church-Turing thesis. But effectivity imposes no restriction on computation time or any other resource; in that sense, it is incompatible with engineering or physics. We propose a natural generalization of it, means-fit effectivity, which is effectivity relative to the (physical or abstract) underlying machin- ery of the algorithm. This machinery varies from one class of algorithms to another. Think for example of ruler-and-compass algorithms, arithmeti- cal algorithms, and Blum-Shub-Smale algorithms. We believe that means-fit effectivity is meaningful and useful independently of the Church-Turing the- sis. Means-fit effectivity is definable, at least in the theory of abstract state machines (ASMs). The definition elucidates original effectivity as well. Fa- miliarity with the ASM theory is not assumed. We tried to make the paper self-contained.