Means-fit effectivity

MaRDI QIDQ5011875zbMATH OpenFDO

Authors Yuri Gurevich

Publication date 30 August 2021

Full work available at URL https://arxiv.org/abs/2002.03145, http://bulletin.eatcs.org/index.php/beatcs/article/view/615/623

Mathematics Subject Classification ID

Logic in computer science (03B70) General topics in the theory of computing (68Q01) General topics in the theory of algorithms (68W01)

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-fitting effectivity, which is effectivity relative to the (physical or abstract) underlying machinery of the algorithm. This machinery varies from one class of algorithms to another. Think for example of ruler-and-compass algorithms, arithmetical algorithms, and Blum-Shub-Smale algorithms. We believe that means-fitting effectivity is meaningful and useful independently of the Church-Turing thesis. Means-fitting effectivity is definable, at least in the theory of abstract state machines (ASMs). The definition elucidates original effectivity as well. Familiarity with the ASM theory is not assumed. We tried to make the paper self-contained.

Recommendations

• Three paths to effectiveness
• A formalization and proof of the extended Church-Turing thesis (extended abstract)
• scientific article; zbMATH DE number 1869991
• Abstract effective models
• A Natural Axiomatization of Computability and Proof of Church's Thesis

Cited in

(3)

• Three paths to effectiveness
• scientific article; zbMATH DE number 1870122 (Why is no real title available?)
• Means-end relations and a measure of efficacy

This page was built for publication: Means-fit effectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5011875)