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

DOI10.1016/j.ipl.2013.07.004zbMath1285.11147MaRDI QIDQ2445235

Apoloniusz Tyszka

Publication date: 14 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2013.07.004

zbMATH Keywords

theory of computation; Davis-Putnam-Robinson-Matiyasevich theorem; Diophantine equation with a finite number of solutions; Diophantine representations; Matiyasevich's conjecture on finite-fold

Mathematics Subject Classification ID

11U05: Decidability (number-theoretic aspects)

11D45: Counting solutions of Diophantine equations

03D80: Applications of computability and recursion theory

Related Items

All Functions $$g: \mathbb{N} \rightarrow \mathbb{N}$$ Which have a Single-Fold Diophantine Representation are Dominated by a Limit-Computable Function $$f: \mathbb{N}\setminus \{0\} \rightarrow \mathbb{N}$$ Which is Implemented in MuPAD and Whose Computability is an Open Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards finite-fold Diophantine representations
• On the Number of Solutions of Diophantine Equations
• An algorithm which transforms any Diophantine equation into an equivalent system of equations of the forms x_i=1, x_i+x_j=x_k, x_i \cdot x_j=x_k
• A conjecture on integer arithmetic which implies that there is an algorithm which to each Diophantine equation assigns an integer which is greater than the heights of integer (non-negative integer, rational) solutions, if these solutions form a finite set