JoshuaZ comments on Which fields of learning have clarified your thinking? How and why? - Less Wrong

12 [deleted] 11 November 2011 01:04AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (64)

You are viewing a single comment's thread. Show more comments above.

Comment author: JoshuaZ 12 November 2011 01:51:51PM *  2 points [-]

Yes, Hilbert's 10th Problem was whether there was an algorithm for solving whether a given Diophantine equation has solutions over the integers. The answer turned out to be "no" and the proof (which took many years) in some sense amounted to showing that one could for any Turing machine and starting tape make a Diophantine equation that has a solution iff the Turing machine halts in an accepting state. Some of the results and techniques for doing that can be used to show that other classes of problems can model Turing machines, and that's the context that Matiyasevich discusses it.