78 votes
Accepted

Why is uncomputability of the spectral decomposition not a problem?

The singular value decomposition, when applied to a real symmetric matrix $A = \sum_i \lambda_i(A) u_i(A) u_i(A)^T$, computes a stable mathematical object (spectral measure $\mu_A = \sum_i \delta_{\...
Terry Tao's user avatar
  • 108k
78 votes
Accepted

Will this Turing machine find a proof of its halting?

It is a very nice question. The answer is yes, the machine will find a proof of its own halting nature, and it will halt when it does so. I claim this is a consequence of Löb's theorem. Let $M$ be a ...
Joel David Hamkins's user avatar
78 votes

Will this Turing machine find a proof of its halting?

Build a second machine $N$. $N$ searches for a proof in ZFC of, "if $N$ halts then $M$ halts". If it finds one, it halts. ZFC can argue as follows. "Suppose $N$ halts. Then it found a ...
Akiva Weinberger's user avatar
55 votes

On mathematical arguments against Quantum computing

Here are some references and following them a short answer. A good reference for the current situation to start with is John Preskill's recent paper "Quantum Computing in the NISQ era and beyond" ...
53 votes

How feasible is it to prove Kazhdan's property (T) by a computer?

I think it is appropriate to let MO users know (the OP himself knows it well) that this question was recently solved: it is feasible to provide a computer based proof for property (T) using the Ozawa ...
Uri Bader's user avatar
  • 11.4k
46 votes

On mathematical arguments against Quantum computing

Scott Aaronson has this list of Eleven Objections, involving both mathematics and physics arguments. What I did is to write out every skeptical argument against the possibility of quantum ...
44 votes
Accepted

Decision problems for which it is unknown whether they are decidable

An integer linear recurrence sequence is a sequence $x_0, x_1, x_2, \ldots$ of integers that obeys a linear recurrence relation $$x_n = a_1 x_{n-1} + a_2 x_{n-2} + \cdots + a_d x_{n-d}$$ for some ...
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.
Benjamin Steinberg's user avatar
31 votes

Using Busy Beavers to prove conjectures

Indeed, the second option is a problem: the BB($n$) cannot be computed in ZF for $n$ large (an explicit bound $n\ge 7910$ was given by Aaronson-Yedidia in their article A Relatively Small Turing ...
Corentin B's user avatar
30 votes

Decision problems for which it is unknown whether they are decidable

In Conway's Game of Life, the problem of deciding whether a given pattern with finitely many live cells is a Garden of Eden (i.e. whether it lacks a predecessor). The main obstacle is that there could ...
29 votes
Accepted

Is there a known Turing machine which halts if and only if the Collatz conjecture has a counterexample?

$\newcommand\PA{\mathit{PA}}$Let's note that this is not a question of whether Collatz is undecidable. The statement $\neg\mathrm{Con}(\PA)$ is undecidable (by $\PA$, assuming $PA$ is consistent) but ...
Bjørn Kjos-Hanssen's user avatar
28 votes
Accepted

Any important consequences with presupposition of $\mathbf{P} \neq \mathbf{NP}$

Because there are natural computational problems involving many mathematical objects, there are a bunch of implications of complexity class separations like $\mathrm{P} \neq \mathrm{NP}$. I think the ...
28 votes

On mathematical arguments against Quantum computing

The promise of quantum computing supremacy is bunk by Colin Earl references to Polynomial Time and Extravagant Models by Leonid A. Levin On Quantum Computing by Oded Goldreich Note (d) Quantum ...
27 votes
Accepted

Does "every" first-order theory have a finitely axiomatizable conservative extension?

Essentially, yes. An old result of Kleene [1], later strengthened by Craig and Vaught [2], shows that every recursively axiomatizable theory in first-order logic without identity, and every ...
Emil Jeřábek's user avatar
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 ...
25 votes
Accepted

Languages beyond enumerable

Yes, for starters there is the arithmetical hierarchy, where enumerable = $\Sigma^0_1$ and it continues $\Pi^0_1$, $\Delta^0_2$, $\Sigma^0_2$ etc. See also the Computability Menagerie.
Bjørn Kjos-Hanssen's user avatar
25 votes
Accepted

How (non-)computable is set theory?

The question is extremely interesting, and I have looked into this kind of thing with various colleagues (including Russell Miller and Kameryn Williams), although our investigation has not yet ...
Joel David Hamkins's user avatar
25 votes
Accepted

"Natural" undecidable problems not reducible to the halting problem

The problems reducible to the halting problem are exactly the problems of complexity $\Delta^0_2$ in the arithmetic hierarchy, and there are indeed many natural problems outside of this class. In this ...
Joel David Hamkins's user avatar
25 votes

Using Busy Beavers to prove conjectures

Although the other answers point out correctly that the exact value of $\text{BB}(n)$ is independent of ZF for large enough and even moderately sized values of $n$, nevertheless I should like to point ...
Joel David Hamkins's user avatar
24 votes
Accepted

The Lucas argument vs the theorem-provers -- who wins and why?

Yes, computers can infer that the Gödel sentence is true. This is performed in a meta-theory which is stronger than the object theory, as it has to be. For example, Russell O'Connor formalized Gödel'...
Andrej Bauer's user avatar
  • 47.7k
24 votes
Accepted

Do we expect that sufficiently large computable ordinals settle every question of arithmetic?

The question of whether a computable linear order is well-founded is $\Pi^1_1$-complete, so this is true in a sense: There is a computable function $F$ such that, for every sentence $\varphi$ in the ...
Noah Schweber's user avatar
23 votes
Accepted

Hard-to-compute real numbers

EDIT: This was in a comment below, but I now think it should be part of the main answer: There are two different ways to ask the question in the OP: Is there a real number $r$ such that no polytime ...
Noah Schweber's user avatar
23 votes

Why is uncomputability of the spectral decomposition not a problem?

The SVD decomposition falls under the family of phenomena where discontinuity implies non-computability. (Intuitively, this is because, at the point of discontinuity, infinite precision is required.) ...
Andrej Bauer's user avatar
  • 47.7k
22 votes
Accepted

(non-)existence of the aperiodic monotile

This recent preprint claims to find such a tile. David Smith, Joseph Samuel Myers, Craig S. Kaplan, Chaim Goodman-Strauss, “An aperiodic monotile”, (2023-03-20) arXiv:2303.10798 A longstanding open ...
22 votes

Why is uncomputability of the spectral decomposition not a problem?

This is primarily an issue of backwards vs. forwards stability. Good SVD algorithms are backwards stable in the sense that the computed singular values and singular vectors are the true singular ...
Nick Alger's user avatar
  • 1,140
22 votes
Accepted

Are the vertical sections of the Ackermann function primitive recursive?

No, already $A(n,3)$ is not primitive recursive. Let me use the essentially equivalent up-arrow notation: $A(n,m)=2\uparrow^{n-1}m$, and argue why $f(n)=2\uparrow^n 3$ is not PR. I claim $f(2n-2)\geq ...
Wojowu's user avatar
  • 27.4k
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}...
Francesco Polizzi's user avatar
21 votes
Accepted

Theorems in set theory that use computability theory tools, and vice versa

Here are several examples. There is a natural affinity between forcing and many constructions in the Turing degrees. Specifically, many constructions of degrees by meeting requirements in succession ...
Joel David Hamkins's user avatar
20 votes

The Halting Problem and Church's Thesis

The invocation of Church's thesis is not a religuous move but rather a warning to the reader that the author is describing informally an effective procedure which could be translated into a ...
Andrej Bauer's user avatar
  • 47.7k
20 votes

For a computable binary tree, is having no computable branches the same as having no probabilistic algorithm for producing branches?

No, we can construct a computable tree with no computable paths such that there is a probabilistic Turing machine which with nonzero probability constructs a path. The basic idea is this: kill off a ...
Noah Schweber's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible