Timeline for Undecidability of Diophantine equations with disjoint variables?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 1, 2017 at 9:38 | comment | added | Liam_math | @ErfanKhaniki, joro means that deciding whether $F(\vec{y})=0$ has a solution. Your statement of the Hilbert 10th problem is clearly correct. The question here is whether the undecidability stands when $f$ and $g$ have disjoint sets of variables. | |
| Jun 1, 2017 at 0:42 | comment | added | Erfan Khaniki | @joro: What do you mean by "$F(\vec{y})=0$ be undecidable"? The undecidability of the Hilbert 10th problem means there is no Turing machine that decides correctly for every two polynomials $f$ and $g$ with positive coefficients whether $f=g$ has a solution in natural numbers or not. | |
| May 31, 2017 at 16:04 | comment | added | Liam_math | Let us continue this discussion in chat. | |
| May 31, 2017 at 15:30 | comment | added | joro | @Liam_math I am not sure about the restriction to naturals. Maybe sum of 4 squares is just one step. | |
| May 31, 2017 at 15:23 | vote | accept | Liam_math | ||
| May 31, 2017 at 15:23 | comment | added | Liam_math | many thanks. I figured out myself so deleted the comment. Thanks anyway. But I am still puzzled by this natural number restriction. I do not see how the sum of 4 squares works. | |
| May 31, 2017 at 14:40 | comment | added | joro | @Liam_math for $-2x+4$ the reduction is $(v+2)^2+(vx+4)^2=0$ which forces $v= -2$. | |
| May 31, 2017 at 14:03 | comment | added | Liam_math | For the requirement that each variable is in natural numbers, the reduction probably does not work, because $f(\vec{x})=0$ cannot have a solution in natural numbers if all coefficients of $f$ are positive. Again, please correct me. | |
| May 31, 2017 at 13:28 | comment | added | joro | @Liam_math from $-2x^3y$ I get $(v_1+2)^2+(v_1x^3 y)^2$. For naturals probably every variable should be replaced by sum of 4 squares. | |
| May 30, 2017 at 20:58 | comment | added | Liam_math | Moreover, this answer is nice, but what I meant to ask is whether $f(\vec{x})=g(\vec{y})$ has a solution in natural numbers (my apology!) In this case, is the problem still undecidable? | |
| May 30, 2017 at 20:51 | comment | added | Liam_math | Thanks. I am not clear about the part "get F from F'". For instance, from -2x^3y, what do you obtain? | |
| May 30, 2017 at 16:18 | history | edited | joro | CC BY-SA 3.0 |
added 70 characters in body
|
| May 30, 2017 at 15:51 | history | answered | joro | CC BY-SA 3.0 |