Apart from problems that specifically have to do with Turing machines, like "Simulate a Turing Machine with the given description", are there any problems that require Turing-complete potentially nonterminating recursion?

For example, are there any known non-Turing-machine-related problems that can't be solved in Coq?


closed as off-topic by Sasho Nikolov, Mohammad Al-Turkistany, Jan Johannsen, Kaveh, David Eppstein Aug 9 '16 at 20:34

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Sasho Nikolov, Mohammad Al-Turkistany, Jan Johannsen, Kaveh, David Eppstein
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Are you asking for examples of semi-decidable undecidable problems (i.e. a recursively-enumerable and not recursive language?) $\endgroup$ – JimN Jul 31 '16 at 21:30
  • 1
    $\begingroup$ Anything that tries to solve an undecidable problem: showing termination, proving theorems in first/higher-order logic, null pointer analysis... $\endgroup$ – cody Aug 1 '16 at 11:44

Given a system of polynomials with integer coefficients (Diophantine system), find a solution if there is one, or else run forever. Any program which does this must necessarily be partial because the set of solutions of Diophantine systems is a complete c.e. set, see Hilbert's tenth problem.


Not the answer you're looking for? Browse other questions tagged or ask your own question.