Paper from Vielhaber et al. on arxiv

[Pascal Michel]

I have found today the following paper on arxiv:

https://arxiv.org/pdf/2303.02855.pdf

I have not read it yet, but it seams interesting.

Pascal

[Shawn Ligocki]

Thanks for sharing, Pascal. For what it's worth, some of the bounds listed in this paper are quite soft. For example they list BB(1840, 2) > n(3) > A(7198, 158386). But in fact, it is known that BB(16, 2) > Graham's number > A^64(4) >> A(7198,158386). I wrote a blog post last July about the machine (found by Daniel Nagaj) which demonstrates this bound. I'm not very familiar with Friedman's "n()" function, but it does sound like n(4) >> Graham.

--
You received this message because you are subscribed to the Google Groups "Busy Beaver Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to busy-beaver-dis...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/1b505559-e7dc-415f-986d-b03688cb8158n%40googlegroups.com.

[Justin Kee]

All, 

So I have a question that I would like to present to the group. My question may be a bit off-putting or display my non-understanding of Turing machines, but I hope you will forgive my reasoning as uninformed.

It goes something like this: simple Turing machines, as I understand them, such as TM (4,2) can exhibit Collatz like behavior, e.g. they can iterate up to a mod form in the base case and terminate their computations upon reaching a finite output based on x mod y, for some y. So BB (4,2) can iterate a certain number of steps but stops once it reaches x steps. 

My question is this: at what level of complexity do Turing machines exhibit behavior that is more complex than simple Collatz like behaviors and start computing more complex functions, such as matrix algebras, increasing the level of complexity by orders of magnitude? E.g. does a Turing machine of say (6,6) exhibit the ability to perform more complex mathematics, and by doing so complete their operations via more advanced mathematics, and as a result grow in complexity faster?

I suppose what I am asking is do Turing machines grow in their ability to compute more advanced calculations and as a result require more time and space complexity to either halt or not? Does this question even make sense?

Thanks in advance for your thoughts.

Best,

Justin Kee

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/CADhnJ7CcdEf5oKuLOwwxPtu-kq-prNeq078Hc-iRpAAL2WDevA%40mail.gmail.com.

[Terry Ligocki]

Also, we may only be finding Collatz-like behavior in the BB candidates because it is one of the more powerful computations that we know how to find! Even for the current size TMs, there could be surprises and new territory to explore. One group is actively trying to close out the (5,2) case, https://bbchallenge.org/, and for (6,2) TMs there has been recent progress that has found BB candidates where the number of steps can only (currently) be bounded by incredibly large numbers, https://www.sligocki.com/2022/06/21/bb-6-2-t15.html.

Since TMs are "Turing equivalent" (of course, :-), any computation can be done with a large enough TM. So, one question is where do transitions to more complicated computations/behaviors occur (as you were asking). When is a TM large enough to include the halting problem - at that point, the Busy Beaver result can't be proven.

In addition, there are questions about TM with more than two symbols as they can leverage different techniques to compute. For example, the BB(2,n) seems to grow considerably faster than BB(n,2)...

Terry J. (Ligocki, tjli...@gmail.com)

On Wed, Apr 12, 2023 at 12:19 AM Pascal Michel <pascalm...@gmail.com> wrote:

This question makes sense.

Certainly, the computational power of Turing machines grows when they get more states and symbols.

How exactly? That's the big question.

It happens that the busy beaver candidates that we know often have a Collatz-like behavior.

Will they get a more complex behavior? We simply don't know.

Pascal

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/dfaebadc-ecdf-497c-ab7f-14ba4c53fc0en%40googlegroups.com.