On subrings R of Q for which HTP for solutions in R has a positive solution if and only if the set of all Diophantine equations with a finite number of solutions in R is recursively enumerable

Download Edit this record How to cite View on PhilPapers
Abstract
Let R be a subring of Q with or without 1, and let for every positive integer n there exists a computable surjection from N onto R^n. 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 R has a positive solution if and only if the set of all Diophantine equations with a finite number of solutions in R is recursively enumerable.
Categories
PhilPapers/Archive ID
PESOSR
Revision history
Archival date: 2019-04-15
View upload history
References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Added to PP index
2019-04-15

Total views
3 ( #39,607 of 38,850 )

Recent downloads (6 months)
3 ( #37,900 of 38,850 )

How can I increase my downloads?

Monthly downloads since first upload
This graph includes both downloads from PhilArchive and clicks to external links.