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 Agnieszka Peszek (FoPaPE / IoAEaI)
Agnieszka Peszek,,
- Institute of Agricultural Engineering and Informatics
, Apoloniusz Tyszka (FoPaPE)
Apoloniusz Tyszka,,
- Faculty of Production and Power Engineering
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
URL https://www.info.uaic.ro/wp-content/uploads/2019/09/XXIX1_3-2.pdf
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
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?