User Bjørn Kjos-Hanssen

11 votes

Accepted

Can a stochastic Turing machine output a consistent extension of PA with positive probability?

answered Nov 21, 2015 at 0:18

11 votes

Can We Decide Whether Small Computer Programs Halt?

answered Dec 29, 2013 at 20:59

11 votes

Accepted

Generalising the union-closed sets conjecture from lattice to a larger class of posets

answered Sep 19, 2020 at 18:25

11 votes

Accepted

Usual technical term for replacing a set by the set of singletons of its members?

answered May 11, 2017 at 19:26

10 votes

Accepted

What non-standard model of arithmetic does Hofstadter reference in GEB?

answered Sep 18, 2018 at 7:33

10 votes

The use of the word "model" in Mathematical Logic vs the same word in Natural Sciences

answered Oct 15, 2010 at 15:49

10 votes

Still Difficult After All These Years

answered Nov 2, 2010 at 18:21

10 votes

How many Complexity Classes do you know?

answered Mar 6, 2014 at 2:09

10 votes

A translation of the Cantor set contained in the irrationals

answered Feb 22, 2014 at 20:19

10 votes

Proof complexity of two directions of equivalency?

answered May 17, 2014 at 20:52

10 votes

Accepted

Lebesgue measure of a set of irrational numbers

answered Jul 16, 2014 at 22:57

10 votes

When the automorphism group of an object determines the object

answered Jan 17, 2017 at 6:37

10 votes

Three-halves-free words (analogous to square-free)

answered Apr 6, 2015 at 1:29

9 votes

Natural examples of $\bf\Sigma^0_3$ equivalence relations

answered Aug 27, 2015 at 3:38

9 votes

What kind of algebra is the class of ordered pairs equipped with the binary operation which forms them?

answered Jul 12, 2014 at 22:40

9 votes

Accepted

Is Van der Waerden's function elementary

answered Feb 28, 2014 at 8:04

9 votes

Is every non-recursive set in $\Sigma_1$ complete in $\Sigma_1$ (relatively to many-to-one reductions)?

answered Mar 21, 2014 at 20:52

9 votes

Accepted

Is the equational theory of groups axiomatized by the associative law?

answered Aug 31, 2019 at 23:06

9 votes

Accepted

Choice sets from above and below

answered Nov 7, 2017 at 7:05

9 votes

Accepted

What about $n^{\frac{1}{x}+\frac{1}{y}}+n^{\frac{1}{y}+\frac{1}{z}}=n^{\frac{1}{z}+\frac{1}{x}}$ over positive integers?

answered Sep 5, 2019 at 7:37

8 votes

Examples of statements with a high quantifier complexity

answered Sep 24, 2017 at 19:25

8 votes

Accepted

Sets with equal positive measure in every interval

answered Oct 14, 2010 at 6:47

8 votes

Where to publish math that's original but easy but requires theorems not every undergrad knows?

answered Jan 7, 2014 at 18:30

8 votes

Accepted

Reverse Math of High Sets?

answered Feb 1, 2014 at 21:21

8 votes

How to explain the concentration-of-measure phenomenon intuitively?

answered Jun 27, 2015 at 20:32

8 votes

Accepted

Define Turing machine with algebraic concepts/structures

answered Jan 15, 2015 at 5:24

8 votes

Is it consistent with ZFC (or ZF) that every definable family of sets has at least one definable member?

answered Sep 12, 2014 at 17:54

8 votes

Accepted

Publishing an elementary proof of a less-general and less-useful version of a classic result?

answered Oct 13, 2014 at 8:37

8 votes

Accepted

Is there an unambiguous CFL whose complement is not context-free?

answered Oct 18, 2014 at 7:50

7 votes

A decision problem for clones

answered Mar 28, 2015 at 23:36

Stack Exchange Network

415 Answers

Can a stochastic Turing machine output a consistent extension of PA with positive probability?

Can We Decide Whether Small Computer Programs Halt?

Generalising the union-closed sets conjecture from lattice to a larger class of posets

Usual technical term for replacing a set by the set of singletons of its members?

What non-standard model of arithmetic does Hofstadter reference in GEB?

The use of the word "model" in Mathematical Logic vs the same word in Natural Sciences

Still Difficult After All These Years

How many Complexity Classes do you know?

A translation of the Cantor set contained in the irrationals

Proof complexity of two directions of equivalency?

Lebesgue measure of a set of irrational numbers

When the automorphism group of an object determines the object

Three-halves-free words (analogous to square-free)

Natural examples of $\bf\Sigma^0_3$ equivalence relations

What kind of algebra is the class of ordered pairs equipped with the binary operation which forms them?

Is Van der Waerden's function elementary

Is every non-recursive set in $\Sigma_1$ complete in $\Sigma_1$ (relatively to many-to-one reductions)?

Is the equational theory of groups axiomatized by the associative law?

Choice sets from above and below

What about $n^{\frac{1}{x}+\frac{1}{y}}+n^{\frac{1}{y}+\frac{1}{z}}=n^{\frac{1}{z}+\frac{1}{x}}$ over positive integers?

Examples of statements with a high quantifier complexity

Sets with equal positive measure in every interval

Where to publish math that's original but easy but requires theorems not every undergrad knows?

Reverse Math of High Sets?

How to explain the concentration-of-measure phenomenon intuitively?

Define Turing machine with algebraic concepts/structures

Is it consistent with ZFC (or ZF) that every definable family of sets has at least one definable member?

Publishing an elementary proof of a less-general and less-useful version of a classic result?

Is there an unambiguous CFL whose complement is not context-free?

A decision problem for clones