Skip to main content
MathOverflow

Return to Answer

added 22 characters in body
Source Link
C7X
C7X
  • 2k
  • 1
  • 9
  • 31

I would like to elaborate on an idea at the end of one of Z. A. K.'s comments above. The following quote is from Scott Aaronson's "The Busy Beaver Frontier" (2020):

As we’ll see in Section 5.2, there happens to be a Turing machine with $27$ states, which given a blank input, runs through all even numbers $4$ and greater, halting if it finds one that isn’t a sum of two primes. This machine halts if and only Goldbach’s Conjecture is false, and by the definition of $BB$, it halts in at most $BB(27)$ steps if it halts at all. But this means that knowing the value of $BB(27)$ would settle Goldbach's Conjecture—at least in the abstract sense of reducing that problem to a finite, $BB(27)$-step computation.

If Goldbach's conjecture is false, the smallest counterexample $n$ must be at most $2\cdot BB(27)+2$, since the machine will find the counterexample and halt after checking $\frac{n-2}{2}$ numbers, and this number must be at most $BB(27)$. If Goldbach is true, then as pointed out by Hamkins, any number $N$ will work, including $2\cdot BB(27)+2$. So $2\cdot BB(27)+2$ is an "explicitly" written down constant $N$ with the property you desire.

I say explicit in quotes since I argue that choosing $BB(27)$ for such a constant $N$ is essentially a repackaging of a trivial solution like "$N$ is $2$ if Goldbach is true, and the least Goldbach counterexample if Goldbach is false". Consider the set $S$ of $27$-state Turing machines which are inequivalent to the $27$-state Goldbach conjecture machine in Aaronson's paper under permuting states and mirroring the move instructions. Define the number $N'$ to be the supremum of the halting times of members of $S$ that halt on blank inputs. Also let $f$ be a computable function such that $f(k)$ is the number of steps it takes for the $27$-state Turing machine to check whether $k$ is a Goldbach counterexample or not, and that the machine has some constant number of setup steps $c$. Then $BB(27)$ is essentially "$c+\sum_{2\leq k\leq n,\; k\text{ even}}f(k)$ if this number is greater than $N'$, and $N'$ otherwise". In particular it will not be possible to get a nontrivial upper bound on $BB(27)$ until Goldbach is resolved.

I would like to elaborate on one of Z. A. K.'s comments above. The following quote is from Scott Aaronson's "The Busy Beaver Frontier" (2020):

As we’ll see in Section 5.2, there happens to be a Turing machine with $27$ states, which given a blank input, runs through all even numbers $4$ and greater, halting if it finds one that isn’t a sum of two primes. This machine halts if and only Goldbach’s Conjecture is false, and by the definition of $BB$, it halts in at most $BB(27)$ steps if it halts at all. But this means that knowing the value of $BB(27)$ would settle Goldbach's Conjecture—at least in the abstract sense of reducing that problem to a finite, $BB(27)$-step computation.

If Goldbach's conjecture is false, the smallest counterexample $n$ must be at most $2\cdot BB(27)+2$, since the machine will find the counterexample and halt after checking $\frac{n-2}{2}$ numbers, and this number must be at most $BB(27)$. If Goldbach is true, then as pointed out by Hamkins, any number $N$ will work, including $2\cdot BB(27)+2$. So $2\cdot BB(27)+2$ is an "explicitly" written down constant $N$ with the property you desire.

I say explicit in quotes since I argue that choosing $BB(27)$ for such a constant $N$ is essentially a repackaging of a trivial solution like "$N$ is $2$ if Goldbach is true, and the least Goldbach counterexample if Goldbach is false". Consider the set $S$ of $27$-state Turing machines which are inequivalent to the $27$-state Goldbach conjecture machine in Aaronson's paper under permuting states and mirroring the move instructions. Define the number $N'$ to be the supremum of the halting times of members of $S$ that halt on blank inputs. Also let $f$ be a computable function such that $f(k)$ is the number of steps it takes for the $27$-state Turing machine to check whether $k$ is a Goldbach counterexample or not, and that the machine has some constant number of setup steps $c$. Then $BB(27)$ is essentially "$c+\sum_{2\leq k\leq n,\; k\text{ even}}f(k)$ if this number is greater than $N'$, and $N'$ otherwise". In particular it will not be possible to get a nontrivial upper bound on $BB(27)$ until Goldbach is resolved.

I would like to elaborate on an idea at the end of one of Z. A. K.'s comments above. The following quote is from Scott Aaronson's "The Busy Beaver Frontier" (2020):

As we’ll see in Section 5.2, there happens to be a Turing machine with $27$ states, which given a blank input, runs through all even numbers $4$ and greater, halting if it finds one that isn’t a sum of two primes. This machine halts if and only Goldbach’s Conjecture is false, and by the definition of $BB$, it halts in at most $BB(27)$ steps if it halts at all. But this means that knowing the value of $BB(27)$ would settle Goldbach's Conjecture—at least in the abstract sense of reducing that problem to a finite, $BB(27)$-step computation.

If Goldbach's conjecture is false, the smallest counterexample $n$ must be at most $2\cdot BB(27)+2$, since the machine will find the counterexample and halt after checking $\frac{n-2}{2}$ numbers, and this number must be at most $BB(27)$. If Goldbach is true, then as pointed out by Hamkins, any number $N$ will work, including $2\cdot BB(27)+2$. So $2\cdot BB(27)+2$ is an "explicitly" written down constant $N$ with the property you desire.

I say explicit in quotes since I argue that choosing $BB(27)$ for such a constant $N$ is essentially a repackaging of a trivial solution like "$N$ is $2$ if Goldbach is true, and the least Goldbach counterexample if Goldbach is false". Consider the set $S$ of $27$-state Turing machines which are inequivalent to the $27$-state Goldbach conjecture machine in Aaronson's paper under permuting states and mirroring the move instructions. Define the number $N'$ to be the supremum of the halting times of members of $S$ that halt on blank inputs. Also let $f$ be a computable function such that $f(k)$ is the number of steps it takes for the $27$-state Turing machine to check whether $k$ is a Goldbach counterexample or not, and that the machine has some constant number of setup steps $c$. Then $BB(27)$ is essentially "$c+\sum_{2\leq k\leq n,\; k\text{ even}}f(k)$ if this number is greater than $N'$, and $N'$ otherwise". In particular it will not be possible to get a nontrivial upper bound on $BB(27)$ until Goldbach is resolved.

Source Link
C7X
C7X
  • 2k
  • 1
  • 9
  • 31

I would like to elaborate on one of Z. A. K.'s comments above. The following quote is from Scott Aaronson's "The Busy Beaver Frontier" (2020):

As we’ll see in Section 5.2, there happens to be a Turing machine with $27$ states, which given a blank input, runs through all even numbers $4$ and greater, halting if it finds one that isn’t a sum of two primes. This machine halts if and only Goldbach’s Conjecture is false, and by the definition of $BB$, it halts in at most $BB(27)$ steps if it halts at all. But this means that knowing the value of $BB(27)$ would settle Goldbach's Conjecture—at least in the abstract sense of reducing that problem to a finite, $BB(27)$-step computation.

If Goldbach's conjecture is false, the smallest counterexample $n$ must be at most $2\cdot BB(27)+2$, since the machine will find the counterexample and halt after checking $\frac{n-2}{2}$ numbers, and this number must be at most $BB(27)$. If Goldbach is true, then as pointed out by Hamkins, any number $N$ will work, including $2\cdot BB(27)+2$. So $2\cdot BB(27)+2$ is an "explicitly" written down constant $N$ with the property you desire.

I say explicit in quotes since I argue that choosing $BB(27)$ for such a constant $N$ is essentially a repackaging of a trivial solution like "$N$ is $2$ if Goldbach is true, and the least Goldbach counterexample if Goldbach is false". Consider the set $S$ of $27$-state Turing machines which are inequivalent to the $27$-state Goldbach conjecture machine in Aaronson's paper under permuting states and mirroring the move instructions. Define the number $N'$ to be the supremum of the halting times of members of $S$ that halt on blank inputs. Also let $f$ be a computable function such that $f(k)$ is the number of steps it takes for the $27$-state Turing machine to check whether $k$ is a Goldbach counterexample or not, and that the machine has some constant number of setup steps $c$. Then $BB(27)$ is essentially "$c+\sum_{2\leq k\leq n,\; k\text{ even}}f(k)$ if this number is greater than $N'$, and $N'$ otherwise". In particular it will not be possible to get a nontrivial upper bound on $BB(27)$ until Goldbach is resolved.