# Tagged Questions

**4**

votes

**0**answers

119 views

### The theory of two finite linear orders

My colleague Matthias Baaz is looking for a reference for the following question (or possibly theorem):
Let T be the "theory of pairs of finite linear orders". That is, consider all finite ...

**9**

votes

**2**answers

311 views

### Is equivalence of functions built from nested exponentiations a decidable problem?

Let $\mathcal{E}$ be the minimal set of symbolic expressions (without any predefined meaning) such that
The symbol $x$ is in $\mathcal{E}$, and
If expressions $P,Q\in\mathcal{E}$, then the ...

**18**

votes

**0**answers

312 views

### Decidability of equality of elementary expressions

In the following definition the term expression is to be understood as a finite tree built from formal symbols without any predefined meaning assigned to them.
Define the set $\mathcal{E}$ of ...

**23**

votes

**3**answers

471 views

### Is the field of constructible numbers known to be decidable?

By the field of constructible numbers I mean the union of all finite towers of real quadratic extensions beginning with $\mathbb{Q}$. By decidable I mean the set of first order truths in this field, ...

**2**

votes

**0**answers

89 views

### Extend Lowenheim's decidability result to fragment of second-order logic

Since relational monadic first-order logic has finite model property, its SAT problem is decidable. In H.Behmann's paper, he extended this result to fragment of SOL where all predicates, free and ...

**4**

votes

**2**answers

259 views

### (Un)Decidability of the root existence problem for functions with bounded domain

The problem whether a real function $f$ has a root or not is undecidable, given that $f$ is from a class of functions including polynomials and the sine function ...

**28**

votes

**3**answers

2k views

### For which Millennium Problems does undecidable -> true?

Three good answers were received — by Alex Gavrilov, Bjørn Kjos-Hanssen, and Terry Tao — and the bounty has been awarded (somewhat arbitrarily) to Alex Gavrilov.
The answers ...

**15**

votes

**4**answers

752 views

### Proving univariate polynomials (defined by sums, binomial coeffs, etc.) are nonnegative: is it 'routine'?

My colleagues and I are working on a project related to an old paper of C. Borell and we have boiled it down to the following problem:
Show, for all integers $1 \leq i \leq k$, that the univariate ...

**13**

votes

**4**answers

994 views

### Decidability of tiling R^2

Does there exist a closed curve, with finite area and finite circumference, of which it is undecidable (in an axiomatic system where it is constructable) whether it can tile the plane?
I know the ...

**13**

votes

**6**answers

967 views

### Non-constructive proofs of decidability?

Are there examples of sets of natural numbers that are proven to be decidable but by non-constructive proofs only?