Skip to main content
added 122 characters in body
Source Link
Asaf Karagila
  • 410.2k
  • 49
  • 657
  • 1.1k

Recall the Busy Beaver function, $BB(n)$ is the maximal number of steps that a Turing machine with at most $n$ states will halt on the blank tape, assuming it halts at all.

$\sf ZFC$ cannot decide the value of $BB(1919)$.1

Namely, if there is a contradiction to $\sf ZFC$, then a Turing machine with less than $2000$ states should be able to find it. Yes, $1919$ is a large number, but it's not unimaginably large. But what it means is that $BB(1919)$ is pretty much entirely unimaginable, because we cannot even give it a concrete estimation.

(See this and that on Scott Aaronson's blog.)


1. Under the usual caveat that we need to assume that $\sf ZFC$ is consistent of course.

Recall the Busy Beaver function, $BB(n)$ is the maximal number of steps that a Turing machine with at most $n$ states will halt on the blank tape, assuming it halts at all.

$\sf ZFC$ cannot decide the value of $BB(1919)$.

Namely, if there is a contradiction to $\sf ZFC$, then a Turing machine with less than $2000$ states should be able to find it. Yes, $1919$ is a large number, but it's not unimaginably large. But what it means is that $BB(1919)$ is pretty much entirely unimaginable, because we cannot even give it a concrete estimation.

(See this and that on Scott Aaronson's blog.)

Recall the Busy Beaver function, $BB(n)$ is the maximal number of steps that a Turing machine with at most $n$ states will halt on the blank tape, assuming it halts at all.

$\sf ZFC$ cannot decide the value of $BB(1919)$.1

Namely, if there is a contradiction to $\sf ZFC$, then a Turing machine with less than $2000$ states should be able to find it. Yes, $1919$ is a large number, but it's not unimaginably large. But what it means is that $BB(1919)$ is pretty much entirely unimaginable, because we cannot even give it a concrete estimation.

(See this and that on Scott Aaronson's blog.)


1. Under the usual caveat that we need to assume that $\sf ZFC$ is consistent of course.

Source Link
Asaf Karagila
  • 410.2k
  • 49
  • 657
  • 1.1k

Recall the Busy Beaver function, $BB(n)$ is the maximal number of steps that a Turing machine with at most $n$ states will halt on the blank tape, assuming it halts at all.

$\sf ZFC$ cannot decide the value of $BB(1919)$.

Namely, if there is a contradiction to $\sf ZFC$, then a Turing machine with less than $2000$ states should be able to find it. Yes, $1919$ is a large number, but it's not unimaginably large. But what it means is that $BB(1919)$ is pretty much entirely unimaginable, because we cannot even give it a concrete estimation.

(See this and that on Scott Aaronson's blog.)