When are two algorithms the same?

, &
Bulletin of Symbolic Logic 15 (2):145-168 (2009)
  Copy   BIBTEX

Abstract

People usually regard algorithms as more abstract than the programs that implement them. The natural way to formalize this idea is that algorithms are equivalence classes of programs with respect to a suitable equivalence relation. We argue that no such equivalence relation exists

Categories

Keywords

Reprint years

DOI

10.2178/bsl/1243948484

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 106,126

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Classes of Markov-like k-ALGORITHMS.Zdzislaw Grodzki & Jerzy Mycka - 1996 - Reports on Mathematical Logic:83-99.
A polynomial time algorithm for determining Dag equivalence in the presence of latent variables and selection bias.Peter Spirtes - unknown
Review: V. K. Detlovs, The Equivalence of Normal Algorithms and Recursive Functions. [REVIEW]E. M. Fels - 1962 - Journal of Symbolic Logic 27 (3):362-362.
Measuring power of algorithms, computer programs and information automata.Mark Semenovich Burgin (ed.) - 2010 - New York: Nova Science Publishers.
Classifying positive equivalence relations.Claudio Bernardi & Andrea Sorbi - 1983 - Journal of Symbolic Logic 48 (3):529-538.
that B is Turing reducible to A and write B≤ T A. We say that B≡ T A if B≤ T A and A≤ T B.≡ T is an equivalence relation, and≤ T induces a par-tial ordering on the corresponding equivalence classes; the poset obtained in this way is called the degrees of unsolvability, and elements of this poset are called degrees. [REVIEW]J. Knight, A. Kucera & R. Shore - 1995 - Bulletin of Symbolic Logic 1 (2).
Thin equivalence relations and effective decompositions.Greg Hjorth - 1993 - Journal of Symbolic Logic 58 (4):1153-1164.
Review: Andreas Blass, Near Coherence of Filters, I: Cofinal Equivalence of Models of Arithmetic. [REVIEW]H. B. Enderton - 1993 - Journal of Symbolic Logic 58 (1):350-350.
On Polynomial-Time Relation Reducibility.Su Gao & Caleb Ziegler - 2017 - Notre Dame Journal of Formal Logic 58 (2):271-285.

Analytics

Added to PP
2010-09-13

Downloads
75 (#302,572)

6 months
6 (#723,794)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

What is a Simulation Model?Juan M. Durán - 2020 - Minds and Machines 30 (3):301-323.

View all 23 citations / Add more citations

References found in this work

Add more references