# Questions tagged [decidability]

The tag has no usage guidance.

76 questions
Filter by
Sorted by
Tagged with
150 views

### Help understand why FOL wff are enumerable, but FOL is undecidable

I am very new to this. I am trying to understand some basics about what kinds of enumerations in FOL are possible, and which are not. If you accept that FOL is defined in terms of a finite number of ...
1k views

### Can you see that the Linz Halting Problem proof contains a fatal flaw?

Applying a Simulating Halt Decider to the Linz Halting Problem Proof When a simulating halt decider correctly simulates N steps of its input it derives the exact same N steps that a pure UTM would ...
1 vote
376 views

94 views

### Tenth Hilbert problem on interval arithmetic

What is the decidability status of Hilbert's Tenth problem interpreted over interval arithmetic? In details, let $p\in\mathbb{Q}[x_1,\ldots,x_n]$ be a Diophantine polynomial. The problem is that of ...
It is well-known that polynomial diophantine equations are undecidable (Hilbert's 10th problem): that is, given a quantifier-free formula over the language $\{=, +, \cdot, 1\}$ (of equality, addition, ...