His choice to bury his work under a mountain of slop means the rest of us don't have to pretend to care about it if we don't want to. Long live the humans!
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?
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).
I am not sure I follow? But maybe I misunderstood your quote. It seems any given TM (And for a fixed N, there are only finite many), there are only the two option: it halts, or it doesn't halt. There is no third option?
Of course, the question whether you can proof that it doesn't halt, in ZF or ZFC, is a different question. (You can always proof that it halts if you know that it halts. You run it until it halts)
I'm not entirely sure about what I'm unsure about, but I think I struggle to accept that there is truth beyond the axioms. Like in my mind if the axioms can't prove whether it halts or not then that's that. There is no "but actually it doesn't halt". Or at least that's where my current thinking is, I think?
I do lack a lot of knowledge about the concept of interpretation, so maybe that's where my issue is?
All great questions. You're dancing around the edge of model theory here and the difference between truth and provability. It's probably past what can be explained well in a comment. Nevertheless, with omissions, simplifications, and my limited knowledge:
In logic, a model is a "set" of objects and all the true facts about those objects. For example, the integers and "1+1=2,1+2=3...". If a model deals with truth, then a "theory" is a mathematical structure that deals with provability. For example, the theory of groups contains an axiom "a+0=a" that applies to any a.
We say that a model "models" a theory when everything the theory proves is true in the model. The integers are a model of a group.
But, the integers mod 2 ({0,1}) are also a model of a group, but a very different one.
So, consider the statement "1+1≠0". The theory of groups isn't powerful enough to prove or disprove this proposition. It is a false statement in the integers, but a true statement of the mod2 integers. So there is a gap between what is true in a model, and what is provable in a theory.
(Look up both godel's completeness theorem and his incompleteness theorem for more insight into this relationship)
Back to turing machines, our most popular foundations of math is a theory named ZFC. With this theory we can prove many things, but there are also many things that can't be proven or disproven. ZFC lets us prove that "BB(500) is an integer greater than 5". But it doesn't let us prove that "BB(500)=174936...35" (pretend that's a concrete number). In fact, there probably is a model of ZFC where it is true that BB(500)=174936...35, and there is also probably a model of ZFC where BB(500)=284729...86.
Axioms define what is provable, but godel showed that there will always be more true things than there are provable things (if your theory is finite-ish). Most concrete questions about the BB function will never be provable.
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)
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.
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.
I review code line by line and build a mental model of the software as I review it. I find plenty of important bugs that way. PRs are an opportunity to learn (both committer and reviewer), communicate, and improve the quality of code a team ships. Sadly, many people decline that opportunity for the sake of short-term velocity.
Why is it unrealistic? We have decades that prove people can make games without AI. Is the unrealistic part just expecting people to be honest about whether they used it or not? We somehow manage to have the food industry mostly honest about what they put in.
And a patch panel and a bunch of patch cables that you plug in and out to construct your pipelines.
And eventually hire people whose job it is to patch pipelines on demand for everyone in the office.
“Hey Jim, I’m gonna output the systemd logs of nginx on line five, can you assemble a grep pipeline for me to match all HTTP 500 status codes from /api/cart POST request log lines? Connect the filtered output to Tim’s desk, line 7. He’s there now, we are trying to figure something out.”
I wonder how close you can get with Nvidia's GPUDirect. Hook the fast NVME directly up to the GPU (well, it gets direct DMA to GPU at any rate), then implement parallel grep in CUDA... profit?
reply