Comment by jkramar

There won't always be a proof. If there always was, you could programmatically find it via brute-force search and solve the halting problem.