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 …

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 …

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 predi …

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$, …

Consider expressions built using number $1$, arithmetical operators $+, -, *, /$ and exponentiation ^ (in case of multiple values, the principal value is assumed, the same way as i …

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 …

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?" …

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 …

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$, t …

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 …

Gregory Chaitin has quoted Marcus du Sautoy to the effect that: If the Riemann Hypothesis (RH) is undecidable this implies that it's true, because if the RH were false it would …

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