All Questions
9 questions
21
votes
1
answer
1k
views
Is "almost-solvability" of Diophantine equations decidable?
Say that a Diophantine equation is almost-satisfiable iff for each $n\in\mathbb{N}$ it has a solution mod $n$. Trivially genuine satisfiability over $\mathbb{N}$ implies almost-satisfiability, but the ...
- 21.2k
7
votes
0
answers
274
views
Is decidability reducible to unique decidability (perhaps in multilinear polynomial situations)?
Given a Diophantine equation it is not decidable if it has integer solution.
I. Is there a Diophantine set $\mathcal D_{unique}$ satisfying the properties
every member in $\mathcal D_{unique}$ is a ...
- 13.9k
3
votes
0
answers
186
views
Decidable equality for computable functions $\mathbb{N}\to\mathbb{N}$
Suppose we have two computable functions $f, g:\mathbb{N}\to\mathbb{N}$. When is $f=g$ algorithmically decidable?
For example it is decidable if $f$ and $g$ are polynomials of a priori known degree.
- 31
9
votes
0
answers
346
views
Is Videla's solution of Hilbert's tenth problem for rational functions over field of characteristic 2 wrong?
The paper in question.
Quick introduction to the problem: suppose that $F$ is a finite field of characteristic 2
(for purposes of this post $F = \mathbb{F}_2$ will suffice) and let $F[t]$ and $F(t)$ ...
- 543
3
votes
1
answer
209
views
How does the minimal size of a rational solution to a system of polynomial equations depend on parameters?
The undecidability of Hilbert's tenth problem implies the following (there is a stronger statement here, Theorem 9):
For any computable function $f$, there is a family of integer polynomials (where ...
- 934
17
votes
0
answers
808
views
Decidability of $x^3+y^3+z^3 = c$
I wondering if it is known whether the following problem is algorithmically decidable or undecidable by Turing machines: given an integer c, determine if there are integers $(x,y,z)$ such that $x^3+y^...
- 171
24
votes
1
answer
1k
views
Are sums of sequences decidable?
Suppose that $f,g$ are rational functions with integer coefficients such that $\sum_{n=0}^{\infty}f(n)$ and $\sum_{n=0}^{\infty}g(n)$ both converge. Is it decidable whether
$\sum_{n=0}^{\infty}f(n)=\...
49
votes
5
answers
5k
views
Are the two meanings of "undecidable" related?
I am usually confused by questions of the type "could such and such a problem be undecidable", because as far as I know there are two distinct possible meanings of "undecidable". ...
- 18.7k
3
votes
2
answers
912
views
Why is every finite set Diophantine? [closed]
I understand that every finite set is recursively enumerable, as I see that one could just encode each element of some finite set on a Turing Machines tape, and then have the machine check each member ...
