Conjecturally computable functions which unconditionally do not have any finite-fold Diophantine representation

Apoloniusz Tyszka

Abstract

We define functions f(1), f(2), g(1), g(2): N \ {0} -> N \ {0} and prove that they do not have any finite-fold Diophantine representation. We conjecture that if a system S subset of {x(i) + x(j) = x(k), x(1) . x(j) = x(k): i, j, k is an element of {1, ..., n}} has only finitely many solutions in positive integers x, then each such solution (x(1), ..., x(n)) satisfies x(1), ..., x(n) <= 2(2n-1). Assuming the conjecture, we prove: (1) the functions f(1), f(2), g(1), g(2) are computable, (2) there is an algorithm which takes as input a Diophantine equation, returns an integer, and this integer is greater than the heights of integer (non-negative integer, positive integer, rational) solutions if the solution set is finite, (3) a finite-fold Diophantine representation of the function N (sic) n -> 2(n) is an element of N does not exist, (4) if a set M subset of N is recursively enumerable but not recursive, then a finite-fold Diophantine representation of M does not exist. Conjecturally computable functions which unconditionally do not have any finite-fold Diophantine representation - ResearchGate.
Author Apoloniusz Tyszka (FoPaPE)
Apoloniusz Tyszka,,
- Faculty of Production and Power Engineering
Journal seriesInformation Processing Letters, ISSN 0020-0190, (A 15 pkt)
Issue year2013
Vol113
Pages719-722
Publication size in sheets0.5
Keywords in EnglishTheory of computation, Davis–Putnam–Robinson–Matiyasevich theorem, Diophantine equation with a finite number of solutions, Matiyasevichʼs conjecture on finite-fold Diophantine representations
DOIDOI:10.1016/j.ipl.2013.07.004
URL http://www.sciencedirect.com/science/article/pii/S0020019013001932
Internal identifierWIPiE/2013/87
Languageen angielski
Score (nominal)20
ScoreMinisterial score = 20.0, 26-07-2017, ArticleFromJournal
Ministerial score (2013-2016) = 20.0, 26-07-2017, ArticleFromJournal
Citation count*13 (2016-03-01)
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?