Skip to main content
Minor wording thing
Source Link
Sridhar Ramesh
  • 5.8k
  • 1
  • 34
  • 45

Are there any significant open problems in mathematics which are clearly decidable (in that it is easy to write a clearly corresponding program which will eventually output either Yes or No (or whatever sort of answer, out of finitely many possibilities, is appropriate), though it may take an implausibly long time to do so) but which remain open?

Dropping the qualifier "significant", examples of this sort of thing would be determining whether chess between perfect players results in a white win, black win, or stalemate; determining the $10^{10^{100}}$th decimal digit of $\pi$; etc. But none of these are of particular significance in mathematics, such that anyone would ordinarily list them as an open problem of note.

So, though it is inherently a subjective judgment: Are there any good examples of significant open problems of this sort?

(Edit: I nominate this question for reopening as NOT a duplicate, in that the question it has been marked a duplicate of specifically excludes problems that "naturally resolve after a finite computation", being interested only in problems which nontrivially reduce to finite computation. My interest is in either, but for me, the ideal examples are those that are manifestly finite computations from the start!)

Are there any significant open problems in mathematics which are clearly decidable (in that it is easy to write a program which will eventually output either Yes or No (or whatever sort of answer, out of finitely many possibilities, is appropriate), though it may take an implausibly long time to do so) but which remain open?

Dropping the qualifier "significant", examples of this sort of thing would be determining whether chess between perfect players results in a white win, black win, or stalemate; determining the $10^{10^{100}}$th decimal digit of $\pi$; etc. But none of these are of particular significance in mathematics, such that anyone would ordinarily list them as an open problem of note.

So, though it is inherently a subjective judgment: Are there any good examples of significant open problems of this sort?

(Edit: I nominate this question for reopening as NOT a duplicate, in that the question it has been marked a duplicate of specifically excludes problems that "naturally resolve after a finite computation", being interested only in problems which nontrivially reduce to finite computation. My interest is in either, but for me, the ideal examples are those that are manifestly finite computations from the start!)

Are there any significant open problems in mathematics which are clearly decidable (in that it is easy to write a clearly corresponding program which will eventually output either Yes or No (or whatever sort of answer, out of finitely many possibilities, is appropriate), though it may take an implausibly long time to do so) but which remain open?

Dropping the qualifier "significant", examples of this sort of thing would be determining whether chess between perfect players results in a white win, black win, or stalemate; determining the $10^{10^{100}}$th decimal digit of $\pi$; etc. But none of these are of particular significance in mathematics, such that anyone would ordinarily list them as an open problem of note.

So, though it is inherently a subjective judgment: Are there any good examples of significant open problems of this sort?

(Edit: I nominate this question for reopening as NOT a duplicate, in that the question it has been marked a duplicate of specifically excludes problems that "naturally resolve after a finite computation", being interested only in problems which nontrivially reduce to finite computation. My interest is in either, but for me, the ideal examples are those that are manifestly finite computations from the start!)

Post Reopened by Bjørn Kjos-Hanssen, Timothy Chow, Stefan Kohl, Jan-Christoph Schlage-Puchta, Jeremy Rouse
added 443 characters in body
Source Link
Sridhar Ramesh
  • 5.8k
  • 1
  • 34
  • 45

Are there any significant open problems in mathematics which are clearly decidable (in that it is easy to write a program which will eventually output either Yes or No (or whatever sort of answer, out of finitely many possibilities, is appropriate), though it may take an implausibly long time to do so) but which remain open?

Dropping the qualifier "significant", examples of this sort of thing would be determining whether chess between perfect players results in a white win, black win, or stalemate; determining the $10^{10^{100}}$th decimal digit of $\pi$; etc. But none of these are of particular significance in mathematics, such that anyone would ordinarily list them as an open problem of note.

So, though it is inherently a subjective judgment: Are there any good examples of significant open problems of this sort?

(Edit: I nominate this question for reopening as NOT a duplicate, in that the question it has been marked a duplicate of specifically excludes problems that "naturally resolve after a finite computation", being interested only in problems which nontrivially reduce to finite computation. My interest is in either, but for me, the ideal examples are those that are manifestly finite computations from the start!)

Are there any significant open problems in mathematics which are clearly decidable (in that it is easy to write a program which will eventually output either Yes or No (or whatever sort of answer, out of finitely many possibilities, is appropriate), though it may take an implausibly long time to do so) but which remain open?

Dropping the qualifier "significant", examples of this sort of thing would be determining whether chess between perfect players results in a white win, black win, or stalemate; determining the $10^{10^{100}}$th decimal digit of $\pi$; etc. But none of these are of particular significance in mathematics, such that anyone would ordinarily list them as an open problem of note.

So, though it is inherently a subjective judgment: Are there any good examples of significant open problems of this sort?

Are there any significant open problems in mathematics which are clearly decidable (in that it is easy to write a program which will eventually output either Yes or No (or whatever sort of answer, out of finitely many possibilities, is appropriate), though it may take an implausibly long time to do so) but which remain open?

Dropping the qualifier "significant", examples of this sort of thing would be determining whether chess between perfect players results in a white win, black win, or stalemate; determining the $10^{10^{100}}$th decimal digit of $\pi$; etc. But none of these are of particular significance in mathematics, such that anyone would ordinarily list them as an open problem of note.

So, though it is inherently a subjective judgment: Are there any good examples of significant open problems of this sort?

(Edit: I nominate this question for reopening as NOT a duplicate, in that the question it has been marked a duplicate of specifically excludes problems that "naturally resolve after a finite computation", being interested only in problems which nontrivially reduce to finite computation. My interest is in either, but for me, the ideal examples are those that are manifestly finite computations from the start!)

Source Link
Sridhar Ramesh
  • 5.8k
  • 1
  • 34
  • 45

Decidable open problems

Are there any significant open problems in mathematics which are clearly decidable (in that it is easy to write a program which will eventually output either Yes or No (or whatever sort of answer, out of finitely many possibilities, is appropriate), though it may take an implausibly long time to do so) but which remain open?

Dropping the qualifier "significant", examples of this sort of thing would be determining whether chess between perfect players results in a white win, black win, or stalemate; determining the $10^{10^{100}}$th decimal digit of $\pi$; etc. But none of these are of particular significance in mathematics, such that anyone would ordinarily list them as an open problem of note.

So, though it is inherently a subjective judgment: Are there any good examples of significant open problems of this sort?