I feel like I keep failing to wrap my mind around computability in the same way over and over.

Would the following statement be correct?

"There is a turing machine that cannot be proven whether it will terminate or not. For any n we can construct a proof that it will run longer than n. But we cannot construct a proof that for any n it will run longer than n. Due to this particular turing machine, BB(k) cannot be determined for k large enough to admit that turing machine."

▲

cobbal 6 hours ago | parent | next [-]

That's correct. In particular, k=8000 is enough (probably much lower)

https://scottaaronson.blog/?p=2725

▲

orangecat 6 hours ago | parent | next [-]

335 according to https://github.com/jeff87654/busy-beaver/blob/main/ZF/README...

▲

GolDDranks 6 hours ago | parent | prev | next [-]

The current "independent of ZF" upper bound seems to be BB(432).

Source: https://wiki.bbchallenge.org/wiki/Logical_independence

▲

im3w1l 5 hours ago | parent | prev [-]

So then if the BB sequence has finitely many entries. What does it mean that it grows faster than any computable sequence? A finite sequence can't have any asymptotic behavior right?

▲

gizmo686 5 hours ago | parent | next [-]

The BB sequence still has infinitely many entries. Any turing machine will either halt or not halt. For any N, there is a finite set of N-state turing machines which halt, and there is therefore a finite number of steps after which all halting N-state turing machines would halt.

There is a point where these values become uncomputable, but they still exist (for some definition of exist).

▲

cobbal 4 hours ago | parent | prev | next [-]

As others have said, the sequence is infinite, though unknowable. Even if math can't say what the precise value is, it can still prove things about the shape of the sequence.

As a simple example, we know that BB(1000) <= BB(1001) (since you can encode the longest running 1000-TM with an extra, unused state as a 1001-TM) even though we will never know either of those values.

The argument that it grows faster than any computable function is similar in that it proves things without knowing concrete numbers. (I'd have to look up the details of the proof to say more)

	▲	wat10000 3 hours ago \| parent [-]
		You should be able to prove it by showing that the existence of a faster-growing computable function lets you solve the halting problem. Assume f(x) is computable and grows faster than BB(x). We can create a computable g(x) where g(x) > BB(x) for all x, by setting g(x) = f(x) + C for some suitable constant. Now we create a computer program that does the following. 1. Get the size of the input program and compute g(n). 2. Run the input program for g(n) steps. 3. If it stopped, return true. If it's still running, return false. This solves the halting problem. Since a computer program can't solve the halting problem, this program can't exist. Everything except "compute g(n)" is straightforward, so there must be no such function g, and no such function f.

▲

GolDDranks 5 hours ago | parent | prev [-]

Where did you get that the BB sequence would have finitely many entries? You can choose any integer n for BB(n), and there are infinitely many integers.

▲

6 hours ago | parent | prev [-]

[deleted]