72
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_{\...
- 91.7k
58
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 ...
- 197k
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" ...
54
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 ...
- 588
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
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
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 ...
- 10k
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.1k
33
votes
Does an existence of large cardinals have implications in number theory or combinatorics?
There's an extremely elementary theorem whose only known proof relies on the existence of a rank-into-rank cardinal (basically the strongest large cardinal axiom not known to contradict ZFC).
Let $...
- 11.8k
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 ...
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 ...
- 39.4k
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
Is it possible to make an algorithm that could predict the likelihood that a program will halt?
Here is one way of interpreting your question. In my joint paper:
Joel David Hamkins and Alexei Miasnikov, The halting problem is decidable on a set of asymptotic probability one, Notre Dame J. ...
- 197k
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.
- 23.8k
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 ...
- 197k
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'...
- 43.8k
22
votes
Accepted
What is the relationship between Turing Machines and Gödel's Incompleteness Theorem?
It's simple. If the halting problem is undecidable, then PA is not complete, since otherwise, you could solve the halting problem by searching for proofs in PA. And the same argument works for any ...
- 197k
22
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 precissions is required.)
...
- 43.8k
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 ...
- 24k
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}...
- 62.2k
21
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 ...
- 840
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 ...
- 43.8k
20
votes
Are the vertical sections of the Ackermann function primitive recursive?
If you don't mind not getting the best possible result, then the proof is very short. Indeed,
$$A(n,4)=A(n-1,A(n,3))$$
so if you can prove that $A(n,3)\geq n-1$ then $A(n,4)\geq A(n-1,n-1)$, which we ...
- 27.7k
19
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 ...
- 21.6k
19
votes
Accepted
Is the cohomology ring of a finite group computable?
As I understand it this follows from Benson's Regularity Conjecture, proved by Symonds fairly recently. It says that $b_p = 2(|G|-1)$ will do.
- 16.9k
18
votes
Accepted
Is there a stronger form of recursion?
Yes, there are such principles. In fact, there is a natural hierarchy of such class-theoretic recursion principles, which form a hierarchy of strength transcending Gödel-Bernays set theory GBC. ...
- 197k
18
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 ...
- 21.6k
18
votes
Decision problems for which it is unknown whether they are decidable
In response to this CompSciTheory (cstheory) question,
A simple problem whose decidability is not known
,
I posted that:
It is unknown whether or not
it is decidable to determine if a given shape ...
Only top scored, non community-wiki answers of a minimum length are eligible