## On the Relationship Between Matiyasevich's and Smoryński's Theorems

### Agnieszka Peszek , Apoloniusz Tyszka

#### Abstract

Let R be a non-zero subring of Q with or without 1. We assume that for every positive integer there exists a computable surjection from N onto Rn. Every R ∈{Z,Q} satisfies these conditions. Matiyasevich’s theorem states that there is no algorithm to decide whether or not a given Diophantine equation has a solution in non-negative integers. Smory ́nski’s theorem states that the set of all Diophantine equations which have at most finitely many solutions in non-negative integers is not recursively enumerable. We prove:(1)Smory ́nski’s theorem easily follows from Matiyasevich’s theorem,(2)Hilbert’s Tenth Problem for solutions in Rhas a positive solution if and only if the set of all Diophantine equations with a finite number of solutions in Risrecursively enumerable. “Hilbert’s Tenth Problem for solutions in R”is the problem of whether there exists an algorithm which for any given Diophantine equation with integer coefficients, can decide whether the equation has a solution with all unknowns taking values in R.Author | |||||

Journal series | Scientific Annals of Computer Science, ISSN 1843-8121, e-ISSN 2248-2695, (N/A 20 pkt) | ||||

Issue year | 2019 | ||||

Vol | 29 | ||||

No | 1 | ||||

Pages | 101-111 | ||||

Publication size in sheets | 0.5 | ||||

Keywords in English | computable set, Davis-Putnam-Robinson-Matiyasevich theorem, Diophantine equation which has at most finitely many solutions, Hilbert’s Tenth Problem for solutions in a subring of Q, Matiya-sevich’s theorem, recursively enumerable set, Smorynski ’s theorem. | ||||

ASJC Classification | ; | ||||

DOI | DOI:10.7561/SACS.2019.1.101 | ||||

URL | https://www.info.uaic.ro/wp-content/uploads/2019/09/XXIX1_3-2.pdf | ||||

Language | en angielski | ||||

License | Journal (articles only); author's original; ; after publication | ||||

File |
| ||||

Score (nominal) | 20 | ||||

Score source | journalList | ||||

Publication indicators | : 2018 = 0.395 | ||||

Citation count* |

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.

Back