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

learn more… | top users | synonyms

93
votes
42answers
20k 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 ...
63
votes
2answers
2k 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 ...
57
votes
3answers
6k 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 ...
56
votes
8answers
6k 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 ...
44
votes
5answers
5k 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 ...
36
votes
3answers
1k 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 ...
29
votes
3answers
2k 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 ...
28
votes
5answers
896 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 ...
28
votes
0answers
959 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 ...
27
votes
3answers
1k 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 ...
27
votes
3answers
2k 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 ...
26
votes
15answers
5k 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 ...
26
votes
10answers
3k 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$ ...
26
votes
5answers
26k views

How large is TREE(3)?

Friedman, in http://www.math.osu.edu/~friedman.8/pdf/EnormousInt112201.pdf, shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman ...
25
votes
1answer
773 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 ...
24
votes
1answer
857 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 ...
24
votes
0answers
699 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 ...
23
votes
2answers
1k 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$, ...
23
votes
2answers
1k 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 ...
23
votes
1answer
838 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 ...
22
votes
10answers
4k 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 ...
22
votes
8answers
2k 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 ...
22
votes
5answers
1k 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". I regard the ...
22
votes
1answer
604 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 ...
21
votes
3answers
2k 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 ...
21
votes
3answers
2k 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 ...
21
votes
2answers
741 views

Antirandom reals

This is a crossposting of http://math.stackexchange.com/questions/1446602/anti-random-reals, which has not gotten any answers; after thinking about the problem, I've become more convinced that it ...
20
votes
5answers
3k views

Why relativization can't solve NP !=P?

If this problem is really stupid, please close it. But I really wanna get some answer for it. And I learnt computational complexity by reading books only. When I learnt to the topic of relativization ...
20
votes
3answers
2k 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 ...
20
votes
4answers
2k 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 ...
20
votes
1answer
860 views

Word problem for fundamental group of submanifolds of the 4-sphere

Given any finitely-presented group $G$, there are a few equivalent techniques for constructing smooth/PL 4-manifolds $M$ such that $\pi_1 M$ is isomorphic to $G$. For most constructions of these ...
18
votes
3answers
2k 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 ...
18
votes
4answers
923 views

Kolmogorov complexity is the strongest noncomputable function

Yury I. Manin says that Kolmogorov complexity (in some nontrivial sense) is the strongest noncomputable function ("Колмогоровская сложность... невычислима... она во многих интересных смыслах ...
18
votes
1answer
901 views

Looking for a copy of Leo Harrington's unpublished notes on the first nonprojectible ordinal

Sometime around 1975, Leo Harrington wrote a set of notes, apparently 13 pages long, entitled Kolmogorov's $R$-operator and the first nonprojectible ordinal. I do not know how widely they were ...
17
votes
5answers
1k 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 ...
17
votes
5answers
5k 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 ...
17
votes
1answer
1k views

Lawvere's fixed point theorem and the Recursion Theorem

Building off of Qiaochu's comment on my answer to a previous mathoverflow question, I would like to know: can the Recursion Theorem, $$\forall e\exists k[\Phi_e\text{ is total }\implies ...
17
votes
1answer
436 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 ...
16
votes
1answer
1k views

Is it possible to make an algorithm that could predict the likelihood that a program will halt?

Today I began to read about computability theory. I do not even have an elementary understanding of the topic but it certainly got me thinking. I know there is there is no 'one-for-all' algorithm that ...
16
votes
1answer
1k views

What is the relationship between Turing Machines and Gödel's Incompleteness Theorem?

In this article, Scott Aaronson talks about using Turing Machines for proving the Rosser Theorem. What is the relationship between the numbering that Gödel used in his proof of incompleteness and ...
16
votes
1answer
707 views

Polynomial-time algorithm to compare numbers in Conway chained arrow notation

I am looking for a polynomial-time algorithm which, given a character string containing two numbers in Conway's chained arrow notation for large numbers, indicates whether the first number is less ...
15
votes
4answers
1k views

Languages beyond enumerable

A language is a set of finite-length strings from some finite alphabet $\Sigma$. It is no loss of generality (for my purposes) to take $\Sigma=\{0,1\}$; so a language is a set of bit-strings. ...
15
votes
3answers
643 views

Which distributions can you sample if you can sample a Gaussian?

Explicitly: You have a computer that is able to pick a real number at random according to the normal distribution: $\mathcal{N}(0,1) = \frac{1}{\sqrt{2\pi}}e^{-x^2/2}$. Which distributions can this ...
15
votes
1answer
715 views

Undecidable theories easier than $Q$

Most proofs of undecidability for various theories (pure logic with binary relation, group theory, etc.) show that the natural numbers and Robinson's $Q$, in one form or another, can be encoded ...
15
votes
2answers
2k views

Structure theorems for Turing-decidable languages?

Languages decidable by weak models of computation often have certain necessary characteristics, e.g. the pumping lemma for regular languages or the pumping lemma for context-free languages. Such ...
15
votes
3answers
562 views

Do decidable properties of finitely presented groups depend only on the profinitization?

This is a just-for-fun question inspired by this one. Let $P$ be a property of finitely presentable groups. Suppose that The truth of $P(G)$ only depends on the isomorphism class of $G$. Given a ...
15
votes
2answers
622 views

Effectively closed computable functions

I've recently been interested in the following type of functions. A total computable function f:N→N is effectively closed if there is a computable function p such that f[N \ We] = N \ Wp(e), ...
15
votes
1answer
366 views

Computability of Brauer groups

A friend of mine and I were talking about computable algebra, and this question came up. The answer may already be known, but I couldn't find it with Google: Suppose I have a countable field, $k$. ...
15
votes
0answers
641 views

Groups generated by 3 involutions

Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where $0 \leq r < m$. Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition $\tau_{r_1(m_1),r_2(m_2)}$ be the ...
14
votes
6answers
1k views

Non-constructive proofs of decidability?

Are there examples of sets of natural numbers that are proven to be decidable but by non-constructive proofs only?