150 votes
Accepted
Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?
$\DeclareMathOperator\cr{cr}\DeclareMathOperator\pcr{pcr}$For the pair crossing number $\pcr(G)$, the short answer is yes the crossing lemma holds for drawings on the sphere, but it is not known ...
- 6,977
62 votes
Is data science mathematically interesting?
I will stay away from the academic politics of hiring "professors of data science", but if I interpret the question more specifically as "does data science offer problems of mathematical interest", I ...
56 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 ...
- 12k
46 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 ...
45 votes
Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?
Assuming an unpublished Ramsey-type result by Robertson and Seymour about Kuratowski minors [FK18, Claim 5], which is now "folklore" in the graph-minor community, an asymptotic variant of ...
- 6,626
43 votes
Is data science mathematically interesting?
Fundamentally a lot of what a modern data scientist does is very similar to what in previous generations would have been the responsibility of a statistician, and it shouldn't surprise you that there ...
43 votes
Accepted
Revisiting the unreasonable effectiveness of mathematics
A 2013 issue of Interdisciplinary Science Reviews was entirely devoted to this topic. One viewpoint, by Jesper Lützen, struck me: When Wigner claimed that the effectiveness of mathematics in the ...
34 votes
Is data science mathematically interesting?
The Mathematics of Data may go some way towards answering your question. As one example of a mathematically interesting topic that is motivated by data science, you might want to look at the concept ...
34 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 ...
- 3,393
31 votes
Lists as a foundation of mathematics
Andreas Blass has already provided a good reference in the literature, but unfortunately I cannot read German, so I've had to make do with writing my own answer. As you observed, you're clearly not ...
- 19k
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 ...
30 votes
Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?
@user161819 I wanted to make a comment but it got too long, so putting it as an answer. But please take it just as a comment for later, once everything is finished: If I understand your comment to my ...
- 6,977
30 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 ...
- 246k
28 votes
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 ...
25 votes
Revisiting the unreasonable effectiveness of mathematics
I have never seen any remotely plausible attempt at setting up a framework in which we are able to quantitatively calculate exactly how much effectiveness would be "reasonable," let alone ...
25 votes
A clear map of mathematical approaches to Artificial Intelligence
I highly recommend the syllabus for Boaz Barak's Harvard course on Foundations of Deep Learning. It balances a mathematical point of view with a respect for the fast-moving empirical aspects of the ...
24 votes
Open questions about posets
The 1/3-2/3 conjecture is probably considered one of the most significant open problems about finite posets; see the Wikipedia page: https://en.wikipedia.org/wiki/1/3%E2%80%932/3_conjecture.
23 votes
Is there a concept of Turing Machine over a group, not just over the integers as a model of the tape?
NOTE: I misread the OP, and so this answer isn't actually relevant. That said, I'll leave it up since the sources seem potentially interesting. I've made this CW and tweaked the first sentence ...
22 votes
Is data science mathematically interesting?
To begin, there is a family of results which are sometimes referred to as "No free lunch" theorems. Each of these results, in their own way, asserts that any optimization algorithm is just as good as ...
21 votes
Examples of errors in computational combinatorics results
(1) In this paper (published J. Combinatorial Designs, 15 (2007) 98-119), in the history section starting page 3, we cite many published errors in counting Latin squares and related objects. Some, but ...
21 votes
Lists as a foundation of mathematics
Peter Koepke and Martin Koerwien developed the theory of sets of ordinals as a foundation of mathematics, showing senses in which it is equivalent to ZFC as a foundation. Peter Koeopke and Martin ...
- 246k
20 votes
Is there a concept of Turing Machine over a group, not just over the integers as a model of the tape?
In "A notion of effectiveness for subshifts on finitely generated groups", the authors define a class of subshifts on groups (a subshift on a group $G$ is a set $X \subseteq A^G$ of ...
- 940
19 votes
Who first chose the names Alice and Bob for players A and B?
Allow me to mention that since the players in effect adopt the roles of the quantifiers $\forall$ and $\exists$, as Bob has a winning strategy just in case for every move for Alice, there is a reply ...
- 246k
18 votes
Accepted
Any important consequences with presupposition of $\mathbf{P} \neq \mathbf{NP}$
Let me take a slightly different angle on this question and interpret it as asking what sorts of hardness results require P ≠ NP only, and which ones require stronger assumptions. By itself, P ≠ NP ...
18 votes
Can you consistently add axioms about the Busy Beaver function to ZF?
Let $b_k$ be the assertion that the busy beaver function at $k$ has the value that it actually has, that is, the value it has in the standard natural numbers of the meta-theory. We know that not all ...
- 246k
18 votes
Defining computable functions categorically
You are looking for realizability toposes and related categories, as was already pointed out in the comments. Let me make a quick summary of how things work and why we can completely circumvent the ...
- 51.3k
18 votes
Accepted
Are there logical systems where formal proofs are not computer verifiable?
There are logical systems whose formal proofs are not computer verifiable. One such example is infinitary logic in which logical statements can be infinitely long, and a specific statement in a proof ...
- 51.3k
18 votes
Open questions about posets
Here's a problem that I believe has little chance of being resolved, and it's also not so clear to me what the motivation behind the problem is, but it involves some very pretty algebraic ...
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