The decidability tag has no usage guidance.

**3**

votes

**1**answer

92 views

### Relationship between computational undecidability and axiomatic undecidability

On surface, these seem two completely different class of problems. One class represent statements which can't be proved or disproved in an axiomatic theory. For example
One can write down a ...

**4**

votes

**0**answers

216 views

### Is the two variable fragment of arithmetic, i.e., theory of ($\mathbb{N}, + ,\times$), decidable?

Any references would be appreciated. Most places only address different vocabularies (e.g. a survey of arithmetical definability by Bes).

**5**

votes

**1**answer

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

**13**

votes

**1**answer

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

**0**

votes

**0**answers

150 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 (...

**2**

votes

**1**answer

87 views

### Complexity of Deciding Feasibility of a system of linear inequalities over restricted variables

I am working out an interesting problem and would like some help with this particular sub problem:
Suppose we have a matrix $ M =\left\lbrace a_{ij}\right\rbrace $ of size $n\times m$ where $ a_{ij}\...

**4**

votes

**1**answer

298 views

### Show that the positive existential theory is undecidable

To show that the positive existential theory of $\mathbb{C}[t, e^{\lambda t} \mid \lambda \in \mathbb{C}]$ in the language $\{+, \cdot , ' , 0 , 1, t\}$ is undecidable we have to prove the following: $...

**19**

votes

**3**answers

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

**5**

votes

**0**answers

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

**7**

votes

**0**answers

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

**1**

vote

**1**answer

110 views

### Recurrence relations with polynomial coefficients: an undecidable problem

I read once (somewhere) that solving a recurrence relation with polynomial coefficients, in the general case, is an undecidable problem. I can't remember the exact reference and I've been trying to ...

**4**

votes

**0**answers

114 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, ...

**2**

votes

**0**answers

87 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 \...

**12**

votes

**0**answers

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

**0**

votes

**2**answers

150 views

### Undecidable set of problems [closed]

Is there some set of problems, for which determining if given problem is decidable or not is itself undecidable?

**-1**

votes

**1**answer

253 views

### Are limits decidable? Should definitions be decidable? [closed]

This question is about the Turing computability of the $\epsilon-N$ definition of a limit of an infinite sequence $S$. First, a proposition:
There cannot exist a Turing Machine $M$ which, given a ...

**1**

vote

**0**answers

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

**7**

votes

**1**answer

190 views

### Decidability of an Algebraic System in Real Numbers

Is there an algorithm to decide whether an algebraic system
\begin{gathered}
{f_1}({x_1}, \ldots ,{x_n}) = 0 \hfill \\
\vdots \hfill \\
{f_m}({x_1}, \ldots ,{x_n}) = 0 \hfill \\
\end{...

**2**

votes

**2**answers

167 views

### Pseudo-decision procedures for first order arithmetic

I was reading this paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.117.2911&rep=rep1&type=pdf in which the author describes an algorithm, based on Groebner basis, ...

**11**

votes

**0**answers

393 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 $x^3+y^...

**20**

votes

**2**answers

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

**2**

votes

**0**answers

44 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?

**3**

votes

**1**answer

232 views

### Is the equational theory of commutative vN regular rings decidable?

I wanted to check whether $A(x,y):=\frac{xy}{x+y}$ is an associative operation in every commutative vN regular ring. Now $A(-1,A(1,1))=A(-1,\frac{1}{2})=1\neq 0 =A(0,1)=A(A(-1,1),1)$. On the other ...

**11**

votes

**2**answers

958 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 "...

**6**

votes

**2**answers

170 views

### Algorithm for determining when polynomial iteration is bounded?

Let $f: \mathbb{Q}\to \mathbb{Q}$ be a polynomial map with rational coefficients. Let $p\in \mathbb{Q}^n$. Is there a known algorithm that given this data determines whether or not the iterates $f(p),...

**9**

votes

**2**answers

640 views

### Undecidable puzzles

There are plenty of popular NP-hard puzzles,
for example, generalized Sudoku ($n^2 \times n^2$-board), Flow (I cannot give a source for this), Minesweeper, etc.
Recently, I read a bit about aperiodic ...

**1**

vote

**0**answers

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

**4**

votes

**1**answer

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

**1**

vote

**0**answers

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

**2**

votes

**0**answers

133 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 $\mathbb{...

**4**

votes

**1**answer

150 views

### Decidability of a matrix product being the identity

Given a finite set $S$ of $n\times n$ integer matrices, it is known
that for $k\geq 3$ it is undecidable whether some product of them
(allowing repetitions) is the zero matrix (called the mortality
...

**4**

votes

**0**answers

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

**5**

votes

**2**answers

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

**0**

votes

**1**answer

172 views

### Can aperiodic tilings be non-hierarchical? and confusion over domino problem

Anyone experienced with the undecidability of aperiodic tiling?
It's related to the halting problem which Turing proved was undecidable in the 30's and basically superimposes tiles onto other tiles ...

**10**

votes

**2**answers

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

**21**

votes

**0**answers

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

**27**

votes

**3**answers

706 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, ...

**4**

votes

**1**answer

816 views

### Is compass and straight edge geometry complete?

Euclid's first three postulates are the basis of compass and straight edge constructions which are as complex as arithmetic.
The constructions themselves may be expressed as a formula with each of ...

**2**

votes

**1**answer

138 views

### Recognizing parallelogram tilings from their vertex set

Suppose I have a tiling of the plane with parallelograms where the sides of the parallelograms come from a specified finite set of vectors. If I only have access to the vertices of this tiling I may ...

**8**

votes

**1**answer

1k views

### Is the first-order theory (with =) of real numbers with addition and multiplication complete and decidable?

Due to Andreas Blass's answer to my question "Is the feasibility of a system of nonlinear, non-convex equations (inequalities) decidable?", i have now investigated real closed fields (RCF), because i ...

**2**

votes

**1**answer

187 views

### Is the feasibility of a system of nonlinear, non-convex equations (inequalities) decidable?

I would like to know whether the following problem is decidable.
Is the system
$x^T Q_i x + r_i = 0 \mbox{ for } i = 1, ..., k$
$x^T Q_j x + r_j \neq 0 \mbox{ for } j = k+1, ..., t$
feasible, ...

**2**

votes

**0**answers

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

**3**

votes

**2**answers

260 views

### Decide the limit of a decreasing sequence of real number

Given a bounded decreasing sequence of rational number $a_0,a_1,\cdots$, then we know that it has limit $a$. Suppose this sequence satisfy that $|a_k-a|<1/2^k$ for any $k$.
The sequence is given ...

**8**

votes

**1**answer

738 views

### Could the Jacobian conjecture be undecidable?

Most of us know the Jacobian conjecture. Here's a version below for fixed positive integers $d$ and $n$:
$J(d,n)$: If $f: C^n \rightarrow C^n$ is a polynomial map of degree $d$, and if the Jacobian ...

**27**

votes

**1**answer

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

**16**

votes

**3**answers

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

**7**

votes

**1**answer

339 views

### Decidability of periodic tilings of the plane

I'm interested in tilings of the plane by squares, with labels on the edges. It's well known that (1) the question "can one tile the plane with the following finite set of tiles?" is undecidable, and (...

**0**

votes

**1**answer

205 views

### Can one always Decide whether a Systems of Nonlinear Equations with Bilinear terms is Feasible?

I have come to a point in my PhD research were i need to prove that a particular decision procedure is decidable or not. And if i can solve the sub-problem described below, i shall have proved it. 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

**5**

votes

**2**answers

312 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=...