# Tag Info

Accepted

• 11.8k

### 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 ...
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 ...

### 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 ...
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
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 ...

### 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. ...
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
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 ...
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
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 ...

### 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
Accepted

• 62.2k

### 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

### 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

### 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
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
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.
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. ...