Generating the greatest common divisor, and limitations of primitive recursive algorithms

Research output: Contribution to journalArticle

Abstract

The greatest common divisor of two integers cannot be generated in a uniformly bounded number of steps from those integers using arithmetic operations. The proof uses an elementary model-theoretic construction that enables us to focus on "integers with transcendental ratio." This unboundedness result is part of the solution of a problem posed by Y. Moschovakis on limitations of primitive recursive algorithms for computing the greatest common divisor function.

Original languageEnglish (US)
Pages (from-to)297-324
Number of pages28
JournalFoundations of Computational Mathematics
Volume3
Issue number3
DOIs
StatePublished - Dec 1 2003

ASJC Scopus subject areas

  • Analysis
  • Computational Mathematics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Generating the greatest common divisor, and limitations of primitive recursive algorithms'. Together they form a unique fingerprint.

  • Cite this