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.

@Mutual_Information

9 ай бұрын

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.

@joshuazelinsky5213

9 ай бұрын

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.

@Mutual_Information

8 ай бұрын

@@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?

@joshuazelinsky5213

8 ай бұрын

@@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.

@joshuazelinsky5213

8 ай бұрын

@@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

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)

@Mutual_Information

9 ай бұрын

Oh yea, 100%

@kindlin

8 ай бұрын

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.

@LostOter

8 ай бұрын

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

@kindlin

8 ай бұрын

@@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.

@thomazmartins8621

8 ай бұрын

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.

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

@asandax6

Ай бұрын

That's because maths like language is a tool for describing the universe and it's inner workings. This basically makes math a language

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

@Mutual_Information

8 ай бұрын

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

@Thats_A_Dummy_Name

8 ай бұрын

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

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

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!

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!

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.

@Mutual_Information

7 ай бұрын

appreciate that, means a lot.. and thank *you* for watching my stuff

9:00 we can assume that a beaver is lost

you are a G

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.

@Mutual_Information

9 ай бұрын

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

@nandanshettigar7261

8 ай бұрын

@@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 :)

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.

@Mutual_Information

8 ай бұрын

Yea! we feel the same

@piotr.ziolo.

7 ай бұрын

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.

@Mutual_Information

7 ай бұрын

@@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

Thank you for the effort to provide this insight. Mind-bending.

Phenomenal job with this and the previous video. First Busy Beaver videos on KZread in years that I think extend the understanding of laymen like me.

@Mutual_Information

7 ай бұрын

Thank you my dude

@joebloggs3551

7 ай бұрын

​​@@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 😝

@Mutual_Information

7 ай бұрын

@@joebloggs3551 You're too kind Joe - it's much appreciated! And I'd love to answer those questions, if only I knew them :)

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🤔

@Mutual_Information

9 ай бұрын

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).

Excellent video, an eye-opening “appetizer”. I know just enough about the subjects to recognize that I have so much more to learn.

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.

@Mutual_Information

9 ай бұрын

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.

Amazing, NO WORDS Just AMAZING :0

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.

Amazing video, a really good follow up. Subscribed

@Mutual_Information

8 ай бұрын

I'm honored, thank you!

Wow, I found it weird that the incompleteness theorems were somehow linked to the halting problem but this makes a lot of sense now

@dekippiesip

7 ай бұрын

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.

I like small channels like yours that do interesting videos

Commenting for the algorithm, another great video!

@Mutual_Information

9 ай бұрын

Awesome, thank you!

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.

Amazing video

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

@Mutual_Information

9 ай бұрын

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?

@mgostIH

9 ай бұрын

​@@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.

@Mutual_Information

8 ай бұрын

@@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..

@dekippiesip

7 ай бұрын

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?

@mgostIH

7 ай бұрын

@@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.

next up you will solve the P vs NP problem and the clay institute will give you a million dollars, correct?

@Mutual_Information

9 ай бұрын

Lol I think there's a wide gap between making a shiny KZread video and actually solving extremely hard problems, but I appreciate the vote of confidence!

@siddharthbisht1287

8 ай бұрын

@@Mutual_Information anytime sir, I am hopeful

Amazing explanation, you earned a sub.

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.

@Mutual_Information

6 ай бұрын

yea I bet that's true too

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.

@Mutual_Information

9 ай бұрын

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.

I really enjoy these videos as someone who likes math and googology (the study of large numbers) :)

you can analyse continouse version of SAT problem - it show what happens at boundary of computation really well...

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!

@Mutual_Information

8 ай бұрын

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)

@Daniel-Six

8 ай бұрын

@@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.

@Mutual_Information

8 ай бұрын

@@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?

@Daniel-Six

8 ай бұрын

@@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.

thanks! very intresting:)

So... when's the video on the Conjectures coming out? Because we NEED to hear you tell us more about this beauty!!

@Mutual_Information

8 ай бұрын

lol oh man.. my topic list never shrinks!

@lexinwonderland5741

8 ай бұрын

@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!

@Mutual_Information

8 ай бұрын

@@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 :)

@Mutual_Information

9 ай бұрын

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!

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!

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.

what software do you and 3blue1brown use to make the animations? btw do a video on shannon's law

@joseville

6 ай бұрын

3Blue1Brown uses Grant Sanderson's Manim

mind blowing

more please.

I'd raise the volume

@Julian-tf8nj

8 ай бұрын

Many KZread videos have this problem. On Firefox, I use the "SoundFixer" extension - VERY handy at times! 😁

This kind of nonsense is why I'm a computer scientist not a mathematician 😂😅

@Julian-tf8nj

8 ай бұрын

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.

@Imperial_Squid

8 ай бұрын

@@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

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.

i wonder if this is one of those problems a quantum computer could solve for determining if S(27) halts or continues forever

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)!

@user-oe5eg5qx4c

8 ай бұрын

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.

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

@kiffeeify

9 ай бұрын

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 ? ¯\_(ツ)_/¯

@AssemblyWizard

9 ай бұрын

This already exists, google "Fuzzy logic". Maybe also "Godel logic", or "Many valued logic" in general

@nonamehere9658

9 ай бұрын

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

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!

@Mutual_Information

8 ай бұрын

Indeed, multiple reasons why omniscient knowledge is forever out of reach

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.

@Mutual_Information

8 ай бұрын

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.

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?

@Mutual_Information

8 ай бұрын

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.

Mathematics at this level is so intimidating like wtf

Continue with busy beaver in your other videos. Examples, proofs as concretely as you can.

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.

"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.

@Mutual_Information

8 ай бұрын

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.

@Cowtymsmiesznego

Ай бұрын

@@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

If S(27) encodes Goldbach, and if Goldbach is true AND unprovable, would that suggest that n_T

@Mutual_Information

8 ай бұрын

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.

@Killua2001

8 ай бұрын

@@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?)

@Mutual_Information

8 ай бұрын

@@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.

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)?

@Mutual_Information

6 ай бұрын

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).

Can't you just reverse compute ergo backtrack the steps leading to Goldbach's conjecture or similar problems?

@Mutual_Information

7 ай бұрын

I'm not exactly sure what you're suggesting. What do you mean specifically?

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).

@Mutual_Information

9 ай бұрын

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

At the end- how can a turing machine enumerate all proofs in a system T? Surely there are infinite?

@Mutual_Information

8 ай бұрын

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)

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

@AssemblyWizard

9 ай бұрын

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.

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.

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.

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?

@Mutual_Information

8 ай бұрын

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.

Do the conjectures plz

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?

@Mutual_Information

6 ай бұрын

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.

@ahoj7720

4 ай бұрын

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.

@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.

@Achrononmaster

8 ай бұрын

I appreciate after 13 mins you sort of acknowledged this. Nice channel of content you have I must say.

You’re the math version of Jon Solo haha!

10:25 any **halting** 27-state machine

What about running busy beaver on quantum computer?

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.

@Mutual_Information

8 ай бұрын

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.

@sdjhgfkshfswdfhskljh3360

8 ай бұрын

​@@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.

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."

@Mutual_Information

3 ай бұрын

Because the statement is "BB(n) grows faster than any *computable* function". BB(n) itself isn't computable, so neither is n*BB(n).

@BrianHill

3 ай бұрын

@@Mutual_Information Oh! Thank you for straightening me out! Your presentation is extraordinarily good.

why can't they flip the Busy Beaver around so that it halts if a theory is true?

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.

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.

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.

psa: abstracting abstraction itself breaks the universe

@Mutual_Information

Ай бұрын

lol yes be careful out there

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

8 ай бұрын

How do you figure out how much is sufficient? As far as I know that's equivalent to the halting problem.

@R.B.

8 ай бұрын

@@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.

@duncathan_salt

8 ай бұрын

@@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

What! Why is Collatz Conjecture here? What has that got to do with Busy Beaver!

@Mutual_Information

9 ай бұрын

lol I know right!?

(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?

@Mutual_Information

3 ай бұрын

lol, a computer god would make more sense than a hairy meat sack organism

I would like to send you money directly, since it seems you like it (for some reasons unknownable). I do not want to feed Patreon parasite.

@Mutual_Information

8 ай бұрын

That's fair and good to know. I'll set something up for that

8:05 Kermit?!

13:54 Wait, but isn't that just circular reasoning ?

@Mutual_Information

5 ай бұрын

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.

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

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

Hehe. Tree(3)

S(S(27)) > S(28)?

@Mutual_Information

8 ай бұрын

Yes certainly because S(27) > 28

@incription

8 ай бұрын

@@Mutual_Information in hindsight, that was a stupid question... is it proven whether S(n) is always greater than S(n-1)?

@Mutual_Information

8 ай бұрын

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)) 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.

@incription

8 ай бұрын

@@Mutual_Information Cool, thank you!

This video sounds like it answers questions i had from the last video, so i like it, but i don't get it

3/3

13:05 This is only possible through the existence of God. Look into Christian philosophy and metaphysics (but not the heretics! Stick with scripture!) and a lot of these strange mathematical phenomena just seem to click into place. Like certain aspects of Gods creative authority that dictate certain axioms of reality and things like that. It's some very interesting stuff that shows how lots of seemingly different things are connect, like God is the hub to which all spokes are connected to!

If it can be mathematically proven that no line of reasoning can prove that a certain machine halts, then it doesn't, right? Because "run the machine a hundred googol times" is a way of mathematically proving that it halts, insofar as it does actually halt in that number of steps.

@Mutual_Information

Ай бұрын

You can't prove with it halts or not without running it. And running the machine isn't a proof either because it may just run forever and that whole time, you won't know whether it is about to halt or not.

This seems like a really well put together video - however, i do think it looks like you are copying the visual style and presentation that has made 3blue1brown famous - his style is good but as you know there is a fine line between inspiration and plagiarism and i think this tilts a bit too close to the latter.

@Daniel-Six

8 ай бұрын

I just asked him what visualization software he is using. I'm a career 3D animator and I do everything by hand, which would be almost impossible for the kind of stuff he does here. I suspect both he and 3B1B use similar/same software (maybe Mathematica), and that's why their videos look alike. It's not any kind of plagiarism, from an intellectual perspective at least.

@Mutual_Information

8 ай бұрын

I don't use what 3Blue1Brown uses, manim. I use something I built. I submitted this video to his SoMe3 competition - I don't think he'd find it encroaching.

w

Please, talk for hours. I'm listening.

Can you not show yourself? It is distracting