Yeah, this is a little bit subtle. Please ignore the lack of rigor below, but this is my understanding: They aren't looking at a particular polynomial like 4x + 3y = 2. That has a solution x=2, y=-2, but they don't really care about the exact value for (x, y), just that it's integers. They're more interested in the parameters: (4, 3, 2), and in general Ax + By = C. If you like, it's almost like hyper parameter tuning: what are the parameter settings for (A, B, C) where I can get this shape of equation to "work", e.g. give me acceptable x and y? A "Diophantine set" is a family of parameters that all work. It turns out you can think of "parameters of a given shape of Diophantine equation" as an exotic programming paradigm.
Fermat: x^N + y^N = z^N. The Diophantine set only has the number N=2, because Fermat's Last Theorem tells us that no other possible N will work if x, y, z have to be integers. This is just a finite set.
Other polynomial expressions work with an infinite number of parameter settings: Pell's equation is x^2 - N*y^2 = 1. In this case, every N that is not a square will work. This is an infinite set.
Because a lot of the parameter sets are infinite like this, the size of the parameter set are instead measured using big-O notation. For Fermat's Last Theorem, {N=2} is constant, so big-O(1). For Pell's equation, {N not a square} is O(N). For other Diophantine expressions, the parameter settings are O(N^2), or O(2^N), or any other growth function you want that's achievable with Turing machines.
And this is the essence of what MRDP proved. Robinson, Davis, Putnam, and Matiyasevich over several papers proved that if you could encode a set that grew roughly like O(2^N), you also could encode any other computable set in the parameters. Approximately, demonstrating an exponentially-fast-growing family of parameters for some specific Diophantine problem was enough for Diophantine problems as a whole to be Turing complete. Matiyasevich's clinching discovery was a concrete example using the Fibonacci numbers.
In fact, according to the Esolang Wiki [https://esolangs.org/wiki/List_of_ideas#Mathematics] , Gregory Chaitin apparently has built a Diophantine equation whose parameters encode an entire Lisp interpreter.
Fermat: x^N + y^N = z^N. The Diophantine set only has the number N=2, because Fermat's Last Theorem tells us that no other possible N will work if x, y, z have to be integers. This is just a finite set.
Other polynomial expressions work with an infinite number of parameter settings: Pell's equation is x^2 - N*y^2 = 1. In this case, every N that is not a square will work. This is an infinite set.
Because a lot of the parameter sets are infinite like this, the size of the parameter set are instead measured using big-O notation. For Fermat's Last Theorem, {N=2} is constant, so big-O(1). For Pell's equation, {N not a square} is O(N). For other Diophantine expressions, the parameter settings are O(N^2), or O(2^N), or any other growth function you want that's achievable with Turing machines.
And this is the essence of what MRDP proved. Robinson, Davis, Putnam, and Matiyasevich over several papers proved that if you could encode a set that grew roughly like O(2^N), you also could encode any other computable set in the parameters. Approximately, demonstrating an exponentially-fast-growing family of parameters for some specific Diophantine problem was enough for Diophantine problems as a whole to be Turing complete. Matiyasevich's clinching discovery was a concrete example using the Fibonacci numbers.