# Tagged Questions

The tag has no usage guidance.

3k 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 ...
710 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, ...
476 views

### Decidability of equality of expressions built using 1,+,-,*,/,^

Consider expressions built using number $1$, arithmetical operators $+, -, *, /$ and exponentiation ^ (in case of multiple values, the principal value is assumed, the same way as it implemented in ...
423 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 ...
930 views

### What do you do if you believe a problem is undecidable?

While the title of this question is subjective, I hope to make what I'm looking for quite concrete. The first, and main question is this: If you believe that a problem you are working on is formally ...
672 views

### Is being rational decidable?

Given a real number uniquely defined by a finite system of equations and inequalities with rational coefficients involving the standard elementary functions only. Is it decidable whether this number ...
859 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 ...
476 views

### Is the isomorphism problem for amenable groups decidable?

Is it algorithmically decidable if two finitely presented amenable groups are isomorphic? Or slightly different: Does there exist a family of amenable groups (indexed by natural numbers) for which ...
1k 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?
1k 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 ...
344 views

### Is this theory decidable?

It is well-known that both Presburger arithmetic (by contrast with Peano arithmetic) and Tarski geometry are decidable. I was in the shower this morning and wondered whether there exists an elegant ...
188 views

### Is tightness decidable?

Given a contact structure on a three-manifold, is there an algorithm to decide whether or not it tight? For concreteness' sake, let's agree to represent the given contact three-manifold via an open ...
960 views

### Decidability of decidability

The questions I'm going to ask are non formal because they concern decidability of decidability, and I couldn't find any references on that after some quick searches. I hope that this thread is still "...
393 views

195 views

### Decidability of differential equations

Is there anything well-known about the algorithmic decidability of the satisfiability of an ODE $\dot{x}=f(x)$, $x: [0,1]\to R^n$ with an initial condition $x(0)=x_0$, given that $f(x)$ belongs to ...
313 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 (http://dl.acm.org/citation.cfm?id=...
169 views

### Deciding isomorphism between structures which interpret in the pure set

I am interested in the following decision problem: Given descriptions of two relational structures $A,B$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $A$ and $B$...
150 views

### List of finitely presented groups with undecidable word problem

Is there any reasonably updated list of (representative) examples of finitely presented groups with undecidable word problem? By "representative" I mean "avoiding obvious redundancy", i.e. examples ...
290 views

### Quantifier elimination vs decidability

Quantifier elimination is used as a technique to get decidability (e.g. $Th( \mathbb{N}, +)$ ) of theories, but typically one has to go over to some expansion. Are there examples of theories which are ...
298 views

87 views