The decidability tag has no usage guidance.

**20**

votes

**0**answers

392 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 ...

**12**

votes

**0**answers

163 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 ...

**11**

votes

**0**answers

362 views

### Decidability of $x^3+y^3+z^3 = c$

I wondering if it is known whether the following problem is algorithmically decidable or undecidable by Turing machines: given an integer c, determine if there are integers $(x,y,z)$ such that ...

**5**

votes

**0**answers

134 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 ...

**4**

votes

**0**answers

95 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 ...

**4**

votes

**0**answers

121 views

### Proving Richardson's theorem for constants

(I asked this a little over 3 months ago on math.SE, and when I initially re-asked here, no one had responded there. $\:$ After I re-asked here, Eric Towers responded there, since I had forgotten to ...

**4**

votes

**0**answers

100 views

### Undecidability of the existential theory

Do you know if I can find the proof that the existential theory of $\mathbb{Z}$ with the structure of addition , divisibility and the relation $(\exists s \in \mathbb{Z})m=np^s$ is undecidable, ...

**4**

votes

**0**answers

158 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 ...

**2**

votes

**0**answers

83 views

### Positive existential theory of $(\mathbb{Z}; +, |_n)$

I am reading a paper and there is the following theorem:
Let $n$ be a fixed integer, and $n >1$.
Denote divisibility in $\mathbb{Z}[\frac{1}{n}]$ by $|_n$, thus for
all $x, y \in ...

**2**

votes

**0**answers

43 views

### Decidability of first order theory of subclasses of posets

Is the first order theory of finite posets known to be undecidable?
Does anyone know a survey about such results?

**2**

votes

**0**answers

130 views

### What is the general feeling for Hilbert's 10th problem for Q?

We know that Hilbert's 10th problem for $\mathbb{Z}$ is undecidable. I was wondering whether there is a strong opinion in the mathematical community on the decidability of Hilbert's 10th for ...

**2**

votes

**0**answers

104 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 ...

**1**

vote

**0**answers

25 views

### Relation between indexed languages (OI-macro or context-free tree) and scattered context languages

I'm not sure about the relation between indexed languages (generated by indexed grammars--Aho) and scattered context languages (generated by
scattered context grammars--J Hopcroft).
I think that ...

**1**

vote

**0**answers

71 views

### What is the generic complexity of First Order Predicate Calculus?

I suspect that it should be the same as that of the Turing machine halting problem, which wikipedia gives as GenP and attributes this result to Hamkins and Miasnikov, but I am not sure. Is the generic ...

**1**

vote

**0**answers

82 views

### unique types and decidability

Suppose $\mathcal{M}$ is an infinite structure which has the property that every type that is realised is realised uniquely. Also assume that every element of $\mathcal{M}$ is definable but there is ...

**0**

votes

**0**answers

99 views

### Is the positive existential theory undecidable?

Could you tell if the positive existential theory of $\mathbb{C}[e^{\mu x} \mid \mu \in \mathbb{C}]$ is undecidable in the language $\{+, \cdot , \frac{d}{dx} , 0, 1, e^x\}$ ?
How can we prove the ...

**0**

votes

**0**answers

50 views

### Is the question whether a FO formula F has a model of size k (k is a finite number) decidable?

Hi all,
can someone please tell me whether the question whether a FO formula F has a model of size k (where k is a finite number) is decidable?
Thanks in advance!
TL