In fact no such algorithm exists as was shown by Yuri Matijasevic in 1970. In an interview in D J Albers, G I Alexanderson and C Reid, More mathematical people (Harcourt, Brace, Jovanovich, 1990) Julia Robinson talks about her obsession with Hilbert's Tenth Problem:
Throughout the 1960s, while publishing a few papers on other things, I kept working on the Tenth Problem, but I was getting rather discouraged. For a while I ceased to believe in the Robinson hypothesis, although Raphael [my husband] insisted that it was true but just too difficult to prove. I even worked in the opposite direction, trying to show that there was a positive solution to Hilbert's problem, but I never published any of that work. It was the custom in our family to have a get-together for each family member's birthday. When it came time for me to blow out the candles on my cake, I always wished, year after year, that the Tenth Problem would be solved - not that I would solve it, but just that it would be solved. I felt that I couldn't bear to die without knowing the answer.
Finally - on February 15, 1970 - Martin telephoned me from New York to say that John Cocke had just returned from Moscow with the report that a 22-year-old mathematician in Leningrad had proved that the relation n = F2m , where F2m is a Fibonacci number, is diophantine. This was all that we needed. It followed that the solution to Hilbert's tenth problem is negative - a general method for determining whether a given diophantine equation has a solution in integers does not exist.
Just one week after I had first heard the news from Martin, I was able to write to Matijasevic:
... now I know it is true, it is beautiful, it is wonderful. If you really are 22 [he was], I am especially pleased to think that when I first made the conjecture you were a baby and I just had to wait for you to grow up!That year when I went to blow out the candles on my cake, I stopped in mid-breath, suddenly realizing that the wish I had made for so many years had actually come true.
I have been told that some people think that I was blind not to see the solution myself when I was so close to it. On the other hand, no one else saw it either. There are lots of things, just lying on the beach as it were, that we don't see until someone else picks one of them up. Then we all see that one.
In 1971 Raphael and I visited Leningrad and became acquainted with Matijasevic and with his wife, Nina, a physicist. At that time, in connection with the solution of Hilbert's problem and the role played in it by the Robinson hypothesis, Linnik told me that I was the second most famous Robinson in the Soviet Union, the first being Robinson Crusoe.