论文标题
平均拟合有效性
Means-fit effectivity
论文作者
论文摘要
从历史上看，有效算法的概念与教会论文密切相关。但是有效性对计算时间或任何其他资源没有任何限制；从这个意义上讲，它与工程或物理学不兼容。我们提出了它的自然概括，均值拟合的有效性，这是相对于（物理或抽象）算法的（物理或抽象）机械的有效性。该机械从一类算法到另一种算法不等。例如，想想尺子和混合算法，算术算法和蓝光算法。我们认为，拟合的有效性是有意义的，并且独立于教会论文。均值拟合效率是可以定义的，至少在抽象状态机理论（ASM）的理论中。该定义也阐明了原始效果。不假定对ASM理论的熟悉。我们试图使纸张独立。
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.
