[HN Gopher] Striking new Beeping Busy Beaver champion
___________________________________________________________________
Striking new Beeping Busy Beaver champion
Author : bdr
Score : 83 points
Date : 2021-07-28 01:36 UTC (17 hours ago)
(HTM) web link (www.scottaaronson.com)
(TXT) w3m dump (www.scottaaronson.com)
| suyjuris wrote:
| Busy Beaver-type functions (counting how long a program runs,
| provided that it terminates) might look like a mere curiosity,
| but they make interesting statements about the power of different
| systems of computation. For Turing machines it grows quicker than
| any computable function - and Turing machines are quite powerful!
|
| If you consider a finite-state automaton, you might define a
| similar problem: What is the longest word that automaton accepts,
| provided that it accepts only finitely many words? This you can
| answer directly: it is n-1, where n is the number of states. And
| finite-state automata are not very powerful.
|
| Here is another system: I give you a list of transactions, where
| each transaction consists of multiple instructions of the form
| "add/remove x units from account y". You may only execute a
| transaction if no account goes negative. Here, a Busy Beaver-type
| question would be "What is the longest sequence of transactions
| that move one unit from the first account to the second, where
| all the others must start and end empty?" This is actually a
| somewhat powerful system, and here the answer grows at the rate
| of the Ackermann function - extremely fast (and, if you have
| never heard of it, probably faster than any computable function
| you can think of), but still computable. [1]
|
| Recently we have shown a Busy Beaver-type result for a certain
| distributed computation model, where many (very limited)
| participants interact to compute things as a group. There the
| question was about counting how large the group is, but each
| participant can only count to n. So given a protocol that
| reliably recognises certain group sizes, what is the largest size
| it accepts? (Again, provided that it accepts only finitely many.)
| We proved that it is at most 2^(2^(2^n)) - so in some sense that
| model is very weak, but nevertheless much more powerful that
| finite state automata.
|
| [1] I did not think to carefully about this, some details might
| be wrong.
| 6nf wrote:
| A0 -> 1RB A1 -> 1LC B0 -> 1RD B1 -> 1RB
| C0 -> 0RD C1 -> 0RC D0 -> 1LD D1 -> 1LA
|
| I'm guessing A0 -> 1RB means 'If the state is A and the symbol
| read from tape is 0 then change the tape symbol to 1, move right,
| and change the state to B'
| actually_a_dog wrote:
| This should help:
| https://nickdrozd.github.io/2020/10/04/turing-machine-notati...
| fjfaase wrote:
| There is also a Busy Beaver like problem with respect to (a
| modified version of) Brainfuck:
| https://www.iwriteiam.nl/Ha_bf_numb.html
| fjfaase wrote:
| For Brainfuck one could also define a Busy Beaver problem like
| the maximum number of steps before a given Brainfuck program
| stops. But you need to define what counts as a step. I would
| say that executing a command from the program counts as one
| step, meaning that the interpretation of '[' does not count all
| the commands that are skipped when the current memory cell is
| 0.
| alanbernstein wrote:
| I wasn't aware of the "Collatz-like iterative process" for BB
| lower bounds.
|
| That seems to suggest that the collatz conjecture sits somewhere
| close to the "edge of computability", which really fits well with
| Erdos' quote "Mathematics may not be ready for such problems."
| prezjordan wrote:
| The "generalized collatz conjecture" (rather than 3n+1 and n/2
| we use some a*n+k) was proven by the wonderful John Conway to
| be undecidable [0] by inventing a toy language called FRACTRAN
| [1] and showing that it was turing complete.
|
| It would be so wonderful to show that 3n+1 and n/2 are enough
| to compute anything - writing "programs" this way would be fun
| to look at.
|
| [0]:
| https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable...
|
| [1]: https://en.wikipedia.org/wiki/FRACTRAN
| nneonneo wrote:
| There's another possible explanation: Collatz-type recurrences
| are the most complex behaviors that can be encoded using a tiny
| number of Turing machine states, due to the way TMs access
| memory. From another comment, it turns out you can apply
| similar busy-beaver definitions to the lambda calculus, but you
| get very different results for small structures due to the
| innate recursive structure of the lambda calculus.
|
| Of course, if you have enough states in your Turing machine, or
| enough terms in your lambda expression, you can express any
| computation. The interesting thing is what happens when you
| look at small instances of each.
| galaxyLogic wrote:
| Looks like great fun with very big numbers.
|
| I wonder can something similar be defined in terms of Lambda
| Calculus?
| fjfaase wrote:
| When I was working on a similar problem with respect to
| calculating numbers with a version of Brainfuck where each cell
| can contain any natural number, I remember feeling some kind of
| mental nausea about how big numbers can get.
| tromp wrote:
| Indeed it can:
|
| https://mathoverflow.net/questions/353514/whats-the-smallest...
|
| https://oeis.org/A333479
| loldk wrote:
| I like the contrast on this site.
| isoprophlex wrote:
| > The first three of these, I managed to get on my own, with the
| help of a QBasic program I wrote.
|
| Amazing :)
| linspace wrote:
| Yes, I loved it. Anyway uncomputable functions find all
| languages weak.
___________________________________________________________________
(page generated 2021-07-28 19:02 UTC)