Who said destroying the machine in the past? They could very well destroy it in the present, as well as the blue prints for it so it couldn't be rebuilt by someone else in the future. They can't change the past because it already happened, but they can very well change their future.

Granted, it would not destroy the problem of Ultimecia in the future, and could create another time loop...

Oh my, that Let's Play thread was the funniest thing ever!