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

Fingerprint

Highest common factor
Recursive Algorithm
Integer
Divisor Function
Transcendental
Computing
Model

ASJC Scopus subject areas

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

Cite this

Generating the greatest common divisor, and limitations of primitive recursive algorithms. / van den Dries, Lou.

In: Foundations of Computational Mathematics, Vol. 3, No. 3, 01.12.2003, p. 297-324.

Research output: Contribution to journalArticle

@article{f99207f0c6f2472daa5bbf62d9390f60,
title = "Generating the greatest common divisor, and limitations of primitive recursive algorithms",
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.",
author = "{van den Dries}, Lou",
year = "2003",
month = "12",
day = "1",
doi = "10.1007/s10208-002-0061-y",
language = "English (US)",
volume = "3",
pages = "297--324",
journal = "Foundations of Computational Mathematics",
issn = "1615-3375",
publisher = "Springer New York",
number = "3",

}

TY - JOUR

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

AU - van den Dries, Lou

PY - 2003/12/1

Y1 - 2003/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=21144456492&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21144456492&partnerID=8YFLogxK

U2 - 10.1007/s10208-002-0061-y

DO - 10.1007/s10208-002-0061-y

M3 - Article

AN - SCOPUS:21144456492

VL - 3

SP - 297

EP - 324

JO - Foundations of Computational Mathematics

JF - Foundations of Computational Mathematics

SN - 1615-3375

IS - 3

ER -