submitted by /u/mehelponow to r/SpaceXLounge [link] [comments] |

The classic **Busy Beaver** function is defined as the maximum number of steps that an N-state 2-color Turing machine program can run before halting when started on the blank tape. The function is **uncomputable**, and any sound proof system *S* can only prove values up to a certain point. That is, there is some number *Q* such that

*BB(Q) = K*,*S ⊬ BB(Q) = K*, and- for all
*P < Q*,*S ⊢ BB(P) = J*where*J = BB(P)*.

Call *Q _{S}* the

**Every theory has a cut-off.** There is *Q _{RA}* for Robinson arithmetic,

**What can be said about these cut-offs?** Certainly strengthening a system will not make it prove less, so when system *T* is more powerful than system *S*, we will have *Q _{S} ≤ Q_{T}*. Consequently,

Are these inequalities strict? It seems like they ought to be, and it would be convenient if they were. It could be that, say, *Q _{RA} = 8*,

But that’s all speculation. It could also be that the cut-offs are all the same: *Q _{RA} = Q_{PA} = Q_{ZF} = Q_{LC}*. According to this picture, the values of BB go provable, provable, provable, then BAM, unprovable.

**How could this be?** There are several possibilities.

First, the most straightforward way to establish that *S* cannot prove some value of *BB* is to devise a Turing machine program that enumerates theorems of *S* and halts if it finds a contradiction. This program will run forever if and only if *S* is consistent. But if *S* is consistent, then by the second incompleteness theorem it cannot prove its own consistency, and therefore cannot prove that the program will run forever. The program has *P* states, so *S* cannot prove the value of *BB(P)*.

Now, let *M _{PA}* be the shortest program that implements this behavior for Peano arithmetic and let

There is another possibility. It could be that there is some statement say of number theory that is **easy to state and difficult to prove**, so difficult in fact that it cannot be proved in any of RA, PA, ZF, etc. And if there is a short TM program that computes this statement (say by halting if the statement is false), then if *L* is that program’s length, none of these systems could prove *BB(L)*. As far as I know there is no reason to believe that this would be impossible.

**Okay, so what if all the cut-offs really are the same? What then?** One response is just to say that if the traditional Turing machine-based definition of Busy beaver is **too coarse-grained** to distinguish between these different proof systems, then that just shows that it’s a bad definition, and we would be better off using something like binary lambda calculus instead. But any such formalism could still just as easily be affected by short-but-difficult statements.

But if these systems are all equivalent by the lights of the ladder picture, this could be viewed as a sort of proof that **people have been looking at the wrong proof systems**. There is an idea, very widespread and very stupid, that humans are inherently able to **“intuit” the consistency of formal systems**, using the “mind’s eye” or maybe some kind of quantum mechanical magic. This is idea is clearly based on the presumed concistency of the usual formal systems PA, ZF, etc. But these systems are just a drop in the ocean of the full world of axiomatic systems. The systems that have been developed historically represent only a very small part of the solution space. Even if these systems are all on the same rung of the ladder, there are surely some systems that do exist on the higher rungs. **Well, what are those systems like?** That would be something to learn.

**Is any of this likely?** Well, it reasonable to expect that PA and ZF show up on different rungs, that *Q _{PA} < Q_{ZF}*. But the Busy Beaver function

I love Jupyter – it's how I learned to code back when I was working as a scientist. But I was always frustrated that there wasn't a simple and elegant app that I could use with my Mac. I made do by wrapping JupyterLab in a chrome app, and then more recently switching to VS Code to make use of Copilot. I've always craved a more focused and lighter-weight experience when working in a notebook. That's why I created Satyrn.

It starts up really fast (faster time-to-execution than VS Code or JupyterLab), you can launch notebooks right from the Finder, and the design is super minimalist. It's got an OpenAI integration (use your own API key) for multi-cell generation with your notebook as context (I'll add other LLMs soon). And many more useful features like a virtual environment management UI, Black code formatting, and easy image/table copy buttons.

Full disclosure: it's built with Electron. I originally wrote it in Swift but couldn't get the editor experience to where I wanted it. Now it supports autocomplete, multi-cursor editing, and moving the cursor between cells just like you'd expect from JupyterLab or VS Code.

Satyrn sits on top of the jupyter-server, so it works with all your existing python kernels, Jupyter configuration, and ipynb files. It only works with local files at the moment, but I'm planning to extend it to support remote servers as well.

I'm an indie developer, and I will try to monetize at some point, but it's free while in alpha. If you're interested, please try it out!

I'd love your feedback in the comments, or you can contact me at jack-at-satyrn-dot-app.

Comments URL: https://news.ycombinator.com/item?id=40899242

Points: 597

# Comments: 158

Next Page of Stories