When are Two Algorithms the Same?

DOI10.2178/BSL/1243948484MaRDI QIDQ3633205zbMATH OpenOpenAlexFDO

Authors Andreas Blass, Nachum Dershowitz, Yuri Gurevich

Publication date 17 June 2009

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0811.0811

zbMATH Keywords

algorithmChurch-Turing thesis

Mathematics Subject Classification ID

General topics in the theory of algorithms (68W01) Computability and recursion theory (03D99) General topics in the theory of computing (68Q01)

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.

Recommendations

• Towards a definition of an algorithm
• scientific article; zbMATH DE number 2155189
• scientific article; zbMATH DE number 1687041
• scientific article; zbMATH DE number 3934392
• Algorithms and the mathematical foundations of computer science

Cites work

• scientific article; zbMATH DE number 1226875 (Why is no real title available?)
• Deductive systems and categories
• Linear logic
• Ordinary interactive small-step algorithms. I
• Sequential abstract-state machines capture sequential algorithms

Cited in

(6)

• Galois theory of algorithms
• When Are Two Gossips the Same?
• 2011 North American Annual Meeting of the Association for Symbolic Logic, University of California at Berkeley, Berkeley, CA, USA, March 24--27, 2011
• Predicativity, the Russell-Myhill paradox, and Church's intensional logic
• Semantics-to-Syntax Analyses of Algorithms
• Towards a definition of an algorithm

This page was built for publication: When are Two Algorithms the Same?

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