As one of the people referenced in Scott's papers, let me say you are definitely welcome. A side from that, I would like to say your video did a really good job explaining where the Collatz aspect is showing up. There's another way that Collatz-like things showing up here is maybe not completely surprising: There's a theorem (I think originally due to Conway but I may be wrong there) that says essentially that you can go in the other direction and that determining whether a given Collatz-like system halts is exactly equivalent to the Halting problem. And the proof is essentially to model Turing machines using Collatz-like functions, where applying the function represents a step in the Turing machine. On the other hand, this theorem is not really a completely satisfying explanation here, because lots of different problem classes are equivalent to the Halting problem, and they don't show up here. So, in some sense, this may be happening because Collatz-like functions are one of the simplest things of this type, but this is not really satisfying as explanations go.
Joshua, it's great to hear from you and I'm happy you enjoyed the video. I feel a bit of regret because there was a segment I cut that discussed one of your conjectures - that the graph of every Busy Beaver is a strongly connected graph. If I understand correctly, it suggests that our programming languages, which rely on things like encapsulation, could never produce a Busy Beaver. I found that quite interesting. It makes clear, in a way I'd never enjoyed before, what's lost when we make programs easy for humans to use. Very cool! And your comment "whether a given Collatz-like system halts is exactly equivalent to the Halting problem" almost doesn't surprise me by this point (thought I certainly didn't know about it) If this trip taught me anything, it's that many things can be converted into the halting problem. But I'd still be interested in understanding Collatz + the Halting Problem connection. I suspect the high chaos/simplicity ratio is just one way to see it.
Well, you can always do another video. Regarding the strongly connected conjecture, I'm not sure it says as strong a statement that our usual encapsulated style of program cannot produce a Busy Beaver. If you take a reasonably encapsulated program and try to naively make a Turing machine out of it, you'll often end up with a strongly connected graph. It says more that Busy Beavers shouldn't be coming from every doing program compositions, where we first run program X, and then after run program Y on the output of X. Also worth recognizing that this is an extremely weak property. The proportion of Turing machines which have strongly connected graphs as the size of the machines goes up goes to 1. So this is really even if true ruling out only a tiny fraction of all machines. (In fact, someone else suggested, (maybe Nick Drozd ?) that we should expect that for any property P that almost directed graphs have should be a property that all sufficiently large Busy Beaver graphs have. Which if true would mean that there's no hope of really drastically reducing the set of candidate machines at any stage.
@@joshuazelinsky5213 Ah I see - well now I'm less regretful, as I would have said something wrong! But now I'm curious. If we have a TM that is not strongly connected, does that imply *anything* about the program that we would conventionally recognize? E.g. something like-but-different from encapsulation?
@@Mutual_Information Yes, it would say something like that it was functionally running one program and then running another program on that program's output. Each time one passed into a new section and could not go back, it would be essentially analogous to that. I think, but am not sure that the closest thing to not being actually encapsulated would be some sort of statement that we should see very large subsets of states with only a tiny number of in and out flows into that state set, since those subsets would essentially represent subfunctions or subprocedures then. Unfortunately, we have so few values of BB where we can actually prove much, that all of these things are conjectures with very little empirical data behind them. A divine being, or at least a being with access to a Halting oracle might find a lot of our guesses here pretty laughable.
@@Mutual_Information Also, I should note that in all fairness to you, when I initially made the strong connectedness conjecture, I interpreted it the same way you are doing, and it took conversations with other people to realize that it was not quite saying something as strong as I thought it was about encapsulation and spaghetti code.
I did an old fashioned computer science degree in the late 80's. Godel/Turning/Church blew my mind when I realised that godel used maths to prove that maths cannot fully explain the universe. And the trigger for it all was Bertrand Russle's logical pardox "This statement is false". Very informative videos, I did not realise that busy beaver and collatz were essentially the same thing
the fact that theres such a fundamental relationship between ideas in math is, ironically, fundamental to math itself. Since math js an axiomatic system and many fields seem to represent the same "logical core" there are tons of areas of overlap that are blurred through the double-vision of varying syntactic interfaces. Ive come to realise this many times and independently. Math is truly amazing
13:23 So to prove ZF is consistent, we must use a more powerful axiom-system. But since this new A.S. cannot prove its own consistency either, we need yet another A.S. more powerful, and so on, until the completeness of the system causes it to have inconsistencies! So it's impossible to prove ZF consistent, no matter how hard we try! This reminds me of a connection I found between time-travel, the observer effect, fluid dynamics, and the halting problem. Here's the short explanation: If you want a 100% accurate weather forecast, you must *simulate the observable universe,* but you need a 2nd universe to build+store the machine (or use the new universe itself as the simulation). But the very act of observing the simulation requires a *2nd pair of simulations,* then we must double the number of universes *recursively* until we get an unmanageable multiverse. So light-speed and causality aren't the only things preventing to predict the future, it's the observer-effect and the halting-problem too!
Your previous busy beaver video made me finally understand what BB is and I became obsessed with it. I'm not completely following this one just yet. Will try rewatching a few times, but thank you for continuing to deep dive on this topic!
One of the problems with proving something by waiting on some Turing machine reaching the BB-limit, is that it will probably be easier to to resolve Goldbach than to prove the upper bound on BB(27)
My understanding is that its impossible to know BB(27) without already having solved Golbach. (and every other B(27) machine). This is because in order to prove that our BB(27) machine is the one that produces the largest value, we would need to prove that Goldbach eighter halts with smaller value, or that it never halts.@@kindlin
@@LostOter Oh no, YT ate my comment. Anyways, what I was trying to say, was, just the fact that the BB(27) method exists, even if it is entirely nonfeasible in any real computation, implies (or maybe proves?) that there is a proof (or anti proof) of the conjecture. The only other outcome would be if that proof was actually the BB(27) method, in which case it's just the trivial answer, but I'm willing to bet that's not the case.
It's impossible to use BB to prove anything, even if we had the values of the function for any n given to us by god. We would need an absurd amount of memory and time, as well as a machine that defies all known laws of thermodynamics.
I genuinely would love to hear you talk more about these theories and papers I know enough about these theories and concepts to follow, and you make learning more those concepts really easy to follow as well
You're my target audience - people who already knew a good deal and aren't spooked by math :) To set expectations, I don't plan on going further on these topics in the near future. This was a bit of a detour for me
I'm in the same boat. However the science is pretty much an empty sheet after you internalized scots busy beaver frontier. Super interesting but also very limited
This video is absolutely incredible. The fact that many famous math problems can be connected to the halting problem totally blew my mind. Thank you for creating this amazing and educational content!!
I knew there was a connection, but hadn't seen it this clearly. In the end mathematics itself is just a programming language. Anything that applies to python or C++ is bound to math, which is just another set of symbols we ascribe meaning to.
Thank you very much for this insight into busy beaver. It always fascinated me, but I did not have much (and still dont have) opportunity to dive deeper into the topic. This is awesome summarisation and personally I am hoping for more insight into this. You are doing it really well.
Your videos are absolutely amazing. As someone looking for intuitive technical rigor, this is perfect for understanding the foundations for complex concepts and always helps and inspires me to better filter the technical jargon throughout the field.
Excellent. When making this videos, I am targeting a specific audience. Those who aren't afraid of math who want to learn more. Sounds like you're right in the center of it
@@Mutual_Information thank you sir; you are without question providing invaluable information to those hungry for learning and applying these fundamental mathematical concepts. With the explosion of AI; I am sure there are hungry/curious researchers out there trying to push the boundaries of computation and are getting productive inspiration from your videos (just as I have been in the past few). Thanks from all of us :)
3:20 these unexpected links are so mind blowing to me - "how can 2 things that seem so disparate be connected?" When these connections finally come to light, I do wonder if our brain also makes physical connections from the neurons representing one concept to the neurons representing the other concept.
At 11:45-12:26 the T about the halting problem sounded something similar to a topos. In “A simple presentation of the effective topos” (2013) by Bernadet and Graham-Lengrand at their intro I found a similar statement that an effective topos which describes ones that are “computable” and have the natural numbers lack the law of excluded middle. Other 2-out-3 cases are mentioned there.
@@Mutual_InformationNo problem. Just to expand on that: the graphics, the clarity in how you phrase things, the level of detail you give the tricky concepts, your general diction. It really is outstanding, watching these videos was like someone unfogged the glass for me on a number of concepts I'd previously found opaque. To put it another way, I think there might actually be nothing in existence that I couldn't understand with one of your videos. So as a maths guy, I can only hope you've enjoyed this venture into the computer science/maths border. Now if you could explain to me why TREE(n) is estimated to be at the SVO, or why SSCG(2) = 3.241704 × 10^35775080127201286522908640065, that would be nirvana. But I suppose you've got to think of your other viewers 😝
Great video. I am not that knowledgeable in mathematics or computation at all, but I could sense near the end that you were going to tie things together with Godel's incompleteness theorem and the halting problem. I think that Godel, Escher, Bach actually discusses this part quite well, although it doesn't reference the busy beaver function. The parts about these 2 videos that really blew my mind were that: a) there are BB functions that encode the answers to famous unsolved mathematical conjectures, and b) there is a point beyond which BB functions become undecideable with the rules of mathematics that we currently use.
I'd add the third revelation: c) If for a given hypothesis you can create a Turing machine which checks all the possible options for counterexamples, then there exists a natural number beyond which it is guaranteed no counterexample exists, hence you have to check only finitely many cases to be sure if the hypothesis is true or not. If I understand correctly, this means that for any hypothesis about prime numbers only finitely many prime numbers are important. Extremely large prime numbers are completely irrelevant and you get the theorem for those numbers for free once you check if the hypothesis is true for those relevant "small" prime numbers. This is completely mindblowing.
@@piotr.ziolo. Nicely generalized! The video explains the example problems (e.g. GoldBach) only b/c it's easier to digest. But the real punch is in the general case, as you point out
These videos are one of the best I have ever seen. Because there are so many natural questions, I feel really encouraged to seek out the topic for myself! If I can suggest another topic for a video, it would have to be the ordinals, from a general point of view, not from ZFC. The question from which the ordinals naturally arise is: "which are the different permanent states of a mathematical statement, hypothetically". For every collection of states, you can hypothetically proof that the "proof state" of a statement is none of these. This is exactly what the ordinals are. This is not just about pure logic, it really hits close to computation as well, especially the Church-Kleene ordinal.
That's an interesting topic for sure, but I can't say I'm prepare for that video in particular. I have a long queue I've been meaning to get to, but I do hope to get back to computational complexity eventually.
What an amzing video! Especially at the end where you explain the connection between the halting problem and many other famous math problems🤯 As a first year computer science undergrad videos like this are a true motivation❤ What did you study? Or are you still studying🤔
Thank you! Glad you feel the way I do on this one. I studied math and econ in undergrad. And then I studied financial engineering in grad school. This computation complexity isn't in my wheel house. I just went down a strange rabbit hole. But keep studying! Eventually, you understand the language of rigor and precision and once you've learned a few subjects, it becomes easier to go into the next one. Also, you meet others who understand the things you'd like to learn, so you ask them too. I'm very grateful that I took an interest in nerdy stuff awhile ago, because it really does open up a lot of technical worlds to you (if you're into that).
Only have seen two videos from your channel and am hooked... you are somehow translating what I perceive about math but can't always put into words... subbed!
This video explains the concept of why we know everything and don't know everything at the same time. We know everything because we can compute everything but we don't know everything because we can't compute everything fast enough.
Ngl, I feel like this busy beaver thing is an Overkill idea that definitionally is the limit of computation. It's like a programming language for math that doesn't solve any problems, just makes them concrete/well-defined. It's like the incompleteness theorems, by definition somethings are impossible to prove/disprove. Disclaimer: this is just my opinion based off watching the last two videos.
That's a fair perspective. Essentially, we are doing exactly that - merely specifying doable/not-doable when it comes to proofs and computation. To some, but not all, it's fascinating because it's hard to imagine what isn't provable or computable. But this is a matter of taste. I've spoken with friends who think it's utterly unsurprising that you can't prove everything.
Would be nice if you covered non deterministic turing machines, NP-Completeness and SAT solvers as the next step! NP-Completeness is in a way a finite length approximation of the halting problem: if we can efficiently solve SAT then we can attack math theorems by exploring all the proofs of length
I would be stretching myself to get into those topics. I may gear up for it by starting to read a text on the side. I recall there was a short textbook that was praised for it's succinct coverage, but I can't find it. Or at least, all the recommended books don't look short. Any chance you know what I'm referring to?
@@Mutual_Information Unfortunately not, but I was able to find something you might find interesting: it's a correspondence letter between Godel and Von Neumann where he explains how despite the halting problem, a fast enough turing machine could displace mathematicians! Search for "gwern godel letter", you should find a reference at Gwern's math index (I cannot type it here, bar the comment getting autoremoved). Checking whether a provided proof for a logical statement is correct is easy to do (polynomial time), making this problem in the class NP! The SAT problem is fundamentally about this.
@@mgostIH I'd never heard of this - very cool. I added it a list of potential topics I'll cover one day. It's pretty interesting to cover the ponderings of the greats..
Is a non deterministic Turing machine like the logical equivalent of an abstract infinitely strong quantum computer, like the Turing machine is the abstract classical computer?
@@dekippiesip Not quite, quantum effects are different from parallelism, you can think of a NDT as a turing machine that has unbounded parallel threads to solve any problem.
My reaction when you revealed "The Collatz Conjecture" was an incredible feeling of "What does THAT have to do with anything?!". That is the mark of a good math surprise. Also, the unprovability feels absurd. Like, BB(1000) exist - it IS a number - but we can't prove what it is. Does the halting/not halting behavior of machines depend on the system? It feels like it shouldn't, but that assumption leads to results that feel absurd.
"There exists a Turing Machine M incomprehensible to mathematics" - I think this is only true for any fixed system of axioms (like ZFC)? Like otherwise you can just add "M halts/M doesn't halt" as an axiom and the system remains consistent? Isn't this just Goedel/large cardinals all over again? We already know that ZFC is not "perfect", and we might need to add new axioms eventually (e.g. CH or ~CH). My (intuitive, informal, and possibly incorrect) understanding of why TMs & BBs are so powerful (i.e. "more powerful" than axiomatic systems) is because they effectively "enumerate logic". Given an axiomatic system, there will be a TM able to enumerate all of its proofs/theorems.
Yes, but I think it defeats the purpose of a system if we extend it with the conclusions we want. Ideally, we could extent it only mildly to gain a handle a machine M, but which specific extension to include is now the question. Regarding your intuition, I like the way you put it. If we use the enumeration of logic itself, we can construct things it can't handle.
@@Mutual_Information I just rewatched these and came up with an idea - iirc, there is intuitively a BB number that's the boundary of computable and uncomputable. HALT (the halting problem) is an example of a proven undecidable problem. The way we prove it is give an example TM M that if we "fed" into the HALT-TM, we would get a contradiction. I've been wondering - how many states do we need to construct M (when the alphabet is just 2 symbols)? Or, more generically, what's the smallest number n for which a TM with that many states exists, and it disproves (forms a counterexample to, if you may) a known undecidable problem? Wouldn't that number give us an idea of when Busy Beavers become uncomputable? Edit: I found a claim somewhere that there is a Universal TM with 24 states and 2 symbols, so n
For any system of mathematics, there are procedures to construct Turing Machines that are incomprehensible to the given system. Personally, I find it more interesting that there are also procedures to construct Turing Machines that are *just a little* comprehensible to a system of math, where the Turing Machine can be constructed to be universal if only if it cannot be proven to be universal, and to still allow proving surprisingly many properties that one would intuitively think are sufficient to give universality.
Lol I think there's a wide gap between making a shiny RUclips video and actually solving extremely hard problems, but I appreciate the vote of confidence!
Okay, I think I’m starting to understand. In other words, if we run each machine for a given input, the machine that generates the largest finite number is a Busy Beaver. Of course some machines go on to infinity. However, as the inputs get larger, we can’t know if a machine is a Busy Beaver or not, because it could simply never halt. Or it might. But it would take an eternity. But also, there has to be a Busy Beaver for every single number, right? Because that’s what logic would dictate.
Extremely interesting topic, and well explained. Thank you! One question though. Regarding the axiomatic system A and the N for which there exists a TM with N states sich that it proves whether all statements are provable in A - sure bute that is the ultimate bound, right? Surely there exists M much smaller than N such that S(M) is ulready unprovable in A. We could then classifiy the "provability span" of a system by such M, right? For example, our current mathematical system might have M = 27 🤔
What about this alternative proof of 11:27 : Assume by way of contradiction, for all N there exists n>N and k such that you can prove S(n) = k. We will decide the halting problem: Given a turing machine of size N, go over all n>N and all k and all proofs of S(n) = k. We can do that strategically to not get stuck and find the promised n,k which we know exist. Now run the given turing machine for k steps and check if it halts. It has less states than n and S(n) = k, so if it halts it surely halts before that. (if we add dummy states to it we can make it an n-state machine, so the S(n) limit applies to it as well).
Yea, that's the alternative. Assume you can and you're gov something that can solve the halting problem, and we know that's not true. I didn't go with that one because it seems to shift the mystery from S(n) = k to the halting problem, which many, myself included, find mysterious itself. I'm happier using the fact that a consistent system can't prove it's own consistency. But that's just a matter of taste
@Mutual_Information that's very lucky for the rest of us!! I found your channel from #SoME3, and I've been binging the whole channel all day! Obviously stuff like the Busy Beaver blows me away and has ever since i first learned about it, but i really appreciate how you go deeply into the math and show worked out examples anywhere you can -- one of my favorite taken away so far was about Factor Analysis (I think? The one where you replace the multivariate normal data with a lower dimensional equivalent plus noise) and part 2 about the exponential function. I'm not naturally a statistics person at all, but once I learned enough math to understand function spaces and the like instead of "random chance" intuition, I fell in love with the topic! Your videos help to remind me why!
@@lexinwonderland5741 Excellent! That's exactly what I'm going for. If I keep all the nitty gritty details, that'll turn off a lot of people, but for some people (you and I) it'll really be appreciated. It's totally necessary stuff for that deep down understanding.
the halting problem might have something to do with start of physical reality (from infinite to finite)? numbers participate in transition from time to energy?
I feel there is something lacking about the last statement, that sound systems cannot proof their own soundness. It hinges on creating a Turing machine enumerating all proofs, and stopping when encountering "0 = 1", then invoking the halting problem by saying you cannot proof a Turing Machine halts. But that's not what the halting problem is. The halting problem says that there is no Turing Machine which can take any Turing Machine as input, and determine it halts on any input. But this does not imply you cannot determine whether a specific Turing Machine halts.
I think my explanation might be confusing here. I'm not proving Godel's theorem: "a consistent system can't prove it's own consistency." I'm asking the audience to accept that as a fact and than I'm using as part of the proof that S(n) = k cannot be proven beyond a point for any given system. In particular, we use Godel's theorem to construct a machine M for which we can prove that T can't prove M doesn't halt.
I was just waiting for Goedel to show up in the video :D I wonder if we can define a new sort of probabilistic axiomatic system. Instead of proofing theorems from axioms it would assign "propabilities of truethfullnes" to the derived theorems. Then these probabilities will propagate to deeper derived theorems via conditional probalities. Probably we end up in Quantum Computing and we can eventually compute probablities for the truethfullness of famous conjectures? Like: The probablity that the goldbach conjecture is true is 42%? That would be truely crazy :D
This would maybe also draw a bridge to the weird n-adic numbers because you could maybe say the probability of "1=1" being false would be 1 / --1 or 1/...9999999999 ? ¯\_(ツ)_/¯
Hmmm, sounds sus... E.g., we can derive a theorem in multiple ways using some other subtheorems. Since longer proofs use more statements with probability
Amazing vids, DJ. It's much easier to understand the topics you cover because of the exceptional graphics work. I am a career 3D animator and I have to ask... what software are you using? Something like Mathematica? If I had to hand animate all the stuff you do it would take forever!
For the animations (here, the turing machine), I'm using a Python plotting library called Altair, and then I have a personal library which turns them into videos. For the text, it's a personal library I use to reveal pieces of an image. I don't think I'm using is that efficient. These videos do in fact take me forever. People who are interested I'd say would be a lot faster if they use Manim. I don't use Manim because I'm trying to be different (and I'm ultimately not all that different lol)
@@Mutual_Information Okay, now I have some sense of your workflow. I suppose you will always need something like Altair to do the complex plots. They would take forever to generate any other way. But as to the rest of the process, I have to ask if you've considered using Blender? I have spent something like 40K hours in Blender, so naturally I'm a fan. But if I understand the situation correctly, you are probably chewing up a lot of evenings getting the timing right on all those intricate sequences of text/symbol exposition. Blender's animation controls are _extremely_ efficient. You could potentially reduce the temporal outlay for these vids quite a bit. Blender is also highly automatable using Python... and even Chat GPT! Blender has a feature set called geometry nodes as well. I can't tell you how powerful these tools are--you can do almost any kind of procedural/logic-based animation sequence quickly, and add a lot of extra visual flourishes which would take forever to code from scratch. Grant would be envious--Manim will never touch Blender for that kind of thing. You have my esteem for developing an awesome catalog of vids. I hope you pursue education rather than financial engineering--we really, really need more people like you to explain tricky concepts in math/CS for visual learners. P.S. The universe is a computer simulation, so your pontifications on the limits of computability gild the most profound questions that can ever be conceived. Detractors in the comments who deem this a whimsical preoccupation don't understand that they are staring at the edge... of everything.
@@Daniel-Six Blender is an incredible tool. I've been blow away by some of the demonstrations. It just looks like a lot of work to upskill on it and I'm a bit accustomed to my workflow. But that's not a great excuse. Do you have anything you'd recommend for using blender for math specific content?
@@Mutual_Information I have math/CS degrees from one of the top schools, I've been a programmer for forty years, built a multimillion dollar technical design firm and released software products professionally. I've done a few things in my life. And I'll tell you this; of all the ambitions I conscientiously pursued, Blender is without a doubt the one which returned the most to me. It's its own universe, and any production process you can bring into the app will become _much_ easier to execute. With your intellect (which is stronger than mine), you would find Blender incredibly enabling. It is designed for technically-minded people and employs Python as its scripting interface, so you can hook Altair into it with a little maneuvering. Everything about creating videos--even editing--will be accelerated after that. Also--I'm sure you can see the writing on the digital wall--things are swiftly moving to AR/VR. The Blender/UnrealEngine axis will soon be ground zero for modern play and pedagogy, and I can't think of more comprehensively useful skill.
0:49 To me, the hard thing about understanding computation, without getting into some pretty technical material on partial recursive functions or whatever, is understanding what counts as a "step". The whole definition hinges on this. In a von neumann architecture, what counts as a step? Is it the action of an individual logic gate? Or something higher level? In a brain, what counts as a step? A neuron firing? A neuron firing with a certain rate? An ion channel opening? Would love to know some approachable resources for this (or you could make a video)!
For a modern computer, executing one instruction is a step, and a program is a list of instructions. Different computer has its own set of executable instructions. At least that is how I think how modern computer works, maybe there are some weird designs make it more complicated to define what a step is.
The easiest way to actually count steps is to use Turing Machines - in a Turing Machine, steps are just state transitions. But you can just say, one instruction = one step, whatever. It barely matters - universality means that you can convert the units of one computational architecture to the units of another within at most a constant multiplier.
@12:40 no! That's the big thing computationalism misses. (Wolfram and all those nutcases.) Such truths are not "fundamentally unknowable" they are fundamentally non-computable. No one, not even the greatest philosophers of all time, know what "knowability" even means. I mean... talk to Srinivasa Ramanujan about it! (I had a go, but my time machine was missing a flux capacitor of the right alloy). Thing is, Ramanujan did not know where he pulled stuff out of the "platonic aether" from. And however he managed it, his insights were not knowably correct (he would've not even known the axiom scheme they applied best to). Just they _were _*_knowable_* (whatever that means). An imperfect inconsistent way of "seeing" truth can be (in principle) complete (whether it is useful or not is a whole different story - requires faith, and of course disappointment, since will often times be plain wrong). A consistent system on the other hand, while thus reliable, is necessarily incomplete.
Does it hold that for every N that there exists a computable, arithmetically sound axiomatic system A such that S(N) = k is a provable statement? In other words, for any 'k', with a good choice of a system A, it is possible to know S(k). The unknowability of S(N) = k is thus always in reference to a specific axiomatic system.
I'm trying to figure out how this relates to our process of higher order mathmatics. Solving a problem like Goldbach mathematically is equivalent to making true statements about that finite state machine, that it halts. But that doesn't tell us anything about how long it takes to halt or the BB number for n=27. This insight only goes one way. And yet, somehow, solving Goldbach mathmatically does allow us to either prove a finite state machine never halts. Or that it does halt, but this could be after a very large number of steps. Which we can do without having to run the program. So while you can't have a general algorithm for the stopping problem, we are solving it for a particular problem/machine. So are all, or some proportion of, mathmatical proofs equivalent to solving the stopping problem for a specific program. Our brains are untimately performing computations too. Are we complex finite state machines? it seems like the machine M which keeps enumerating all proofs and only halts if it finds a contradiction is us. The collective of mathmaticians is kinda that machine. Which then makes sense that our statements about that system start to break down. Maybe that connection is just aesthetic because we don't have a formal algorithm for enumeration of proofs. Or maybe it is meaningful and the algorithm for enumerating proofs is just a very complex process that we can't formalise that describes the mental process of mathematical proof formulation and collective work between humans. But perhaps I am streching the vaild domain for thinking about things in terms of finite state machines.
We absolutely have formal algorithms for enumerating proofs, they're just not *useful* because the interesting proofs are long enough that such an algorithm will never get to them within whatever reasonable time bound you place.
Can you please briefly explain why n * BB(n) does not grow faster than BB(n). I mean, obviously it does grow faster in the pedestrian sense, so you must have some, more subtle definition of "grow faster."
A True, Rounded Computer Scientist is also at least acquainted with Theoretical CS, such as the halting problem, etc. Otherwise, you're a coder, or interface designer, or whatever.
Why does a computation have to be finite? We have computations that, for instance, generate infinite digital sequences - eg the decimal expansion of pi. Can we not consider an infinite decimal sequence a computation (being the result of one)?
Presumably, "computation" is meant to refer to some real world procedure you can do to get an answer. If the computation is infinite, you can never get the answer. So "what things can be answered?" brings a "finite" requirement. It's less useful to make claims about what we can answer with infinite time (but people do that too).
Pi is a decimal sequence where we can compute the nth digit within a finite time, for any n - computing "all" digits is impossible, but we can engage in an infinite collection of finite computations to get Pi, whereas there exist numbers where there is some digit after which we cannot compute the decimal expansion in finite time.
A question: for any given proof of some mathematical fact, does there exist a system that can prove it? By that I mean, for any given mathematical statement in 'n' symbols, is there always some system with '>n' symbols that can prove it? Or are there statements that are unprovable for any number of symbols?
I think the question needs to be phrased a little differently.. "given any PROOF of some mathematical fact, ...". When you say "given any proof", that assumes some system in which the proof is expressed, and so the answer is yes, but it's not meaningful. I think you might mean.. "given any true statement, is there a system which can prove it?".. and I believe the answer is yes, because you can expand the system until it does what you want. But in doing so, you might make the system inconsistent, which many would say invalidates the system. Now, "given any true statement, is there a consistent system which proves it?". To that, I don't know.
There is a difference between true arithmetic statements and theorems that can be proved within an axiomatic system. This is the essence of Gödel’s first incompleteness theorem. And Turing’s approach to the undecidability of the halting problem can be modified to provide a proof of Gödel’s incompleteness theorems.
(please read in "average guy in way over his head" voice, lol) Gave me "the universe is a simulation" shivers to try and wrap my head around the idea that computation - as a concept - far outstrips the entirety of mathematics and axiomatic reasoning or rationality. It hurts the little meat computer in my head, and I had to just stand with my face in my hands for a while. We thought god was a man, then maybe a woman, or nothing at all... But maybe god is an AS/400?
Interesting, I never thought of that. I think that's probably less of interest because then you *must* keep track of all the machines, which makes this a heavier task and doesn't change the computability properties. The nice thing with it being one machine.. is you can talk about the single machine. All that needs to be known is that it produces more 1's than all others.
I wish God could just show up and prove with resounding clarity everything we don't know. Like just suddenly proving or disproving the Collatz conjecture effortlessly, with unbroken logic at every step. Ultimately the proof would be easy (if at all possible), as long as you just know what you're doing. But we'll surely take a lot longer to make progress on these problems, because, us being limited, take time to solve these things.
It's not that there's a Halts machine. It takes two. Both of them agree for all programs that aren't intentionally adversarial. Only when they simultaneously encounter the same Liar do they give opposite outputs. It is then that you know the program is a Liar that will halt for exactly one of the Halts outputs.
I'm thinking of a Halts program that just automatically outputs "halts". Any program that doesn't halt doesn't prove my Halts wrong without coincidentally proving (via some algorithm that proves the program won't halt) the existence of a different Halts (the "proof" algorithm) that won't be wrong.. ad infinitum. There is no possible program that can prove that no Halts program can exist because any "proof" is a self-defeating exercise.
I think there is a bug with posting links for some reason idk, im rewriting this for the 3rd time. I dont understand the connection between BB and Raimans Hypothesis, there is only one reddit post i found and in it people say its not a thing. When it comes to Goldbachs Conjecture there is more to read but i still dont understand
There's no connection to specific problems. It's the fact that proving things is in itself an algorithm, and a computer can go over all possible proofs to find whether a particular statement is provably true or provably false (or neither, in which case it won't halt). Also, in the specific cases you've mentioned we can use a different algorithm: look for counter-examples. If you find one then halt, otherwise keep looking. Then the problem has a counter example iff the machine halts. But in a way, looking for counter examples is the same as looking for a proof that the statement is false, so it's the same idea.
Is the shift function not always going to give a larger nunmber than the ones function? You said that they are both known as the busy beaver, so why does everyone refer to the ones function as the largest function?
the shift function is strictly larger. The naming issue has historical reasons. The shift function is easier to study theoretically, whereas the 1's function is what was presented as the original busy beaver game in Rado's paper. The 1's function is also easier to suggest is the 'largest output' because you can read it from the tape following the halt. Also, the shift function requires you keep a tally of shifts. By this point, it's just unsettled what should really be called "busy beaver" and so it's dictated by rpeference.
Yes totally! Aaronson think it's around 20. We have upper and lower bounds on it. It's at least 5 and less than a 1000 iirc. Because they created an actual TM with less than that many that runs through all the proofs of ZFC (modern foundation of mathematics)... and we know ZFC can't prove that thing halts.
@@Mutual_Information It's utterly baffling that it's such a "small" number. Given that in any axiomatic system there will be a point n_t, is it possible that with a larger axiomatic system we could push n_t>1000? (Even if that also involves proving some major unsolved problems like Goldbach?)
@@Killua2001 Yes the smallness is interesting! It shows how expressive a turing machine is and how fairly simple our axiomatic systems are. And to answer your question, sure, such a system could be constructed.
Circular reasoning is the culprit for why the proof is true! but the argument isn't circular. We're making statements about separate objects relating to each other.
Yes and that's why it'll run forever. The machine/program just give you a way to enumerate through them (and halt if a proof of a contradiction is found)
Unability of particular axiomatic system to get values for some busy beavers doesn't mean that it's not possible to create axiomatic system, which can do this.
Respectfully, I disagree. Essentially, for *any* given axiomatic system, there is a point where it can't prove S(n) = k. And if you were to create one, it's not clear how to. If you trivially include the conclusion, e.g. like S(1000) = 12311..971, you're likely to have accidentally created an inconsistent system. If you want to extend the system to not create an inconsistency and to prove more S(n) values, there's no systematic way to do so either. There's no way to choose such extensions.
@@Mutual_Information "no systematic way" that's what beavers are about if I understand correctly. "there is a point where it can't prove" - I agree. But better axiomatic systems should be possible nevertheless. I'm not mathematican, so I can't even guess how such systems may look like. But it is enough for me to know that there are no hard limits preventing people from upgrading their tools.
Given such an axiomatic system, turing machines can be constructed that would run that proof and then output slightly bigger numbers - you can force those machines to use more states to push up the point at which your system is forced to fail, but they can always be constructed in a finite number of states.
The fact that the human brain can comprehend these bizarre things proves that computers are nowhere close to humans, even if what is known as AGI exists, since they are also equivalent to some Turing machines.
What are those machines doing? I met some of them machines and they are mostly recommending ads to show to people ;). Some also manage the shopping cart and stuff.
Wait, *is* our mathematics computable? I think we use non-finite reasoning all the time. Actually wasn't that the constructivists issue with modern set theory, that it is NOT computable? Maybe I have only a partial understanding here... but I don't feel like its possible to "enumerate all proofs" which are possible in our axiomatic system. That's my intuition but I'd have to ask an expert
If the definition of computation has a finite sequence of steps, and that is part of the definition for a Turing machine, why does a Turing machine need an infinite tape? I've always known that to be part of the description of a Turing machine, but it doesn't seem necessary and might even be inappropriate. Shouldn't it just be a machine with sufficient but finite storage rather than infinite?
@@duncathan_salt the halting problem is whether or not there is a loop. It is a finite number of instructions which will not finish executing. If the premiss is that the tape is effectively the input, self modifying, and also the output, then perhaps you are right. I always saw the tape as being the instructions which defined the program. Therefore it seemed like a contradiction that the definition of the Turing machine has a finite sequence of steps but an infinite tape. `a: append 1 to the tape; goto a;` would satisfy finite steps but require infinite tape. Okay, I'm satisfied that there isn't a contradiction.
@@R.B. ah, yes, I believe you've identified your misconception! the tape is indeed just the I/O. the "program" is the machine's state table, which is indeed strictly finite
It took me a second too, but the intuition I think you’re going for is right. The related conjecture is that for any computable function f, f(S(n)) < S(n+1) for n beyond a point. And we haven’t proved it. We have some very weak bounds. We know S(n+1) > S(n) + 3, which at least shows it’s always increasing.
As one of the people referenced in Scott's papers, let me say you are definitely welcome. A
side from that, I would like to say your video did a really good job explaining where the Collatz aspect is showing up. There's another way that Collatz-like things showing up here is maybe not completely surprising: There's a theorem (I think originally due to Conway but I may be wrong there) that says essentially that you can go in the other direction and that determining whether a given Collatz-like system halts is exactly equivalent to the Halting problem. And the proof is essentially to model Turing machines using Collatz-like functions, where applying the function represents a step in the Turing machine. On the other hand, this theorem is not really a completely satisfying explanation here, because lots of different problem classes are equivalent to the Halting problem, and they don't show up here. So, in some sense, this may be happening because Collatz-like functions are one of the simplest things of this type, but this is not really satisfying as explanations go.
Joshua, it's great to hear from you and I'm happy you enjoyed the video. I feel a bit of regret because there was a segment I cut that discussed one of your conjectures - that the graph of every Busy Beaver is a strongly connected graph. If I understand correctly, it suggests that our programming languages, which rely on things like encapsulation, could never produce a Busy Beaver. I found that quite interesting. It makes clear, in a way I'd never enjoyed before, what's lost when we make programs easy for humans to use. Very cool!
And your comment "whether a given Collatz-like system halts is exactly equivalent to the Halting problem" almost doesn't surprise me by this point (thought I certainly didn't know about it) If this trip taught me anything, it's that many things can be converted into the halting problem. But I'd still be interested in understanding Collatz + the Halting Problem connection. I suspect the high chaos/simplicity ratio is just one way to see it.
Well, you can always do another video. Regarding the strongly connected conjecture, I'm not sure it says as strong a statement that our usual encapsulated style of program cannot produce a Busy Beaver. If you take a reasonably encapsulated program and try to naively make a Turing machine out of it, you'll often end up with a strongly connected graph. It says more that Busy Beavers shouldn't be coming from every doing program compositions, where we first run program X, and then after run program Y on the output of X. Also worth recognizing that this is an extremely weak property. The proportion of Turing machines which have strongly connected graphs as the size of the machines goes up goes to 1. So this is really even if true ruling out only a tiny fraction of all machines. (In fact, someone else suggested, (maybe Nick Drozd ?) that we should expect that for any property P that almost directed graphs have should be a property that all sufficiently large Busy Beaver graphs have. Which if true would mean that there's no hope of really drastically reducing the set of candidate machines at any stage.
@@joshuazelinsky5213 Ah I see - well now I'm less regretful, as I would have said something wrong!
But now I'm curious. If we have a TM that is not strongly connected, does that imply *anything* about the program that we would conventionally recognize? E.g. something like-but-different from encapsulation?
@@Mutual_Information Yes, it would say something like that it was functionally running one program and then running another program on that program's output.
Each time one passed into a new section and could not go back, it would be essentially analogous to that.
I think, but am not sure that the closest thing to not being actually encapsulated would be some sort of statement that we should see very large subsets of states with only a tiny number of in and out flows into that state set, since those subsets would essentially represent subfunctions or subprocedures then.
Unfortunately, we have so few values of BB where we can actually prove much, that all of these things are conjectures with very little empirical data behind them. A divine being, or at least a being with access to a Halting oracle might find a lot of our guesses here pretty laughable.
@@Mutual_Information Also, I should note that in all fairness to you, when I initially made the strong connectedness conjecture, I interpreted it the same way you are doing, and it took conversations with other people to realize that it was not quite saying something as strong as I thought it was about encapsulation and spaghetti code.
I really wish this video never halted
Poetic, few words, but poetic
in that case i'd wish it halted
I did an old fashioned computer science degree in the late 80's. Godel/Turning/Church blew my mind when I realised that godel used maths to prove that maths cannot fully explain the universe. And the trigger for it all was Bertrand Russle's logical pardox "This statement is false". Very informative videos, I did not realise that busy beaver and collatz were essentially the same thing
the fact that theres such a fundamental relationship between ideas in math is, ironically, fundamental to math itself. Since math js an axiomatic system and many fields seem to represent the same "logical core" there are tons of areas of overlap that are blurred through the double-vision of varying syntactic interfaces. Ive come to realise this many times and independently. Math is truly amazing
That's because maths like language is a tool for describing the universe and it's inner workings. This basically makes math a language
13:23 So to prove ZF is consistent, we must use a more powerful axiom-system. But since this new A.S. cannot prove its own consistency either, we need yet another A.S. more powerful, and so on, until the completeness of the system causes it to have inconsistencies! So it's impossible to prove ZF consistent, no matter how hard we try!
This reminds me of a connection I found between time-travel, the observer effect, fluid dynamics, and the halting problem. Here's the short explanation:
If you want a 100% accurate weather forecast, you must *simulate the observable universe,* but you need a 2nd universe to build+store the machine (or use the new universe itself as the simulation). But the very act of observing the simulation requires a *2nd pair of simulations,* then we must double the number of universes *recursively* until we get an unmanageable multiverse.
So light-speed and causality aren't the only things preventing to predict the future, it's the observer-effect and the halting-problem too!
Indeed, multiple reasons why omniscient knowledge is forever out of reach
Your previous busy beaver video made me finally understand what BB is and I became obsessed with it. I'm not completely following this one just yet. Will try rewatching a few times, but thank you for continuing to deep dive on this topic!
One of the problems with proving something by waiting on some Turing machine reaching the BB-limit, is that it will probably be easier to to resolve Goldbach than to prove the upper bound on BB(27)
Oh yea, 100%
The interesting part is that it kind of proves that it is possible to prove it, if just not by that specific method in any reasonable time.
My understanding is that its impossible to know BB(27) without already having solved Golbach. (and every other B(27) machine).
This is because in order to prove that our BB(27) machine is the one that produces the largest value, we would need to prove that Goldbach eighter halts with smaller value, or that it never halts.@@kindlin
@@LostOter Oh no, YT ate my comment. Anyways, what I was trying to say, was, just the fact that the BB(27) method exists, even if it is entirely nonfeasible in any real computation, implies (or maybe proves?) that there is a proof (or anti proof) of the conjecture. The only other outcome would be if that proof was actually the BB(27) method, in which case it's just the trivial answer, but I'm willing to bet that's not the case.
It's impossible to use BB to prove anything, even if we had the values of the function for any n given to us by god. We would need an absurd amount of memory and time, as well as a machine that defies all known laws of thermodynamics.
I genuinely would love to hear you talk more about these theories and papers
I know enough about these theories and concepts to follow, and you make learning more those concepts really easy to follow as well
You're my target audience - people who already knew a good deal and aren't spooked by math :)
To set expectations, I don't plan on going further on these topics in the near future. This was a bit of a detour for me
I'm in the same boat. However the science is pretty much an empty sheet after you internalized scots busy beaver frontier. Super interesting but also very limited
This video is absolutely incredible. The fact that many famous math problems can be connected to the halting problem totally blew my mind. Thank you for creating this amazing and educational content!!
And thank you for watching :)
I hope this channel blows up, because this video and its prequel are incredible learning videos.
This is actually the best video I've seen about the busy beavers. I never thought about it in that perspective!
Wow, I found it weird that the incompleteness theorems were somehow linked to the halting problem but this makes a lot of sense now
I knew there was a connection, but hadn't seen it this clearly. In the end mathematics itself is just a programming language. Anything that applies to python or C++ is bound to math, which is just another set of symbols we ascribe meaning to.
Thank you very much for this insight into busy beaver. It always fascinated me, but I did not have much (and still dont have) opportunity to dive deeper into the topic. This is awesome summarisation and personally I am hoping for more insight into this. You are doing it really well.
appreciate that, means a lot.. and thank *you* for watching my stuff
Your videos are absolutely amazing. As someone looking for intuitive technical rigor, this is perfect for understanding the foundations for complex concepts and always helps and inspires me to better filter the technical jargon throughout the field.
Excellent. When making this videos, I am targeting a specific audience. Those who aren't afraid of math who want to learn more. Sounds like you're right in the center of it
@@Mutual_Information thank you sir; you are without question providing invaluable information to those hungry for learning and applying these fundamental mathematical concepts. With the explosion of AI; I am sure there are hungry/curious researchers out there trying to push the boundaries of computation and are getting productive inspiration from your videos (just as I have been in the past few). Thanks from all of us :)
3:20 these unexpected links are so mind blowing to me - "how can 2 things that seem so disparate be connected?"
When these connections finally come to light, I do wonder if our brain also makes physical connections from the neurons representing one concept to the neurons representing the other concept.
yea I bet that's true too
At 11:45-12:26 the T about the halting problem sounded something similar to a topos. In “A simple presentation of the effective topos” (2013) by Bernadet and Graham-Lengrand at their intro I found a similar statement that an effective topos which describes ones that are “computable” and have the natural numbers lack the law of excluded middle. Other 2-out-3 cases are mentioned there.
Phenomenal job with this and the previous video. First Busy Beaver videos on RUclips in years that I think extend the understanding of laymen like me.
Thank you my dude
@@Mutual_InformationNo problem. Just to expand on that: the graphics, the clarity in how you phrase things, the level of detail you give the tricky concepts, your general diction. It really is outstanding, watching these videos was like someone unfogged the glass for me on a number of concepts I'd previously found opaque.
To put it another way, I think there might actually be nothing in existence that I couldn't understand with one of your videos. So as a maths guy, I can only hope you've enjoyed this venture into the computer science/maths border. Now if you could explain to me why TREE(n) is estimated to be at the SVO, or why SSCG(2) = 3.241704 × 10^35775080127201286522908640065, that would be nirvana. But I suppose you've got to think of your other viewers 😝
@@joebloggs3551 You're too kind Joe - it's much appreciated! And I'd love to answer those questions, if only I knew them :)
Great video. I am not that knowledgeable in mathematics or computation at all, but I could sense near the end that you were going to tie things together with Godel's incompleteness theorem and the halting problem. I think that Godel, Escher, Bach actually discusses this part quite well, although it doesn't reference the busy beaver function. The parts about these 2 videos that really blew my mind were that: a) there are BB functions that encode the answers to famous unsolved mathematical conjectures, and b) there is a point beyond which BB functions become undecideable with the rules of mathematics that we currently use.
Yea! we feel the same
I'd add the third revelation:
c) If for a given hypothesis you can create a Turing machine which checks all the possible options for counterexamples, then there exists a natural number beyond which it is guaranteed no counterexample exists, hence you have to check only finitely many cases to be sure if the hypothesis is true or not.
If I understand correctly, this means that for any hypothesis about prime numbers only finitely many prime numbers are important. Extremely large prime numbers are completely irrelevant and you get the theorem for those numbers for free once you check if the hypothesis is true for those relevant "small" prime numbers. This is completely mindblowing.
@@piotr.ziolo. Nicely generalized! The video explains the example problems (e.g. GoldBach) only b/c it's easier to digest. But the real punch is in the general case, as you point out
Busy Beaver 5 is now known! For certain, to be 47,176,870 steps to reach 4,098 ones!
These videos are one of the best I have ever seen. Because there are so many natural questions, I feel really encouraged to seek out the topic for myself!
If I can suggest another topic for a video, it would have to be the ordinals, from a general point of view, not from ZFC.
The question from which the ordinals naturally arise is: "which are the different permanent states of a mathematical statement, hypothetically".
For every collection of states, you can hypothetically proof that the "proof state" of a statement is none of these.
This is exactly what the ordinals are.
This is not just about pure logic, it really hits close to computation as well, especially the Church-Kleene ordinal.
That's an interesting topic for sure, but I can't say I'm prepare for that video in particular. I have a long queue I've been meaning to get to, but I do hope to get back to computational complexity eventually.
What an amzing video!
Especially at the end where you explain the connection between the halting problem and many other famous math problems🤯 As a first year computer science undergrad videos like this are a true motivation❤ What did you study? Or are you still studying🤔
Thank you! Glad you feel the way I do on this one.
I studied math and econ in undergrad. And then I studied financial engineering in grad school. This computation complexity isn't in my wheel house. I just went down a strange rabbit hole.
But keep studying! Eventually, you understand the language of rigor and precision and once you've learned a few subjects, it becomes easier to go into the next one. Also, you meet others who understand the things you'd like to learn, so you ask them too. I'm very grateful that I took an interest in nerdy stuff awhile ago, because it really does open up a lot of technical worlds to you (if you're into that).
Only have seen two videos from your channel and am hooked... you are somehow translating what I perceive about math but can't always put into words... subbed!
builtbygamers type videos about a topic this technical and detailed is insane
Amazing, NO WORDS Just AMAZING :0
9:00 we can assume that a beaver is lost
This video explains the concept of why we know everything and don't know everything at the same time. We know everything because we can compute everything but we don't know everything because we can't compute everything fast enough.
you are a G
I like small channels like yours that do interesting videos
Commenting for the algorithm, another great video!
Awesome, thank you!
Thank you for the effort to provide this insight. Mind-bending.
Ngl, I feel like this busy beaver thing is an Overkill idea that definitionally is the limit of computation.
It's like a programming language for math that doesn't solve any problems, just makes them concrete/well-defined.
It's like the incompleteness theorems, by definition somethings are impossible to prove/disprove.
Disclaimer: this is just my opinion based off watching the last two videos.
That's a fair perspective. Essentially, we are doing exactly that - merely specifying doable/not-doable when it comes to proofs and computation.
To some, but not all, it's fascinating because it's hard to imagine what isn't provable or computable. But this is a matter of taste. I've spoken with friends who think it's utterly unsurprising that you can't prove everything.
Would be nice if you covered non deterministic turing machines, NP-Completeness and SAT solvers as the next step!
NP-Completeness is in a way a finite length approximation of the halting problem: if we can efficiently solve SAT then we can attack math theorems by exploring all the proofs of length
I would be stretching myself to get into those topics. I may gear up for it by starting to read a text on the side. I recall there was a short textbook that was praised for it's succinct coverage, but I can't find it. Or at least, all the recommended books don't look short. Any chance you know what I'm referring to?
@@Mutual_Information Unfortunately not, but I was able to find something you might find interesting: it's a correspondence letter between Godel and Von Neumann where he explains how despite the halting problem, a fast enough turing machine could displace mathematicians! Search for "gwern godel letter", you should find a reference at Gwern's math index (I cannot type it here, bar the comment getting autoremoved).
Checking whether a provided proof for a logical statement is correct is easy to do (polynomial time), making this problem in the class NP! The SAT problem is fundamentally about this.
@@mgostIH I'd never heard of this - very cool. I added it a list of potential topics I'll cover one day. It's pretty interesting to cover the ponderings of the greats..
Is a non deterministic Turing machine like the logical equivalent of an abstract infinitely strong quantum computer, like the Turing machine is the abstract classical computer?
@@dekippiesip Not quite, quantum effects are different from parallelism, you can think of a NDT as a turing machine that has unbounded parallel threads to solve any problem.
you can analyse continouse version of SAT problem - it show what happens at boundary of computation really well...
Excellent video, an eye-opening “appetizer”. I know just enough about the subjects to recognize that I have so much more to learn.
I really enjoy these videos as someone who likes math and googology (the study of large numbers) :)
My reaction when you revealed "The Collatz Conjecture" was an incredible feeling of "What does THAT have to do with anything?!". That is the mark of a good math surprise.
Also, the unprovability feels absurd. Like, BB(1000) exist - it IS a number - but we can't prove what it is. Does the halting/not halting behavior of machines depend on the system? It feels like it shouldn't, but that assumption leads to results that feel absurd.
"There exists a Turing Machine M incomprehensible to mathematics" - I think this is only true for any fixed system of axioms (like ZFC)? Like otherwise you can just add "M halts/M doesn't halt" as an axiom and the system remains consistent? Isn't this just Goedel/large cardinals all over again? We already know that ZFC is not "perfect", and we might need to add new axioms eventually (e.g. CH or ~CH).
My (intuitive, informal, and possibly incorrect) understanding of why TMs & BBs are so powerful (i.e. "more powerful" than axiomatic systems) is because they effectively "enumerate logic". Given an axiomatic system, there will be a TM able to enumerate all of its proofs/theorems.
Yes, but I think it defeats the purpose of a system if we extend it with the conclusions we want. Ideally, we could extent it only mildly to gain a handle a machine M, but which specific extension to include is now the question.
Regarding your intuition, I like the way you put it. If we use the enumeration of logic itself, we can construct things it can't handle.
@@Mutual_Information I just rewatched these and came up with an idea - iirc, there is intuitively a BB number that's the boundary of computable and uncomputable. HALT (the halting problem) is an example of a proven undecidable problem. The way we prove it is give an example TM M that if we "fed" into the HALT-TM, we would get a contradiction.
I've been wondering - how many states do we need to construct M (when the alphabet is just 2 symbols)? Or, more generically, what's the smallest number n for which a TM with that many states exists, and it disproves (forms a counterexample to, if you may) a known undecidable problem? Wouldn't that number give us an idea of when Busy Beavers become uncomputable?
Edit: I found a claim somewhere that there is a Universal TM with 24 states and 2 symbols, so n
For any system of mathematics, there are procedures to construct Turing Machines that are incomprehensible to the given system. Personally, I find it more interesting that there are also procedures to construct Turing Machines that are *just a little* comprehensible to a system of math, where the Turing Machine can be constructed to be universal if only if it cannot be proven to be universal, and to still allow proving surprisingly many properties that one would intuitively think are sufficient to give universality.
6:08 I'd like to point out that there's a "shortcut" Collatz fn, which is even more similar to the BB one!
next up you will solve the P vs NP problem and the clay institute will give you a million dollars, correct?
Lol I think there's a wide gap between making a shiny RUclips video and actually solving extremely hard problems, but I appreciate the vote of confidence!
@@Mutual_Information anytime sir, I am hopeful
If I had to guess, the answer to "are P and NP the same?" is probably solvable by BB(128)
I don’t understand 33% of what you said which means I probably really only grasped 33% of it but nonetheless this two part series was dope! Subbed!
Amazing video, a really good follow up.
Subscribed
I'm honored, thank you!
Okay, I think I’m starting to understand. In other words, if we run each machine for a given input, the machine that generates the largest finite number is a Busy Beaver. Of course some machines go on to infinity. However, as the inputs get larger, we can’t know if a machine is a Busy Beaver or not, because it could simply never halt. Or it might. But it would take an eternity. But also, there has to be a Busy Beaver for every single number, right? Because that’s what logic would dictate.
Extremely interesting topic, and well explained. Thank you!
One question though. Regarding the axiomatic system A and the N for which there exists a TM with N states sich that it proves whether all statements are provable in A - sure bute that is the ultimate bound, right? Surely there exists M much smaller than N such that S(M) is ulready unprovable in A. We could then classifiy the "provability span" of a system by such M, right? For example, our current mathematical system might have M = 27 🤔
Interesting, didn't think of that. Yea that would be my guess as well.
What about this alternative proof of 11:27 :
Assume by way of contradiction, for all N there exists n>N and k such that you can prove S(n) = k. We will decide the halting problem:
Given a turing machine of size N, go over all n>N and all k and all proofs of S(n) = k. We can do that strategically to not get stuck and find the promised n,k which we know exist. Now run the given turing machine for k steps and check if it halts. It has less states than n and S(n) = k, so if it halts it surely halts before that. (if we add dummy states to it we can make it an n-state machine, so the S(n) limit applies to it as well).
Yea, that's the alternative. Assume you can and you're gov something that can solve the halting problem, and we know that's not true.
I didn't go with that one because it seems to shift the mystery from S(n) = k to the halting problem, which many, myself included, find mysterious itself. I'm happier using the fact that a consistent system can't prove it's own consistency. But that's just a matter of taste
i wonder if this is one of those problems a quantum computer could solve for determining if S(27) halts or continues forever
So... when's the video on the Conjectures coming out? Because we NEED to hear you tell us more about this beauty!!
lol oh man.. my topic list never shrinks!
@Mutual_Information that's very lucky for the rest of us!! I found your channel from #SoME3, and I've been binging the whole channel all day! Obviously stuff like the Busy Beaver blows me away and has ever since i first learned about it, but i really appreciate how you go deeply into the math and show worked out examples anywhere you can -- one of my favorite taken away so far was about Factor Analysis (I think? The one where you replace the multivariate normal data with a lower dimensional equivalent plus noise) and part 2 about the exponential function. I'm not naturally a statistics person at all, but once I learned enough math to understand function spaces and the like instead of "random chance" intuition, I fell in love with the topic! Your videos help to remind me why!
@@lexinwonderland5741 Excellent! That's exactly what I'm going for. If I keep all the nitty gritty details, that'll turn off a lot of people, but for some people (you and I) it'll really be appreciated. It's totally necessary stuff for that deep down understanding.
Will you do another vid about the bb? I wanna keep hearing about all of it :)
I have no plans in the short term :/ there's a few other topics in the machine learning space I'd like to get back to. But in the longer term, maybe!
Amazing video
the halting problem might have something to do with start of physical reality (from infinite to finite)? numbers participate in transition from time to energy?
I feel there is something lacking about the last statement, that sound systems cannot proof their own soundness. It hinges on creating a Turing machine enumerating all proofs, and stopping when encountering "0 = 1", then invoking the halting problem by saying you cannot proof a Turing Machine halts.
But that's not what the halting problem is. The halting problem says that there is no Turing Machine which can take any Turing Machine as input, and determine it halts on any input. But this does not imply you cannot determine whether a specific Turing Machine halts.
I think my explanation might be confusing here. I'm not proving Godel's theorem: "a consistent system can't prove it's own consistency." I'm asking the audience to accept that as a fact and than I'm using as part of the proof that S(n) = k cannot be proven beyond a point for any given system. In particular, we use Godel's theorem to construct a machine M for which we can prove that T can't prove M doesn't halt.
I was just waiting for Goedel to show up in the video :D
I wonder if we can define a new sort of probabilistic axiomatic system. Instead of proofing theorems from axioms it would assign "propabilities of truethfullnes" to the derived theorems. Then these probabilities will propagate to deeper derived theorems via conditional probalities. Probably we end up in Quantum Computing and we can eventually compute probablities for the truethfullness of famous conjectures? Like: The probablity that the goldbach conjecture is true is 42%? That would be truely crazy :D
This would maybe also draw a bridge to the weird n-adic numbers because you could maybe say the probability of "1=1" being false would be 1 / --1 or 1/...9999999999 ? ¯\_(ツ)_/¯
This already exists, google "Fuzzy logic". Maybe also "Godel logic", or "Many valued logic" in general
Hmmm, sounds sus...
E.g., we can derive a theorem in multiple ways using some other subtheorems.
Since longer proofs use more statements with probability
Amazing vids, DJ. It's much easier to understand the topics you cover because of the exceptional graphics work. I am a career 3D animator and I have to ask... what software are you using? Something like Mathematica? If I had to hand animate all the stuff you do it would take forever!
For the animations (here, the turing machine), I'm using a Python plotting library called Altair, and then I have a personal library which turns them into videos. For the text, it's a personal library I use to reveal pieces of an image.
I don't think I'm using is that efficient. These videos do in fact take me forever. People who are interested I'd say would be a lot faster if they use Manim. I don't use Manim because I'm trying to be different (and I'm ultimately not all that different lol)
@@Mutual_Information Okay, now I have some sense of your workflow.
I suppose you will always need something like Altair to do the complex plots. They would take forever to generate any other way. But as to the rest of the process, I have to ask if you've considered using Blender?
I have spent something like 40K hours in Blender, so naturally I'm a fan. But if I understand the situation correctly, you are probably chewing up a lot of evenings getting the timing right on all those intricate sequences of text/symbol exposition. Blender's animation controls are _extremely_ efficient. You could potentially reduce the temporal outlay for these vids quite a bit. Blender is also highly automatable using Python... and even Chat GPT!
Blender has a feature set called geometry nodes as well. I can't tell you how powerful these tools are--you can do almost any kind of procedural/logic-based animation sequence quickly, and add a lot of extra visual flourishes which would take forever to code from scratch. Grant would be envious--Manim will never touch Blender for that kind of thing.
You have my esteem for developing an awesome catalog of vids. I hope you pursue education rather than financial engineering--we really, really need more people like you to explain tricky concepts in math/CS for visual learners.
P.S. The universe is a computer simulation, so your pontifications on the limits of computability gild the most profound questions that can ever be conceived. Detractors in the comments who deem this a whimsical preoccupation don't understand that they are staring at the edge... of everything.
@@Daniel-Six Blender is an incredible tool. I've been blow away by some of the demonstrations. It just looks like a lot of work to upskill on it and I'm a bit accustomed to my workflow. But that's not a great excuse. Do you have anything you'd recommend for using blender for math specific content?
@@Mutual_Information I have math/CS degrees from one of the top schools, I've been a programmer for forty years, built a multimillion dollar technical design firm and released software products professionally. I've done a few things in my life.
And I'll tell you this; of all the ambitions I conscientiously pursued, Blender is without a doubt the one which returned the most to me. It's its own universe, and any production process you can bring into the app will become _much_ easier to execute.
With your intellect (which is stronger than mine), you would find Blender incredibly enabling. It is designed for technically-minded people and employs Python as its scripting interface, so you can hook Altair into it with a little maneuvering. Everything about creating videos--even editing--will be accelerated after that.
Also--I'm sure you can see the writing on the digital wall--things are swiftly moving to AR/VR. The Blender/UnrealEngine axis will soon be ground zero for modern play and pedagogy, and I can't think of more comprehensively useful skill.
Pft! I coded stuff that blew up my first week! Still writing stuff that blows up to this day. Idk why I just love recursion.
I'd raise the volume
Many RUclips videos have this problem. On Firefox, I use the "SoundFixer" extension - VERY handy at times! 😁
psa: abstracting abstraction itself breaks the universe
lol yes be careful out there
Amazing explanation, you earned a sub.
0:49 To me, the hard thing about understanding computation, without getting into some pretty technical material on partial recursive functions or whatever, is understanding what counts as a "step". The whole definition hinges on this.
In a von neumann architecture, what counts as a step? Is it the action of an individual logic gate? Or something higher level?
In a brain, what counts as a step? A neuron firing? A neuron firing with a certain rate? An ion channel opening?
Would love to know some approachable resources for this (or you could make a video)!
For a modern computer, executing one instruction is a step, and a program is a list of instructions. Different computer has its own set of executable instructions. At least that is how I think how modern computer works, maybe there are some weird designs make it more complicated to define what a step is.
The easiest way to actually count steps is to use Turing Machines - in a Turing Machine, steps are just state transitions.
But you can just say, one instruction = one step, whatever. It barely matters - universality means that you can convert the units of one computational architecture to the units of another within at most a constant multiplier.
maybe only the first number(s) have practical relevance, similar to Feinman renormalization?
thanks! very intresting:)
shouldnt s(x) be faster than bb(x)? because the number of ones is always smaller than the number of steps
Yes it grows faster, because to write a new 1, you have to shift.
@12:40 no! That's the big thing computationalism misses. (Wolfram and all those nutcases.) Such truths are not "fundamentally unknowable" they are fundamentally non-computable. No one, not even the greatest philosophers of all time, know what "knowability" even means. I mean... talk to Srinivasa Ramanujan about it! (I had a go, but my time machine was missing a flux capacitor of the right alloy). Thing is, Ramanujan did not know where he pulled stuff out of the "platonic aether" from. And however he managed it, his insights were not knowably correct (he would've not even known the axiom scheme they applied best to). Just they _were _*_knowable_* (whatever that means).
An imperfect inconsistent way of "seeing" truth can be (in principle) complete (whether it is useful or not is a whole different story - requires faith, and of course disappointment, since will often times be plain wrong). A consistent system on the other hand, while thus reliable, is necessarily incomplete.
I appreciate after 13 mins you sort of acknowledged this. Nice channel of content you have I must say.
Does it hold that for every N that there exists a computable, arithmetically sound axiomatic system A such that S(N) = k is a provable statement? In other words, for any 'k', with a good choice of a system A, it is possible to know S(k). The unknowability of S(N) = k is thus always in reference to a specific axiomatic system.
can Turing machine help to find measurement of quantum wave function?
I'm trying to figure out how this relates to our process of higher order mathmatics. Solving a problem like Goldbach mathematically is equivalent to making true statements about that finite state machine, that it halts. But that doesn't tell us anything about how long it takes to halt or the BB number for n=27. This insight only goes one way.
And yet, somehow, solving Goldbach mathmatically does allow us to either prove a finite state machine never halts. Or that it does halt, but this could be after a very large number of steps. Which we can do without having to run the program. So while you can't have a general algorithm for the stopping problem, we are solving it for a particular problem/machine. So are all, or some proportion of, mathmatical proofs equivalent to solving the stopping problem for a specific program.
Our brains are untimately performing computations too. Are we complex finite state machines? it seems like the machine M which keeps enumerating all proofs and only halts if it finds a contradiction is us. The collective of mathmaticians is kinda that machine. Which then makes sense that our statements about that system start to break down.
Maybe that connection is just aesthetic because we don't have a formal algorithm for enumeration of proofs. Or maybe it is meaningful and the algorithm for enumerating proofs is just a very complex process that we can't formalise that describes the mental process of mathematical proof formulation and collective work between humans. But perhaps I am streching the vaild domain for thinking about things in terms of finite state machines.
We absolutely have formal algorithms for enumerating proofs, they're just not *useful* because the interesting proofs are long enough that such an algorithm will never get to them within whatever reasonable time bound you place.
Can you please briefly explain why n * BB(n) does not grow faster than BB(n). I mean, obviously it does grow faster in the pedestrian sense, so you must have some, more subtle definition of "grow faster."
Because the statement is "BB(n) grows faster than any *computable* function". BB(n) itself isn't computable, so neither is n*BB(n).
@@Mutual_Information Oh! Thank you for straightening me out! Your presentation is extraordinarily good.
This kind of nonsense is why I'm a computer scientist not a mathematician 😂😅
A True, Rounded Computer Scientist is also at least acquainted with Theoretical CS, such as the halting problem, etc. Otherwise, you're a coder, or interface designer, or whatever.
@@Julian-tf8nj thanks for your input buddy 👍 I'll be sure to revisit the basics right after I'm done with the PhD I'm currently doing
Why does a computation have to be finite? We have computations that, for instance, generate infinite digital sequences - eg the decimal expansion of pi. Can we not consider an infinite decimal sequence a computation (being the result of one)?
Presumably, "computation" is meant to refer to some real world procedure you can do to get an answer. If the computation is infinite, you can never get the answer. So "what things can be answered?" brings a "finite" requirement. It's less useful to make claims about what we can answer with infinite time (but people do that too).
Pi is a decimal sequence where we can compute the nth digit within a finite time, for any n - computing "all" digits is impossible, but we can engage in an infinite collection of finite computations to get Pi, whereas there exist numbers where there is some digit after which we cannot compute the decimal expansion in finite time.
mind blowing
A question: for any given proof of some mathematical fact, does there exist a system that can prove it? By that I mean, for any given mathematical statement in 'n' symbols, is there always some system with '>n' symbols that can prove it? Or are there statements that are unprovable for any number of symbols?
I think the question needs to be phrased a little differently.. "given any PROOF of some mathematical fact, ...". When you say "given any proof", that assumes some system in which the proof is expressed, and so the answer is yes, but it's not meaningful. I think you might mean.. "given any true statement, is there a system which can prove it?".. and I believe the answer is yes, because you can expand the system until it does what you want. But in doing so, you might make the system inconsistent, which many would say invalidates the system. Now, "given any true statement, is there a consistent system which proves it?". To that, I don't know.
There is a difference between true arithmetic statements and theorems that can be proved within an axiomatic system. This is the essence of Gödel’s first incompleteness theorem. And Turing’s approach to the undecidability of the halting problem can be modified to provide a proof of Gödel’s incompleteness theorems.
(please read in "average guy in way over his head" voice, lol)
Gave me "the universe is a simulation" shivers to try and wrap my head around the idea that computation - as a concept - far outstrips the entirety of mathematics and axiomatic reasoning or rationality. It hurts the little meat computer in my head, and I had to just stand with my face in my hands for a while.
We thought god was a man, then maybe a woman, or nothing at all... But maybe god is an AS/400?
lol, a computer god would make more sense than a hairy meat sack organism
wouldnt it be larger if we counted the 1s printed by all machines that halted, instead of just those printed by the machine that printed the most?
Interesting, I never thought of that.
I think that's probably less of interest because then you *must* keep track of all the machines, which makes this a heavier task and doesn't change the computability properties. The nice thing with it being one machine.. is you can talk about the single machine. All that needs to be known is that it produces more 1's than all others.
I wish God could just show up and prove with resounding clarity everything we don't know. Like just suddenly proving or disproving the Collatz conjecture effortlessly, with unbroken logic at every step. Ultimately the proof would be easy (if at all possible), as long as you just know what you're doing. But we'll surely take a lot longer to make progress on these problems, because, us being limited, take time to solve these things.
10:25 any **halting** 27-state machine
The last proof made sense to me except I'm not sure what it's conclusion that T can't prove M never halts has to do with S(n) = k being unprovable.
It's not that there's a Halts machine. It takes two. Both of them agree for all programs that aren't intentionally adversarial. Only when they simultaneously encounter the same Liar do they give opposite outputs. It is then that you know the program is a Liar that will halt for exactly one of the Halts outputs.
Continue with busy beaver in your other videos. Examples, proofs as concretely as you can.
I'm thinking of a Halts program that just automatically outputs "halts". Any program that doesn't halt doesn't prove my Halts wrong without coincidentally proving (via some algorithm that proves the program won't halt) the existence of a different Halts (the "proof" algorithm) that won't be wrong.. ad infinitum. There is no possible program that can prove that no Halts program can exist because any "proof" is a self-defeating exercise.
I think there is a bug with posting links for some reason idk, im rewriting this for the 3rd time. I dont understand the connection between BB and Raimans Hypothesis, there is only one reddit post i found and in it people say its not a thing. When it comes to Goldbachs Conjecture there is more to read but i still dont understand
There's no connection to specific problems. It's the fact that proving things is in itself an algorithm, and a computer can go over all possible proofs to find whether a particular statement is provably true or provably false (or neither, in which case it won't halt). Also, in the specific cases you've mentioned we can use a different algorithm: look for counter-examples. If you find one then halt, otherwise keep looking. Then the problem has a counter example iff the machine halts. But in a way, looking for counter examples is the same as looking for a proof that the statement is false, so it's the same idea.
What about running busy beaver on quantum computer?
Mathematics at this level is so intimidating like wtf
Can't you just reverse compute ergo backtrack the steps leading to Goldbach's conjecture or similar problems?
I'm not exactly sure what you're suggesting. What do you mean specifically?
You’re the math version of Jon Solo haha!
Is the shift function not always going to give a larger nunmber than the ones function? You said that they are both known as the busy beaver, so why does everyone refer to the ones function as the largest function?
the shift function is strictly larger. The naming issue has historical reasons. The shift function is easier to study theoretically, whereas the 1's function is what was presented as the original busy beaver game in Rado's paper. The 1's function is also easier to suggest is the 'largest output' because you can read it from the tape following the halt. Also, the shift function requires you keep a tally of shifts. By this point, it's just unsettled what should really be called "busy beaver" and so it's dictated by rpeference.
more please.
If S(27) encodes Goldbach, and if Goldbach is true AND unprovable, would that suggest that n_T
Yes totally! Aaronson think it's around 20. We have upper and lower bounds on it. It's at least 5 and less than a 1000 iirc. Because they created an actual TM with less than that many that runs through all the proofs of ZFC (modern foundation of mathematics)... and we know ZFC can't prove that thing halts.
@@Mutual_Information It's utterly baffling that it's such a "small" number. Given that in any axiomatic system there will be a point n_t, is it possible that with a larger axiomatic system we could push n_t>1000? (Even if that also involves proving some major unsolved problems like Goldbach?)
@@Killua2001 Yes the smallness is interesting! It shows how expressive a turing machine is and how fairly simple our axiomatic systems are. And to answer your question, sure, such a system could be constructed.
13:54
Wait, but isn't that just circular reasoning ?
Circular reasoning is the culprit for why the proof is true! but the argument isn't circular. We're making statements about separate objects relating to each other.
At the end- how can a turing machine enumerate all proofs in a system T? Surely there are infinite?
Yes and that's why it'll run forever. The machine/program just give you a way to enumerate through them (and halt if a proof of a contradiction is found)
what software do you and 3blue1brown use to make the animations? btw do a video on shannon's law
3Blue1Brown uses Grant Sanderson's Manim
Unability of particular axiomatic system to get values for some busy beavers doesn't mean that it's not possible to create axiomatic system, which can do this.
Respectfully, I disagree. Essentially, for *any* given axiomatic system, there is a point where it can't prove S(n) = k. And if you were to create one, it's not clear how to. If you trivially include the conclusion, e.g. like S(1000) = 12311..971, you're likely to have accidentally created an inconsistent system. If you want to extend the system to not create an inconsistency and to prove more S(n) values, there's no systematic way to do so either. There's no way to choose such extensions.
@@Mutual_Information "no systematic way" that's what beavers are about if I understand correctly.
"there is a point where it can't prove" - I agree. But better axiomatic systems should be possible nevertheless.
I'm not mathematican, so I can't even guess how such systems may look like. But it is enough for me to know that there are no hard limits preventing people from upgrading their tools.
Given such an axiomatic system, turing machines can be constructed that would run that proof and then output slightly bigger numbers - you can force those machines to use more states to push up the point at which your system is forced to fail, but they can always be constructed in a finite number of states.
What! Why is Collatz Conjecture here? What has that got to do with Busy Beaver!
lol I know right!?
Do the conjectures plz
The fact that the human brain can comprehend these bizarre things proves that computers are nowhere close to humans, even if what is known as AGI exists, since they are also equivalent to some Turing machines.
What are those machines doing? I met some of them machines and they are mostly recommending ads to show to people ;). Some also manage the shopping cart and stuff.
8:05 Kermit?!
Wait, *is* our mathematics computable? I think we use non-finite reasoning all the time. Actually wasn't that the constructivists issue with modern set theory, that it is NOT computable? Maybe I have only a partial understanding here... but I don't feel like its possible to "enumerate all proofs" which are possible in our axiomatic system. That's my intuition but I'd have to ask an expert
If the definition of computation has a finite sequence of steps, and that is part of the definition for a Turing machine, why does a Turing machine need an infinite tape? I've always known that to be part of the description of a Turing machine, but it doesn't seem necessary and might even be inappropriate. Shouldn't it just be a machine with sufficient but finite storage rather than infinite?
How do you figure out how much is sufficient? As far as I know that's equivalent to the halting problem.
@@duncathan_salt the halting problem is whether or not there is a loop. It is a finite number of instructions which will not finish executing. If the premiss is that the tape is effectively the input, self modifying, and also the output, then perhaps you are right. I always saw the tape as being the instructions which defined the program. Therefore it seemed like a contradiction that the definition of the Turing machine has a finite sequence of steps but an infinite tape. `a: append 1 to the tape; goto a;` would satisfy finite steps but require infinite tape. Okay, I'm satisfied that there isn't a contradiction.
@@R.B. ah, yes, I believe you've identified your misconception! the tape is indeed just the I/O. the "program" is the machine's state table, which is indeed strictly finite
S(S(27)) > S(28)?
Yes certainly because S(27) > 28
@@Mutual_Information in hindsight, that was a stupid question... is it proven whether S(n) is always greater than S(n-1)?
It took me a second too, but the intuition I think you’re going for is right. The related conjecture is that for any computable function f, f(S(n)) < S(n+1) for n beyond a point.
And we haven’t proved it. We have some very weak bounds. We know S(n+1) > S(n) + 3, which at least shows it’s always increasing.
@@Mutual_Information Cool, thank you!
sounds like something a quantum algorithm might be able to handle but I'm not the one to wrap my head around it...
Busy beaver. Lol
This video sounds like it answers questions i had from the last video, so i like it, but i don't get it