Questions tagged [computability-theory]

computable sets and functions, Turing degrees, c.e. degrees, models of computability, primitive recursion, oracle computation, models of computability, decision problems, undecidability, Turing jump, halting problem, notions of computable randomness, computable model theory, computable equivalence relation theory, arithmetic and hyperarithmetic hierarchy, infinitary computability, $\alpha$-recursion, complexity theory.

Filter by
Sorted by
Tagged with
135 votes
43 answers
37k views

What are the most attractive Turing undecidable problems in mathematics?

What are the most attractive Turing undecidable problems in mathematics? There are thousands of examples, so please post here only the most attractive, best examples. Some examples already appear on ...
113 votes
11 answers
17k views

On mathematical arguments against Quantum computing

Quantum computing is a very active and rapidly expanding field of research. Many companies and research institutes are spending a lot on this futuristic and potentially game-changing technology. Some ...
101 votes
4 answers
5k views

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

Recently, I have proved that Kazhdan's property (T) is theoretically provable by computers (arXiv:1312.5431, explained below), but I'm quite lame with computers and have no idea what they actually can ...
Narutaka OZAWA's user avatar
91 votes
2 answers
8k views

Will this Turing machine find a proof of its halting?

Consider the following Turing machine $M$: it searches over valid ZFC proofs, in lexicographic order, and if it finds a proof that $M$ halts, then it halts. If we fix a particular model of Turing ...
Henry Yuen's user avatar
  • 1,899
81 votes
4 answers
12k views

Can a group be a universal Turing machine?

This question was inspired by this blog post of Jordan Ellenberg. Define a "computable group" to be an at most countable group $G$ whose elements can be represented by finite binary strings, with the ...
Terry Tao's user avatar
  • 108k
76 votes
6 answers
9k views

Which graphs are Cayley graphs?

Every group presentation determines the corresponding Cayley graph, which has a node for each group element, and arrows labeled with the generators to get from one group element to another. My main ...
Joel David Hamkins's user avatar
74 votes
8 answers
12k views

Succinctly naming big numbers: ZFC versus Busy-Beaver

Years ago, I wrote an essay called Who Can Name the Bigger Number?, which posed the following challenge: You have fifteen seconds. Using standard math notation, English words, or both, name a single ...
Scott Aaronson's user avatar
67 votes
5 answers
10k views

Decidability of chess on an infinite board

The recent question Do there exist chess positions that require exponentially many moves to reach? of Tim Chow reminds me of a problem I have been interested in. Is chess with finitely many men on an ...
Richard Stanley's user avatar
46 votes
5 answers
4k views

Are the two meanings of "undecidable" related?

I am usually confused by questions of the type "could such and such a problem be undecidable", because as far as I know there are two distinct possible meanings of "undecidable". ...
John Pardon's user avatar
  • 18.3k
44 votes
3 answers
3k views

Does an existence of large cardinals have implications in number theory or combinatorics?

Does an existence of large cardinals have implications in more down-to-earth fields like number theory, finite combinatorics, graph theory, Ramsey theory or computability theory? Are there any ...
Oksana Gimmel's user avatar
43 votes
5 answers
63k views

How large is TREE(3)?

Friedman, in _Lectures notes on enormous integers shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman function and exponentiation ...
Feldmann Denis's user avatar
43 votes
3 answers
5k views

"Simpler" statements equivalent to Con(PA) or Con(ZFC)?

Given any reasonable formal system F (e.g., Peano Arithmetic or ZFC), we all know that one can construct a Turing machine that runs forever iff F is consistent, by enumerating the theorems of F and ...
Scott Aaronson's user avatar
39 votes
3 answers
5k views

Is there a computable model of ZFC?

Background Assuming ZFC is consistent, then by downward Löwenheim–Skolem, there is a countable model (M,$\in$) of ZFC. Since the universe M is countable, we may as well think of it as actually being ...
skeptical scientist's user avatar
37 votes
1 answer
3k views

Is the area of the Mandelbrot provably computable?

Recall the Mandelbrot set $M$ is the set of points $c$ in the complex plane such that the sequence $z_0 = 0, z_{n+1} = z_n^2 + c$ is bounded. It is well-known that $M$ is a compact set of positive ...
Jason Rute's user avatar
  • 6,237
36 votes
3 answers
2k views

Is it decidable to check if an element has finite order or not?

Suppose we have a finitely presented group $G$ with decidable word problem. Is it decidable to check whether a given element $x\in G$ has finite order or infinite?
Al Tal's user avatar
  • 1,271
34 votes
9 answers
5k views

Decision problems for which it is unknown whether they are decidable

In computability theory, what are examples of decision problems of which it is not known whether they are decidable?
34 votes
3 answers
5k views

Why is uncomputability of the spectral decomposition not a problem?

Below, we compute with exact real numbers using a realistic / conservative model of computability like Type Two Effectivity. Assume that there is an algorithm that, given a symmetric real matrix $M$, ...
wlad's user avatar
  • 4,823
34 votes
5 answers
1k views

Does the exact pair phenomenon for partial orders occur in your area of mathematics?

Suppose that I have a partial order P and an increasing sequence $a_0< a_1<a_2<\cdots$ of elements of $P$. A pair of elements (b,c) from P is said to be an exact pair for this sequence, if ...
Joel David Hamkins's user avatar
33 votes
15 answers
6k views

What's a magical theorem in logic?

Some theorems are magical: their hypotheses are easy to meet, and when invoked (as lemmas) in the midst of an otherwise routine proof, they deliver the desired conclusion more or less straightaway&...
33 votes
3 answers
4k views

Using Busy Beavers to prove conjectures

I've been pondering some stuff on Shtetl Optimized where Yedidia and Aaronson construct Turing machines that will only halt if (e.g.) the Riemann Hypothesis is false, or Goldbach's conjecture is false....
schnitzi's user avatar
  • 463
33 votes
3 answers
6k views

Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?

Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$, decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective, respectively, injective? -- And ...
Stefan Kohl's user avatar
  • 19.5k
32 votes
1 answer
2k views

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

I originally asked this question on math.stackexchange.com here. There's a famous theorem (due to Montague) that states that if $\sf ZFC$ is consistent then it cannot be finitely axiomatized. ...
Oscar Cunningham's user avatar
32 votes
1 answer
2k views

Godel on recursion-theoretic hierarchies

At the end of his excellent article, "The Emergence of Descriptive Set Theory" (http://math.bu.edu/people/aki/2.pdf), Kanamori writes: "Another mathematical eternal return: Toward the end of his ...
Noah Schweber's user avatar
31 votes
3 answers
3k views

Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?

Question. Given a Turing-machine program $e$, which is guaranteed to run in polynomial time, can we computably find such a polynomial? In other words, is there a computable function $e\mapsto p_e$, ...
Joel David Hamkins's user avatar
31 votes
2 answers
6k views

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

Some of the simplest and most interesting unproved conjectures in mathematics are Goldbach's conjecture, the Riemann hypothesis, and the Collatz conjecture. Goldbach's conjecture asserts that every ...
Tanner Swett's user avatar
  • 1,133
31 votes
2 answers
3k views

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

I came across a post by Ron Maimon on physics.SE that makes what seems to me to be a very interesting conjecture I've never seen before about what it would take to settle every question of arithmetic. ...
Qiaochu Yuan's user avatar
30 votes
11 answers
6k views

Physics and Church–Turing Thesis

Is there constructed some set of physical laws from which we can logically obtain that any function that can be implemented in some device is Turing computable? EDIT I believe that if we restrict ...
Dan's user avatar
  • 1,288
30 votes
2 answers
2k views

How (non-)computable is set theory?

Here is a naive outsiders perspective on set theory: A typical set-theoretical result involves constructing new models of set theory from given ones (typically with different theories for the original ...
Arno's user avatar
  • 4,366
29 votes
3 answers
3k views

Is the theory of categories decidable?

There are a lot of theorems in basic homological algebra, such as the five lemma or the snake lemma, that seem like they'd be more easily proven by computer than by hand. This led me to consider the ...
29 votes
3 answers
3k views

Is it decidable whether or not a collection of integer matrices generates a free group?

Suppose we have integer matrices $A_1,\ldots,A_n\in\operatorname{GL}(n,\mathbb Z)$. Define $\varphi:F_n\to\operatorname{GL}(n,\mathbb Z)$ by $x_i\mapsto A_i$. Is there an algorithm to decide whether ...
John Pardon's user avatar
  • 18.3k
29 votes
2 answers
1k views

Determining if a rational function has a subtraction-free expression

This question was first asked by Mehtaab Sawhney in Alex Postnikov's combinatorics class. Given a rational function $F=P(x_1,...,x_n)/Q(x_1,...,x_n)$ with (say) integer coefficients, it is often of ...
Christian Gaetz's user avatar
29 votes
1 answer
1k views

Can a string's sophistication be defined in an unsophisticated way?

This question is about sophistication, a way of measuring the amount of "interesting, non-random information" in a binary string, which was proposed by Kolmogorov and others in the 1980s. I'll define ...
Scott Aaronson's user avatar
28 votes
1 answer
2k views

Why isn't this a computable description of the ordinal of ZF?

In a previous MO question, I was told by several commenters that (a) it's known that there exists a computable ordinal $\alpha_{ZF}$ that "encodes the strength of ZF set theory" (i.e., a least ...
Scott Aaronson's user avatar
28 votes
0 answers
891 views

On certain representations of algebraic numbers in terms of trigonometric functions

Let's say that a real number has a simple trigonometric representation, if it can be represented as a product of zero or more rational powers of positive integers and zero or more (positive or ...
Vladimir Reshetnikov's user avatar
27 votes
8 answers
4k views

Between mu- and primitive recursion

It is well known that primitive recursion is not powerful enough to express all functions, Ackermann function being probably the best known example. Now, in the logic courses (that I have had look at)...
user avatar
27 votes
3 answers
3k views

"Natural" undecidable problems not reducible to the halting problem

There is a lot of known examples of undecidable problems, a large amount of them not directly related to turing machines or equivalent models of computations, for example here: https://en.m.wikipedia....
manu fava's user avatar
  • 393
27 votes
3 answers
4k views

Is deciding whether a Turing machine *provably* runs forever equivalent to the halting problem?

Assume for this question that ZF set theory is sound. Now consider the language "PROVELOOP," which consists of all descriptions of Turing machines M, for which there exists a ZF proof that M runs ...
Scott Aaronson's user avatar
27 votes
3 answers
2k views

Defining computable functions categorically

Computable functions may be defined in terms of Turing machines or recursive functions, or some other model of computation. We normally say that the choice doesn't matter, because all models of ...
N. Virgo's user avatar
  • 1,316
27 votes
2 answers
2k views

Are any natural examples of Gödel speed-up known?

In 1936 Gödel announced a theorem to the effect that proofs of certain theorems $T_1,T_2,\ldots$ become dramatically shorter when one passes from a formal system, such as Peano arithmetic PA, to a ...
John Stillwell's user avatar
26 votes
10 answers
4k views

Can We Decide Whether Small Computer Programs Halt?

The undecidability of the halting problem states that there is no general procedure for deciding whether an arbitrary sufficiently complex computer program will halt or not. Are there some large $n$ ...
user40919's user avatar
  • 701
26 votes
1 answer
3k views

Is rule 30 Turing complete? Is there a proof that it isn't?

It is well known that the elementary cellular automaton known as rule 110 is Turing complete. Its cousin rule 30 also produces complicated behaviour. When I read Wolfram's a New Kind of Science (in ...
N. Virgo's user avatar
  • 1,316
26 votes
2 answers
1k views

Is the cohomology ring of a finite group computable?

Is there an algorithm which halts on all inputs that takes as input a finite group ($p$-group if you like) and outputs a finite presentation of the cohomology ring (with trivial coefficients $\mathbb{...
Joshua Grochow's user avatar
25 votes
6 answers
9k views

The problem of finding the first digit in Graham's number

Motivation In this BBC video about infinity they mention Graham's number. In the second part, Graham mentions that "maybe no one will ever know what [the first] digit is". This made me think: Could ...
Sune Jakobsen's user avatar
25 votes
3 answers
4k views

Inverse Ackermann - primitive recursive or not?

I wanted to put this originally on math.stackexchange, since I considered it to be a straightforward question and probably a fairly known fact. After I failed to solve the problem, I browsed through ...
Harun Šiljak's user avatar
25 votes
2 answers
2k views

Decidability of 3 body problem

Is there a result showing that something along the lines of the three body problem is undecidable? Or are they known to be decidable or neither? I mean problems along the lines of the following ...
Peter Gerdes's user avatar
  • 2,551
25 votes
4 answers
3k views

Algorithmically unsolvable problems in topology

This question is inspired by a paper by B. Poonen that appeared on the arxiv some time ago: http://arxiv.org/abs/1204.0299. The paper gives a sample of algorithmically unsolvable problems from various ...
25 votes
1 answer
1k views

Busy Beaver modulo 2

There is well-known Rado's "Busy Beaver" sequence — the maximal number of marks which a halting Turing machine with n states, 2 symbols (blank, mark) can produce onto an initially blank two-way ...
TauMu's user avatar
  • 872
25 votes
1 answer
1k views

Are sums of sequences decidable?

Suppose that $f,g$ are rational functions with integer coefficients such that $\sum_{n=0}^{\infty}f(n)$ and $\sum_{n=0}^{\infty}g(n)$ both converge. Is it decidable whether $\sum_{n=0}^{\infty}f(n)=\...
Joseph Van Name's user avatar
25 votes
2 answers
768 views

Are compact topological $n$-manifolds recursively enumerable?

Earlier this year it was asked on MO, "Are there only countably many compact topological manifolds?" Thanks to Cheeger and Kister, the answer is yes. On the other hand, Manolescu recently debunked ...
Eric S.'s user avatar
  • 596
22 votes
5 answers
3k views

Intermediate value theorem on computable reals

Wikipedia says that the intermediate value theorem “depends on (and is actually equivalent to) the completeness of the real numbers.” It then offers a simple counterexample to the analogous ...
Jason Orendorff's user avatar

1
2 3 4 5
20