45
votes
Two (probably) equal real numbers which are not proved to be equal?
Thomson’s problem for $n = 7$ provides a nice example:
$$\min_{x_1, \ldots, x_7 \in \mathbb{S}^2} \sum_{i=1}^7 \sum_{j = i + 1}^7 \frac{1}{|x_i - x_j|} = \frac{1}{2} + 10 \frac{1}{\sqrt{2}} + 5\sqrt{\...
Community wiki
38
votes
Accepted
Is it decidable to check if an element has finite order or not?
A finitely presented group with decidable word problem and undecidable order problem is in McCool, James
Unsolvable problems in groups with solvable word problem.
Canad. J. Math. 22 1970 836–838.
34
votes
Accepted
Are there any undecidability results that are not known to have a diagonal argument proof?
Let me propose a candidate: Kolmogorov complexity is not computable.
That is, there is no computable procedure that, given a finite sequence $s$, produces the size of the smallest program (with ...
27
votes
Accepted
Is "almost-solvability" of Diophantine equations decidable?
A Diophantine equation is almost-satisfiable iff it is satisfiable over the ring $\widehat{\mathbb Z}$, the profinite completion of $\mathbb Z$ (also called by some the Prüfer ring), by a standard ...
Community wiki
23
votes
Accepted
Is there a ring for which the reducibility of a polynomial is undecidable?
Yes, but the answer is a bit unsatisfying. This answer is a summary of the very nice paper Computable Fields and Galois Theory, Russel Miller, Notices of the AMS, 2008.
First of all, if one could not ...
23
votes
Accepted
Is irreducibility of polynomials $\in \mathbb{Z} [X]$ over $\mathbb{Q}$ an undecidable problem?
There is a polynomial-time algorithm that decomposes any non-zero polynomial in $\mathbb{Q}[X]$ into irreducible factors. The algorithm is due to Lenstra–Lenstra–Lovász (Factoring Polynomials with ...
23
votes
Is irreducibility of polynomials $\in \mathbb{Z} [X]$ over $\mathbb{Q}$ an undecidable problem?
There is a quick way to see that this is decidable (with terrible complexity). Let $h(x) \in \mathbb{Z}[x]$ have degree $d$. Evaluate $h$ at $d+1$ points $u_1$, $u_2$, ..., $u_{d+1}$. If any of the $h(...
22
votes
Are there any undecidability results that are not known to have a diagonal argument proof?
From a point of view your question relates to an "open conjecture" in computability theory.
I think you are asking if there is a specific problem $P$, which can be shown to be undecidable, ...
21
votes
Is it decidable to check if an element has finite order or not?
The decidability of the word problem does not imply the decidability of the order problem, and in fact the following more general result holds.
Theorem. Let $\mathbf{a}, \, \mathbf{b}, \, \mathbf{c}...
21
votes
Accepted
Two (probably) equal real numbers which are not proved to be equal?
As mentioned in another MO question,
Gourevitch's conjecture is a nice example:
$$\sum_{n=0}^\infty \frac{1+14n+76n^2+168n^3}{2^{20n}}\binom{2n}{n}^7 = \frac{32}{\pi^3}.$$
Community wiki
20
votes
Are there any undecidability results that are not known to have a diagonal argument proof?
Too long to be a comment: Joel's Kolmogorov complexity argument contains what I would consider to be a diagonalization. Here is an essentially equivalent argument which makes the diagonalization more ...
18
votes
Accepted
Why don't Zeilberger and Gosper's algorithms contradict Richardson's theorem?
(Comment turned into an answer:)
It's as simple as "the composition of hypergeometric terms is not hypergeometric". $f(n)=2^n$ is a hypergeometric term because $\frac{f(n+1)}{f(n)}=2$ is a ...
17
votes
Accepted
Is solvability semi-decidable?
The Adian–Rabin theorem, although it is not usually stated like this, says that Markov properties are not co-semi-decidable, thus « not being metabelian » or « not being solvable » are not semi-...
16
votes
Is (Z,+,0,1,P2,P3) decidable?
Christian Schulz (a grad student at Urbana) and Philipp Hieronymi have recently shown that $(\mathbb{Z},+,<,2^{\mathbb{N}},3^{\mathbb{N}})$ is undecidable. And I believe they prove this for $(\...
16
votes
Are omega-consistent extensions of PA always consistent with each other?
$\def\pa{\mathrm{PA}}\def\N{\mathbb N}\DeclareMathOperator\Th{Th}\def\pri{\mathrm{Pr}_1}\def\code#1{\ulcorner#1\urcorner}$The answer is no: in fact, there are sentences $A$ such that $\pa+A$ and $\pa+\...
16
votes
Two (probably) equal real numbers which are not proved to be equal?
The conjectures on special values of $L$-functions provide a lot of examples. For example, David Boyd conjectured in his celebrated paper that the Mahler measure of the Laurent polynomial $P_k(x,y)=x+\...
Community wiki
16
votes
Two (probably) equal real numbers which are not proved to be equal?
The moving sofa constant is conjectured to be 2.2195..., which is computable as the implicit solution of a set of equations (see Eqs. 1-4 in Romik 2018). On the other hand, while not immediately ...
Community wiki
16
votes
Accepted
Parity of number of solutions to Diophantine equations
While it’s unclear what you mean by “parity” when the number of solutions is infinite, all such questions have been answered by M. Davis, On the number of solutions of Diophantine equations, Proc. AMS ...
16
votes
Accepted
Are 100% of statements undecidable, in Gödel's numbering?
This is going to depend sensitively on your exact choice of Gödel number, and the limit will often not be defined. Pick your favorite very short undecidable statement S. Then for any statement A, you ...
15
votes
Undecidable easy arithmetical statement
The "mortal matrix" problem: Given a set of $n\times n$-matrices with integer entries, decide whether they can be multiplied, in any order and possibly with repetition, to give the $0$-matrix. If I ...
15
votes
Accepted
Undecidable easy arithmetical statement
Ofra: "is there some reasons to believe that the Collatz conjecture is undecidable?"
There is reason to believe a generalized version is undecidable.
This was explored by John Conway in "On ...
15
votes
Is it decidable to check if an element has finite order or not?
Inspired by McCool's paper given in Benjamin's answer, here's an explicit example that is finitely generated but not finitely presented:
let $\phi$ be an injective recursive function from positive ...
15
votes
Are there any undecidability results that are not known to have a diagonal argument proof?
I think that the Burali-Forti-like proof of the incomputability of (a minor variation of) Kleene's $\mathcal{O}$ may fit the bill.
Let $\mathcal{W}$ be the set of indices for computable well-orderings;...
14
votes
Accepted
Commutator problem vs conjugacy/word problem
Denis Osin [Osin, Denis, Small cancellations over relatively hyperbolic groups and embedding theorems, Ann. Math. (2) 172, No. 1, 1-39 (2010). ZBL1203.20031.] proved that every torsion-free countable ...
14
votes
Accepted
Determining whether a lattice is the face lattice of a polytope - NP hard or undecidable?
There's no contradiction:
I don't know the correct complexity, but I recall hearing several times that it is at least as hard as NP.
It is not difficult to show (using Tarski's algorithm, as ...
13
votes
Accepted
Are the terms of a linear recurrence integral?
The problem is effectively decidable. To test whether $u_n$ is eventually integral, first use the recurrence relation for $u_n$ to construct relatively prime polynomials $A,B\in \mathbb{Z}[x]$ such ...
13
votes
Accepted
Decidability of a first-order theory of hyperreals
Yes, the theory is decidable.
If $F$ is an ordered field and $R\subseteq F$ a non-cofinal subfield, then
$$O=\{x\in F:\exists u\in R\:(-u\le x\le u)\}$$
is a convex valuation ring of $F$, with maximal ...
13
votes
Are there any undecidability results that are not known to have a diagonal argument proof?
[Edited slightly for (hopefully!) greater clarity.]
This is more of a comment than an answer, but I think it is relevant. In the context of computational complexity theory (rather than computability ...
12
votes
Accepted
What theories are larger than the real closed field but still decidable?
Thanks to a 1958 paper by Abraham Robinson (whose impetus was a question of Alfred Tarski), an example of such a theory that properly extends RCF is the theory of the structure $(\mathbb{R},~+,~\cdot,...
12
votes
Accepted
Guaranteed correct digits of elementary expressions
There is a certain confusion in the answers, so let me try to dispel this confusion.
There are two different issues here. One is “computing an approximation with arbitrary precision” and one is “...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
decidability × 155lo.logic × 62
computability-theory × 34
nt.number-theory × 22
model-theory × 21
diophantine-equations × 16
gr.group-theory × 14
algorithms × 12
computational-complexity × 12
reference-request × 10
proof-theory × 9
tiling × 8
theories-of-arithmetic × 8
formal-languages × 7
mg.metric-geometry × 6
automata-theory × 6
ra.rings-and-algebras × 5
ds.dynamical-systems × 5
combinatorial-group-theory × 5
ag.algebraic-geometry × 4
set-theory × 4
matrices × 4
polynomials × 4
computational-number-theory × 4
transcendental-number-theory × 4