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 seriesScientific Annals of Computer Science, ISSN 1843-8121, e-ISSN 2248-2695, (N/A 20 pkt)
Issue year2019
Vol29
No1
Pages101-111
Publication size in sheets0.5
Keywords in Englishcomputable 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 Classification1700 General Computer Science; 2604 Applied Mathematics
DOIDOI:10.7561/SACS.2019.1.101
Languageen angielski
LicenseJournal (articles only); author's original; Uznanie Autorstwa - Bez Utworów Zależnych (CC-BY-ND); after publication
File
 On the Relationship Between Matiyasevich's and Smoryński's Theorems of 04-11-2019 326,13 KB
Score (nominal)20
Score sourcejournalList
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2018 = 0.395
Citation count*
 Cite