2
votes
1answer
139 views

Subsets of all Diophantine's sets

Function $\mathbb{N}^k \to \mathbb{N}^m$ is computable $\Leftrightarrow$ graph of function is Diophantine. Consider some subset $S$ of computable functions (for example some Grzegorczyk's class or ...
2
votes
1answer
44 views

A diophantine program for a basic For Loop

By Matiyasevich, every computable function has a diophantine representation. I am wondering if there is a general way to represent a simple iterative for loop. Specifically: Let $f(x)$ be any ...
0
votes
0answers
47 views

A diophantine definition of the Kleene star

Let $f(x \, | \, y_1, \dots, y_n)$ be a Diophantine polynomial that generates the Diophantine set $F$. By Matiyasevich, the set $F^*$ (Kleene star of $F$) is also Diophantine. My question: how can ...
1
vote
1answer
22 views

Show how the Diophantine sets are closed under concatenation.

It follows easily from Matiyasevich's Theorem that the Diophantine sets are closed under concatenation. I am trying to figure out the mechanism by which they are closed under concatenation. In other ...
2
votes
1answer
36 views

Which diophantine polynomials generate these diophantine sets?

Via Matiyasevich's Theorem, it is easy to prove that the following sets are diophantine: $\{k\}$ $\{0, 1, \dots, k-1, k+1, k+2, \dots \}$ $\{0, 1, \dots, k\}$ $\{k+1, k+2, \dots\}$ Number 1 is ...
2
votes
2answers
45 views

When is the complement of a diophantine set in the naturals also diophantine?

A diophantine polynomial is a (multivariable) polynomial with integer coefficients. If we write this polynomial as $p(x, y_1, \dots, y_n)$, then it defines the diophantine set $D_p = \{ x \in ...
1
vote
2answers
204 views

Solving an equation in modular arithmetic

Given $A, B, C$ positive integers, $B < C,$ I would like some thoughts about (possibly efficient) ways to find the smallest integer $X$, where $0 < X < C$, such that: $$A X + B \pmod{C - ...
1
vote
3answers
135 views

Does method exist to solve Diophantine/Algebraic equation with nearest integer variable?

Can anyone kindly tell me if there is a method (other than trial and error) to solve equations of the form below: $$x^2 + x - 35 - 35[(x^2)/35] = 0$$ where $x$ is an integer and $[y]$ denotes the ...
3
votes
2answers
421 views

Algorithm to determine if a Diophantine Equation has an infinite number of solutions

In their paper , Marker and Slaman, proved the decidability of the the theory of the natural numbers with the quantifier "for all but finitely many", One can obviously encode the question of whether ...
3
votes
1answer
341 views

Diophantine equation and Turing Machine

If a Diophantine equation is: exists v, p(x,v) = 0 (where v is a vector of finitely many integers) for some polynomial p, is there a Turing machine which prints out all values of x?