The decidability tag has no wiki summary.

**20**

votes

**0**answers

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

**11**

votes

**0**answers

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

**4**

votes

**0**answers

156 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

42 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

16 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

69 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

49 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