<p>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 <a href="https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem" rel="nofollow">Hilbert's tenth problem</a>.</p>

CC BY-SA 3.0
2016-08-01T16:50:05.433Z
2016-08-01T16:50:05.433Z
Andrej Bauer
<p>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?</p>

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

CC BY-SA 3.0
2016-07-31T21:30:14.080Z
Are you asking for examples of semi-decidable undecidable problems (i.e. a recursively-enumerable and not recursive language?)
JimN
CC BY-SA 3.0
2016-08-01T11:44:16.823Z
Anything that tries to solve an undecidable problem: showing termination, proving theorems in first/higher-order logic, null pointer analysis...
cody
<computability><turing-machines>
Are there any known problems that require potential nontermination to solve?
k_g
# Are there any known problems that require potential nontermination to solve?

(Asked by: username_0 on 2016-07-31)

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?

**Tags:** computability, turing-machines
> **Comments:**
> **username_1**: Are you asking for examples of semi-decidable undecidable problems (i.e. a recursively-enumerable and not recursive language?)  
> **username_2**: Anything that tries to solve an undecidable problem: showing termination, proving theorems in first/higher-order logic, null pointer analysis...  

---

## 1 answers

### Answer by username_3 on 2016-08-01. Score: 3 | Accepted answer

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](https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem).


---

