The tag has no usage guidance.

learn more… | top users | synonyms

31
votes
3answers
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 ...
27
votes
3answers
705 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, ...
27
votes
1answer
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 ...
21
votes
0answers
420 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 ...
20
votes
2answers
929 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 ...
19
votes
3answers
665 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 ...
17
votes
4answers
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 ...
16
votes
3answers
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 ...
14
votes
6answers
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?
13
votes
4answers
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 ...
13
votes
1answer
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 ...
12
votes
0answers
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 ...
11
votes
2answers
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 "...
11
votes
0answers
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^...
10
votes
2answers
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 ...
9
votes
2answers
423 views

Decidability in Groups

This is not my area of research, but I am curious. Let $G=\left< X|R \right>$ be a finitely presented group, where $X$ and $R$ are finite. There are many questions which are undecidable for all ...
9
votes
2answers
638 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 ...
8
votes
1answer
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 ...
8
votes
2answers
662 views

Are there standard examples of stable theories that are undecidable?

What is known about decidability of various first order theories studied in stable model theory, geometric model theory, o-minimality? For example, is there a natural example of an undecidable first ...
8
votes
1answer
277 views

Algorithmic decidability of equality in the ring of periods

Suppose two elements of the ring of periods are given by their systems of polynomial inequalities with rational coefficients. Is there a known algorithm deciding their equality? Is it known if their ...
8
votes
1answer
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 ...
7
votes
1answer
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 (...
7
votes
1answer
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{...
7
votes
0answers
230 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 ...
6
votes
2answers
354 views

showing the subgroup membership problem is undecidable for $F_2 \times F_2$

Let $F_2$ denote the free group of rank 2. Does anybody have a fast proof that the subgroup membership problem is undecidable for $F_2 \times F_2$? I saw a really fast proof last semester that ...
6
votes
3answers
735 views

Decidability of matrix algebra

Take multi-sorted first-order logic with equality, complex scalars, 1xn vectors, nx1 vectors, nxn matrices, addition and multiplication for each pair of sorts they make sense for, and hermitian ...
6
votes
2answers
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),...
5
votes
2answers
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 ...
5
votes
2answers
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=...
5
votes
1answer
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$...
5
votes
0answers
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 ...
4
votes
1answer
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 ...
4
votes
1answer
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: $...
4
votes
1answer
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 ...
4
votes
1answer
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
0answers
215 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).
4
votes
0answers
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, ...
4
votes
0answers
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 ...
3
votes
2answers
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 ...
3
votes
1answer
88 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 ...
3
votes
1answer
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 ...
2
votes
2answers
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, ...
2
votes
1answer
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 ...
2
votes
1answer
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
1answer
86 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}\...
2
votes
0answers
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 \...
2
votes
0answers
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?
2
votes
0answers
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{...
2
votes
0answers
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 ...
1
vote
1answer
109 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 ...