When are Two Algorithms the Same?

DOI10.2178/BSL/1243948484zbMATH Open1192.03021arXiv0811.0811OpenAlexW2169192695MaRDI QIDQ3633205FDOQ3633205

Authors: Andreas Blass, Nachum Dershowitz, Yuri Gurevich 

Publication date: 17 June 2009

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

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.

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

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

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)

Cites Work

• Linear logic
• Ordinary interactive small-step algorithms. I
• Sequential abstract-state machines capture sequential algorithms
• Title not available (Why is that?)
• Deductive systems and categories

Cited In (6)

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

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)