[HN Gopher] BB(3, 4) > Ack(14)
___________________________________________________________________
BB(3, 4) > Ack(14)
Author : LegionMammal978
Score : 200 points
Date : 2024-05-23 11:13 UTC (11 hours ago)
(HTM) web link (www.sligocki.com)
(TXT) w3m dump (www.sligocki.com)
| computerphage wrote:
| And you thought _your_ for-loops were too deeply nested!
| supriyo-biswas wrote:
| Can someone point me to some resources as to how to interpret the
| table, which I assume is some sort of description for a Turing
| machine?
| frutiger wrote:
| Each row is a state and each column is the symbol that was just
| read off the tape. So the first row & first column mean "I have
| just read symbol 0 and am currently in state A".
|
| The cell in the table describes which actions to perform. The
| first row & first column has "1RB" which means: "replace the
| symbol on the tape with '1', shift 1 symbol to the right on the
| tape and switch to state 'B'".
|
| The state 'Z' corresponds to the halting state.
| treyd wrote:
| Each triplet seems to be the symbol to write, and direction to
| move in, and the next state. You can think of the behavior of a
| turing machine as a function of the current state and the
| symbol read that's repeated iteratively.
| LegionMammal978 wrote:
| There's a brief explanation at [0]. (Note that "1RZ" is
| understood to be a halting transition, since state "Z" has no
| rules.) Wikipedia also has a more elaborated example of a TM
| state table [1]. You can see the trace of this particular TM at
| [2].
|
| [0] https://bbchallenge.org/story#turing-machines
|
| [1]
| https://en.wikipedia.org/wiki/Turing_machine#Formal_definiti...
|
| [2]
| https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2...
| nickdrozd wrote:
| The "states" (A, B, C) correspond to goto targets. The "colors"
| (0, 1, 2, 3) are runtime data. At each state, the current color
| is read, and an instruction is executed (print some color, move
| left or right, goto some state) based on which color is there.
| Transliterated into C it looks like this:
| #include "machine.h" int main(void) {
| A: switch (SCAN) { case 0:
| WRITE(1); RIGHT; goto B; case 1:
| WRITE(3); LEFT; goto B; case 2:
| WRITE(1); RIGHT; goto H; case 3:
| WRITE(2); RIGHT; goto A; } B:
| switch (SCAN) { case 0: WRITE(2); LEFT;
| goto C; case 1: WRITE(3); RIGHT;
| goto B; case 2: WRITE(1); LEFT;
| goto C; case 3: WRITE(2); RIGHT;
| goto A; } C: switch (SCAN) {
| case 0: WRITE(3); RIGHT; goto B;
| case 1: WRITE(1); LEFT; goto B;
| case 2: WRITE(3); LEFT; goto C;
| case 3: WRITE(2); RIGHT; goto C; }
| H: HALT; }
|
| Question: are there any opportunities to rewrite this logic in
| a more "structured" style, or to make any other optimizations?
| sans-seraph wrote:
| > Question: are there any opportunities to rewrite this logic
| in a more "structured" style, or to make any other
| optimizations?
|
| Because A and C only jump to B it is possible to structure
| this using only loops and one boolean. Let us use Rust to
| demonstrate as it lacks GOTO: let mut a =
| true; loop { loop { if a
| { // state A match scan() {
| 0 => { write(1); right(); break } 1
| => { write(3); left(); break } 2 => {
| write(1); right(); return } 3 => {
| write(2); right() } } }
| else { // state C match scan() {
| 0 => { write(3); right(); break } 1
| => { write(1); left(); break } 2 => {
| write(3); left() } 3 => { write(2);
| right() } } }
| } a = loop { // state B
| match scan() { 0 => { write(2); left();
| break false } 1 => { write(3); right() }
| 2 => { write(1); left(); break false } 3
| => { write(2); right(); break true } }
| } }
|
| Of course it is possible to rewrite this as a single loop if
| you are willing to accept two bits of extra state rather than
| one.
| nickdrozd wrote:
| Wow! I don't know if I would call that "structured", but
| it's pretty clever. And horrifying. Well-done!
| jamesaross wrote:
| I love these puzzles. GNU C supports a label as value for
| computed goto. This is useful for direct threaded dispatch.
| You trade off a branch instruction for an address lookup, but
| it makes the code more structured. int
| main(void) { void* A[] = {&&A0, &&A1, &&A2, &&A3};
| void* B[] = {&&B0, &&B1, &&B2, &&B3}; void* C[] =
| {&&C0, &&C1, &&C2, &&C3}; goto *A[SCAN]; A0:
| WRITE(1); RIGHT; goto *B[SCAN]; A1: WRITE(3); LEFT ;
| goto *B[SCAN]; A2: WRITE(1); RIGHT; HALT; return 0;
| A3: WRITE(2); RIGHT; goto *A[SCAN]; B0: WRITE(2);
| LEFT ; goto *C[SCAN]; B1: WRITE(3); RIGHT; goto
| *B[SCAN]; B2: WRITE(1); LEFT ; goto *C[SCAN];
| B3: WRITE(2); RIGHT; goto *A[SCAN]; C0: WRITE(3);
| RIGHT; goto *B[SCAN]; C1: WRITE(1); LEFT ; goto
| *B[SCAN]; C2: WRITE(3); LEFT ; goto *C[SCAN];
| C3: WRITE(2); RIGHT; goto *C[SCAN]; }
| sw1sh wrote:
| I've made a small repository with current record holders that
| also shows examples of running these machines with Wolfram
| Language:
| https://datarepository.wolframcloud.com/resources/The-
| Busy-B.... I guess I also need to update it now.
| immibis wrote:
| Discord links! As citations for major results in foundational
| computer science!
| Analemma_ wrote:
| I understand the complaint here, but a lot of recent impressive
| progress in mathematics has been by rapid collaboration +
| iteration (e.g. the project to improve Zhang's prime gap
| bound), and it may be the case that different communication
| tools are not easily fungible with Discord in this regard. You
| have to go where the people actually are.
| wizzwizz4 wrote:
| But Discord _isn 't citable_. Somebody needs to archive the
| Discord and make that available through the proper channels
| (e.g. a website, a book, the Internet Archive).
| univerz wrote:
| that post was just an (work in progress) update. Shawn's
| blog post is a proper announcement - much better than i
| would have written :)
| lambdaxyzw wrote:
| Well it was cited so by definition it's citable.
|
| I don't like discord but... The people doing research have
| chosen this method of collaboration. I like their research.
| Let's not be choosing beggars and tell them how to conduct
| their research.
| Almondsetat wrote:
| But papers aren't citable. Somebody needs to archive the
| paper and make it available through the proper channels
| (e.g. a website, library, journal, the Internet Archive).
| kryptiskt wrote:
| There are a ton of "personal communication" cites out there
| that are dead ends. The point of the cite isn't to provide
| a handy link, though it's nice if it is one, but to hand
| the credit where the credit is due.
| LegionMammal978 wrote:
| FWIW, it's a public Discord server, you can find the invite
| link at the top-right of https://bbchallenge.org.
|
| Also, I'd consider these more as attributions than citations.
| All the major arguments supporting the results have been
| replicated in the blog post (in a more rigorous form), so it
| can stand on its own: the Discord links just provide historical
| context for those interested.
| j2kun wrote:
| Finding bigger busy beaver numbers is not exactly foundational.
| More like recreational. If it were foundational it would be
| peer reviewed in a journal article, not posted on a blog.
| mcherm wrote:
| > If it were foundational it would be peer reviewed in a
| journal article, not posted on a blog.
|
| What I think you are doing here is to DEFINE "foundational
| work" as something that gets published in a journal.
|
| I don't mind if you use that definition, but if you do then
| the fact that all foundational work is published in journals
| is not insightful or informative, it is merely the
| definition.
|
| If, on the other hand, you intended for the statement to say
| something meaningful about how important scientific and
| mathematical work is communicated, then you need a different
| definition of "foundational". And you would have to look to
| that definition to decide whether this work was foundational,
| because if it was then it disproves your hypothesis: it would
| be a counter example that illustrates that some foundational
| work is shared in places other than journals.
| im3w1l wrote:
| To me, figuring out the halting behavior of small turing
| machines is similar in spirit going over all short logical
| propositions and trying to determine if they are true or
| not.
|
| Like it sounds like it could end up being useful somehow.
| lisper wrote:
| Why not? The idea that the only valid way to publish a
| scientific result is in a (so-called) peer-reviewed journal is
| a relic from 200 years ago when the scientific community was
| small enough to fit within the monkeysphere [1]. It is being
| clung to only because it is profitable for a small group of
| powerful academics and publishing houses, not because it has
| any actual merit in terms of the advancement of science. In
| fact, it's probably in no small measure responsible for
| contemporary replication crises. I'm as staunch an advocate of
| the scientific method as you will hope to find (I'm writing a
| book about it!) but IMHO traditional peer review is long past
| its sell-by date.
|
| [1] https://en.wikipedia.org/wiki/Dunbar%27s_number
| TeMPOraL wrote:
| Because Discord is a proprietary glorified IRC SaaS; its
| contents are, by nature, ephemeral and under control of the
| vendor. I'd expect such links to rot very quickly.
|
| Collaborating on Discord is fine. Important results,
| including citations backing them, should really be published
| or at least replicated in more durable medium that's less
| susceptible to link rot, and easier to archive. Today, that's
| PDFs in paper repositories, or even regular blog posts.
| pollyturples wrote:
| MySpace: 16 years (2003-2019) Friendster: 12 years
| (2002-2013) Google+: 8 years (2011-2019) Vine: 4 years
| (2013-2017) Orkut: 10 years (2004-2014) Path: 8 years
| (2010-2018) Yik Yak: 4 years (2013-2017) Meerkat: 2 years
| (2015-2017) Windows Live Messenger (MSN Messenger): 15
| years (1999-2014) AIM (AOL Instant Messenger): 20 years
| (1997-2017) ICQ: Ongoing (since 1996) but significantly
| declined after the early 2000s Yahoo Messenger: 20 years
| (1998-2018) Bebo: 14 years (2005-2019, relaunched in 2021)
| Google Wave: 2 years (2009-2011) Ping (Apple): 2 years
| (2010-2012) Discord: 8 years (2015-)
|
| so clearly discord is inherently different and here to stay
| forever! /s
|
| feels like time is a circle sometimes ha
| TeMPOraL wrote:
| Even with services that lived over a decade, it's not
| clear whether messages were accessible for all that time.
| E.g. Google Talk/Meet/Whatever seemingly lost all
| messages before ~2013. Links to Facebook posts tend to
| die quickly, as both users and Meta itself seem to
| constantly play with privacy features. Etc.
| tsterin wrote:
| I really like your point (I'm one of bbchallenge
| maintainers). I think that Discord is close to optimal
| for us in the short term, but bad for the reasons you and
| other have mentioned mid/long term.
| lisper wrote:
| I don't see any reason why the original publication venue
| has to end up being the canonical reference. That's not
| even true for traditional peer-reviewed papers. Have you
| ever seen an original physical copy of, say, Einstein's
| annus mirabilis papers? I haven't. I suspect that these are
| extremely rare and valuable collectors items and only
| trained archivists are even allowed to handle them.
|
| The right way to reference scientific publications is by
| URN [1], not URL. That makes the location irrelevant, as it
| should be.
|
| [1] https://en.wikipedia.org/wiki/Uniform_Resource_Name
| JadeNB wrote:
| > Have you ever seen an original physical copy of, say,
| Einstein's annus mirabilis papers? I haven't. I suspect
| that these are extremely rare and valuable collectors
| items and only trained archivists are even allowed to
| handle them.
|
| I'm not sure that they're collector's items, but they're
| probably not in that many university libraries. For
| example, the University of Michigan library has a
| physical copy in its special collection, but my
| university's considerably smaller library does not. But
| that's just because of age: this is a 119-year-old paper;
| were it a little younger, say, about 70 years, it would
| be in my university's holdings. I think that's a
| considerably different order of magnitude of its lifetime
| from a Discord link that I'd be absolutely astounded to
| see last a decade, and that in practice will probably
| last much less time than that.
| lisper wrote:
| What difference does it make if the original lasts a year
| or a century? The original is irrelevant except for
| historical purposes. What matters from a scientific point
| of view is that the results withstand scrutiny, and that
| they are reliably replicated and accessible.
| AlotOfReading wrote:
| We discover new approaches to replication all the time.
| Have you never come across foundational papers and
| arguments that everyone loved at the time, but made big
| methodological mistakes that led to the wrong conclusion?
| Or worse, found a source everyone references based on yet
| other secondary sources, only to look at the original
| context to discover that everyone's been misquoting it
| for decades? That happens _regularly_.
| lisper wrote:
| Sure, but I don't see what that has to do with the choice
| of publication venue. All of these things happen in
| traditional peer-review publications too.
| LegionMammal978 wrote:
| In this case, Ligocki's presentation of the proofs in the
| blog post is really _more_ rigorous than anything that
| went on in the Discord server. There 's not some golden
| Truth in there that's being imperfectly mediated; it's
| just about the attribution. You might have more of a
| point for results originating from programmatic searches,
| but that's why the programs are all published outside of
| Discord, so their output can be replicated.
| vlovich123 wrote:
| To be fair, the responsibility for the replication crises is
| much trickier. It's based on human motivations and poor
| science:
|
| 1. Outright fraud
|
| 2. Lack of independent verification of results before
| building up a body of work resulting in a bunch of garbage.
| Contributes to making #1 "easy".
|
| 3. Financial pressures to publish or perish contributing to 1
| & 2. If peer review didn't exist you'd still something
| similar about producing "recognized" results. This is also
| probably why we haven't done any major breakthroughs in
| particle physics which now has a much longer term thinking
| phase to come up with anything.
|
| The biggest problem with peer review is actually the
| establishment of an orthodoxy which discourages itself being
| upended by controlling the career success of anyone who dare
| challenge it - you have to support the orthodoxy to get
| career success and you fail to get recognition if your idea
| challenges the peer reviewers ideas and careers. That being
| said, such pressures existed before, but at least you could
| try to build your own following and it was competing
| orthodoxies instead of a single one winning out.
| lisper wrote:
| > Financial pressures to publish or perish
|
| But those only exist because of the current peer-review
| model. There is a huge non-linearity built in to the
| publication process that provides disproportionate rewards
| for conning a small number of people, fewer than half a
| dozen. That, combined with a presumption of
| trustworthiness, produces a perverse incentive for
| attempting such cons because they are very easy to pull
| off, much easier than actually doing good science.
| vlovich123 wrote:
| The rewards come from the grant model which I forgot to
| mention and also has similar problems to peer review. The
| stipulation to publish is a secondary effect. If peer
| review didn't exist there would still be pressure to show
| that you somehow convinced the leading experts in the
| field.
| lisper wrote:
| > there would still be pressure to show that you somehow
| convinced the leading experts in the field
|
| And how do you tell who are the leading experts in the
| field?
| vlovich123 wrote:
| It doesn't matter. There's plenty of ways. Tenure, those
| who get cited the most as contributing to other works,
| whoever manages to shmooze their way onto the grant
| review board, whoever has been doing "good" work in a
| space etc etc. If you think that peer review is the only
| way status is established, I'm afraid you're failing to
| grok how humans work - we're very status oriented and
| will come up with any mechanism to formalize and
| broadcast that status and academia and the scientific
| world is not immune from this.
| lisper wrote:
| > Tenure
|
| And how do you think that gets decided?
|
| > those who get cited the most
|
| And how do you get cited without first getting published
| in a peer-reviewed publication?
|
| > whoever manages to shmooze their way onto the grant
| review board
|
| Do you think it's possible to do that without a
| publication record?
|
| > whoever has been doing "good" work in a space
|
| As decided by whom?
|
| The point is that the current system is based on a small
| cadre of people assessing each other's work on the
| assumption that they are all competent and trustworthy.
| The bigger the community, the easier it becomes to game
| the system, and the bigger the incentives to do so, and
| so the less reliable traditional peer review becomes as a
| predictor of scientific quality. To say nothing of the
| sheer horrible inefficiency. It takes _months_ to do
| something that should take days. If anything was ever
| ripe for disruption, it 's peer review.
|
| BTW, here is an example of what happens when someone
| actually sets out to game the system and is fairly good
| at it:
|
| https://www.youtube.com/watch?v=ODgYbmmgOss
| vlovich123 wrote:
| > And how do you think that gets decided?
|
| Tenure precedes peer review afaik which I think pretty
| obviously negates this question - humans established
| tenure somehow so whatever that mechanism was. Peer
| review as a concept is quite old (17th century) and what
| these guys did on discord is peer review and
| collaboration. I'm assuming you're just using shorthand
| to refer to journal peer review which is the more recent
| phenomenon.
|
| > And how do you get cited without first getting
| published in a peer-reviewed publication?
|
| Citations exist independently of peer review. Not sure
| why you think you can't have one without the other.
| Journals are certainly not the only source cited. For
| example, math I believe doesn't even generally use
| journals and yet citations are going strong there.
|
| > Do you think it's possible to do that without a
| publication record?
|
| Possible? Of course. Pick 10 random bureaucrats and have
| them pick admissions at random. Good? Well, now you seem
| to be arguing the pro publication position as a way of
| coming up with a better review board. But anyway, yes
| obviously there are better ways of establishing a grant
| review board by trying to populate it with some amount of
| "freethinkers").
|
| Were agreed that the peer review system sucks for all
| sorts of reasons but we're now very far afield from what
| I was trying to correct which is that the replication
| crises has many origins and isn't just the fault of peer
| reviews. You'd have it even if journals and publish or
| perish weren't a thing.
| lisper wrote:
| > Tenure precedes peer review afaik
|
| Um, no. Tenure decisions turn largely on publication
| record, which turns on peer review.
|
| > Citations exist independently of peer review
|
| To cite something there has to be something to cite. It
| is of course possible to cite a non-peer-reviewed
| publication, but in academia this is heavily frowned
| upon. Non-peer-reviewed is generally considered
| synonymous with crackpottery.
|
| > Pick 10 random bureaucrats
|
| I meant do you think it's possible to "shmooze [your] way
| onto the grant review board" without a publication record
| in the real world, not some counterfactual world where
| you have stacked the deck.
|
| > the replication crises has many origins and isn't just
| the fault of peer reviews
|
| I didn't say it was _just_ the fault of peer review. What
| I said was that peer review was "probably in no small
| measure responsible for [the] replication crises", and I
| stand by that.
| JadeNB wrote:
| > > Tenure precedes peer review afaik
|
| > Um, no. Tenure decisions turn largely on publication
| record, which turns on peer review.
|
| I'm pretty sure your parent meant that the _concept_ of
| tenure precedes the _concept_ of peer review. However,
| this too seems to be false, according to the repository
| of truth, Wikipedia, which says that:
|
| > The first record of an editorial pre-publication peer-
| review is from 1665 by Henry Oldenburg, the founding
| editor of Philosophical Transactions of the Royal Society
| at the Royal Society of London.
|
| (https://en.wikipedia.org/wiki/Scholarly_peer_review)
| but:
|
| > Tenure was introduced into American universities in the
| early 1900s in part to prevent the arbitrary dismissal of
| faculty members who expressed unpopular views.
|
| (https://en.wikipedia.org/wiki/Academic_tenure).
| lisper wrote:
| > I'm pretty sure your parent meant that the concept of
| tenure precedes the concept of peer review.
|
| Even if that were true, what does the historical
| development of these institutions have to do with the
| claim that contemporary peer review is responsible for
| the contemporary replication crisis?
| vlovich123 wrote:
| Yeah I obviously am taking about the peer reviewed
| journal not peer review as a concept (which is how this
| discussion started). ~~But it does look like tenure is
| after journals not before.~~ Correction: peer review as
| we know of began in the mid 1970s, so tenure precedes the
| modern peer review system.
| vlovich123 wrote:
| Ok, so what you seem to have said in this thread is that
| the system today is a huge contributor to the replication
| crisis but any suggestion that things could be done
| differently is met with an endless barrage of questions
| and resistance that no, it had to be done this way. So
| your complaint is that there's a system at all instead of
| anarchy? Really not sure what point you're trying to
| make.
| lisper wrote:
| Maybe re-reading my original comment will help clarify:
| https://news.ycombinator.com/item?id=40456188
| vlovich123 wrote:
| Not really no. I suggested that you can decouple tenure
| (1900s) from modern peer review (1970s). Citations aren't
| an issue when publishing (you can publish anywhere) a
| result but are maybe more of an issue when you have a
| collaborative body of work (e.g. closer to open-source
| software development). But even still you can have
| citations (e.g. the citation using the Discord channel).
| For some reason you seemed to take the position that
| citations are inextractable from peer review. The grant
| mechanism is definitely a problem because of how it
| interacts with university funding, but the grant
| selection mechanism can evolve to be closer to how
| entrepreneurs work in the business market (which has its
| own pluses and minuses). What I suggested though is that
| even if you completely remove the modern peer review
| system, you'll still be left with the replication crises
| because. You've seem to have taken issue both with the
| suggestion that peer review is removable from academia
| and completely failed to engage with the issues that have
| nothing to do with peer review.
|
| 1. Issues around funding are a higher order problem with
| peer review only being a symptom at best (if at all). For
| example, Sabine talks about the issues and focuses on
| grants and spends 0 time on modern peer review.
|
| 2. Fraud didn't come into being because of peer review
| but grows with funding. The more funding the bigger the
| problem. Conversely the less funding the more likely
| proportionally the research is fraudulent or of poor
| quality because there's a smaller community checking the
| work. We know that the more funding we spend, the more
| research activity a field experiences. We don't have good
| ways to sift out fraud proactively - it takes
| disproportionately more work to root out fraud and bad
| science than it is to publish that & reap the rewards.
| This is true beyond academia - it's easier to spew BS
| than it is to explain the truth.
|
| 3. Not registering for null results has nothing to do
| with peer review. It's more just "hey I did this work and
| I'm not going to get rewarded so I'm not going to bother
| spending the work to publish the null result". That
| exists independent of the modern peer review system &
| even publish/perish is ancillary to this - a null result
| amounts to "failure" emotionally and that can be hard to
| deal with. That's why there's systems now to mandate pre-
| registration of the experiment - so that meta analysis
| can determine whether or not a result has actually been
| replicated enough to reduce the risk of p-hacking.
|
| 4. The replication crises for particle physics is a stark
| example how peer review is not really contributing as
| much. There's two schools of thought. The first is that
| we just follow the math and use data to refine which
| mathematical model to pick. The second is that we need to
| come up with better philosophical underpinnings for what
| the math is telling us. For now the first school is
| winning in terms of funding dollars (& results), but it's
| really hard to determine a priori which path is actually
| the one we should be following. Moreover, the orthodoxy
| exists independent of the peer review system (& even
| independent of grant proposals).
| UncombedCoconut wrote:
| As a member of these chats: it's often like hitting on an idea
| on a break-room blackboard and working it out, except the
| interaction can be cited. That's a positive change, _if_ we can
| follow through and add to the literature in due time. Here 's
| hoping.
| calfuris wrote:
| That's fine, but the citation shouldn't be in the form of a
| Discord link, or at least not exclusively in that form. Make
| a copy of the relevant messages, host them elsewhere, and
| include that copy in the citation. Discord has been pretty
| good so far but being a durable archive has never been their
| core selling point so I don't trust that to continue
| indefinitely.
| dailykoder wrote:
| Better than math proofs on 4chan[1], huh?
|
| [1]
| https://en.wikipedia.org/wiki/Superpermutation#Lower_bounds,...
| idlewords wrote:
| I thought that was great, too. They should also stream
| themselves solving this stuff on Twitch.
| tromp wrote:
| The new BB(3,4) record holder is 0 1 2
| 3 A 1RB 3LB 1RZ 2RA B 2LC 3RB 1LC 2RA
| C 3RB 1LB 3LC 2RC
|
| with the triple (t',d, s') in row s column t specifying the
| transition from state s with symbol t under the tape head. the
| machine overwrites symbol t with t', moves the tape Left/Right
| according to direction d, and changes state from s to s', halting
| if s'==Z.
|
| This is 3*4*log2(4*2*log2(4+1)) or about 64 bits of information.
| Meanwhile, in only 49 bits, BBl(49) far exceeds Graham's number
| [1].
|
| [1] https://oeis.org/A333479
| nilstycho wrote:
| Can you help me understand the log2(4+1) term?
|
| I calculate 3*4*log2(4*2*log2(4+1)) [?] 51.
|
| I (a layperson) would have thought the calculation would be
| 3*4*log2(4*2*4) = 60.
|
| Is it perhaps 3*4*log2(4*2*log2(3*3*4-1)) [?] 64?
| tromp wrote:
| I miscalculated. It should be 3*4*log2(4*2*(3+1))= 60 bits of
| information.
| im3w1l wrote:
| You also need to subtract some bits from symmetries right?
|
| Like you can mirror the tape. You can relabel states B and
| C. And you can relabel symbols 1, 2, 3. Though the analysis
| is complicated a little bit by the fact that some
| (combinations) of those operations may yield the exact same
| machine.
| nilstycho wrote:
| Also, is there any sense in restricting the universe of
| machines to those that include one and only one halting
| symbol? Machines with more or fewer than one halting
| symbol are possible, but they're less interesting, right?
| LegionMammal978 wrote:
| If you mean multiple halting _transitions_ , then it
| doesn't really help for BB purposes. If the machine
| _does_ halt, then only one of the halting transitions
| will ever be taken, and the others will be 'dead code'.
|
| If you mean multiple halting _states_ , then that is
| possible, and it can be used as a model of computation
| for, e.g., computable functions returning a single bit as
| output. But you still don't gain any additional running
| time before the machine halts.
|
| As for _no_ halting transitions, the problem is choosing
| what point to measure the tape at. One thing you can do
| is to put a mark on one of the transitions, then see
| whether the machine only runs that transition a finite
| number of times, or if it keeps running it forever. This
| yields the "Beeping Busy Beaver" numbers [0], which are
| uncomputable even if you have an oracle for the halting
| problem.
|
| [0] https://www.sligocki.com/2021/03/06/beeping-busy-
| beaver/
| nilstycho wrote:
| What I mean is that instead of measuring the bits of a
| particular program BB(n,k), we could instead define a
| function BBWOHT(n,k) ("Busy Beaver With One Halting
| Transition"), and measure the bits of a particular
| BBWOHT(n,k) program, which would be fewer bits than in
| the equivalent BB(n,k) program.
|
| Perhaps this is semantic games, but I'm trying to get at
| the idea that while there may be 60 bits of information
| in the BB(3,4) program, there are fewer in the
| BBWOHT(3,4) program, because we can prima facie exclude a
| bunch of "uninteresting" BB(n,k) programs from
| consideration if we restrict ourselves to BBWOHT(n,k), in
| the same way that we can exclude a bunch of
| "uninteresting" BB(n,k) programs from consideration if we
| restrict ourselves to BB(n,k) programs that aren't
| symmetries of other BB(n,k) programs.
| tromp wrote:
| There are many inefficiencies in Turing Machines which
| you could try to work around with increasingly
| complicated encodings. But that will never yield a
| provably optimal machine encoding such as you can obtain
| with BBl2 [1].
|
| [1] https://oeis.org/A361211
| tromp wrote:
| Only if you want to count the number of different
| possible TM behaviours. The official count of BB TMs as
| given in OEIS sequence A052200 ignores such symmetries.
|
| [1] https://oeis.org/A052200
| sligocki wrote:
| Counting the number of distinct TMs is not a simple task. The
| way you count it is the most broad (the count of all tables of
| values where each cell can have any (symbol, direction, state)
| combination). But this is a significant overcount of the bits
| needed to describe an arbitrary TM. for the BB(3, 4) case,
| there are only about 600B distinct TMs using the Tree Normal
| Form aka Brady's algorithm
| (https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html)
| which comes out to <40 bits.
| tromp wrote:
| Similarly, 2^n would be a huge overcount of the number of
| n-bit closed terms, which is given by OEIS sequence A114852
| [1]. There are 36140122614 ~ 2^35 closed terms of size 49
| bits (length of a straightforward self-delimiting encoding).
| So in that sense it's still a smaller lambda term computing
| an incomprehensibly larger output.
|
| [1] https://oeis.org/A114852
| PatronBernard wrote:
| Nice that the author provides some context...
| nickdrozd wrote:
| It is sometimes thought that extremely long-running Turing
| machine programs must be deeply complicated, or "spaghetti code".
| This new reigning champion program is a counterexample. All
| things considered, it is relatively simple.
|
| There are three states: A, B, C. (States are just like goto
| targets in C.) State B passes control to A and C, but states A
| and C don't "know about" each other; they only pass control back
| to B. This is a sort of modular construction, whereas in true
| spaghetti code each state would be able to pass to all the
| others.
|
| This program has some other interesting features. It never prints
| a blank (that is, whenever it scans a 0, it prints 1, 2, or 3).
| Additionally, every instruction changes either the state or the
| color -- there are no "lazy instructions" like B1 -> 1LB that
| just move position without changing anything else.
| LegionMammal978 wrote:
| There is some debate in the bbchallenge project regarding the
| current long-running champions: do their properties reflect
| those of the actual longest-running machine of that size, or
| are their properties just the easiest to automatically search
| for and prove things about, as a kind of streetlamp effect?
| There's no way to know, until the entire search space has been
| ruled out, either definitely or heuristically. (Every size past
| BB(5, 2) contains chaotic, pseudorandom machines that are
| expected to run forever, but can't be proven to do so without
| big advances in number theory.)
|
| Though I suspect that no long-running machine can be utterly
| chaotic, at least when you look at the patterns it produces on
| the tape. To run for a long time, a machine must simulate some
| sort of higher-level rule: if it were dumping symbols on the
| tape at random, then it would very soon reach a halting
| configuration, a cyclical configuration, or some other
| simplified pattern. Still, one can have long-running machines
| that do simulate something chaotic on a higher level, spending
| an inordinate amount of time between each high-level step until
| it halts.
| kevinventullo wrote:
| At a high level, wouldn't you expect Champions to be chaotic
| in the limit? As in, the halting problem tells us that any
| increasing sequence of Champions is _not_ computable.
| tromp wrote:
| Yes, for a busy beaver properly defined in information
| theoretic terms, like BBl2 [1], one can prove that its
| champions must be incompressible up to some constant.
| Mikhail Andreev's article "Busy Beavers and Kolmogorov
| complexity" [2] explores these connections.
|
| [1] https://oeis.org/A361211
|
| [2] https://arxiv.org/pdf/1703.05170
| nickdrozd wrote:
| > streetlamp effect
|
| I agree completely, all of these kinds of conjectures are
| shaped by what is detectable. If there are any "dark matter"
| programs out there, they by definition will be difficult to
| find. That said, I find it entirely plausible that the
| champions will win by exploiting complex and exotic
| mathematical facts, while the _implementations_ of the math
| do not themselves need to be complex or exotic at the code
| level.
|
| More rambling thoughts about this:
| https://nickdrozd.github.io/2021/09/25/spaghetti-code-
| conjec...
| LegionMammal978 wrote:
| Yeah, thankfully we're still in the range where halting
| machines are at least estimable in terms of inductive
| notations like the up-arrow. But as the machines gain more
| breathing room for working with variable-length data, we
| can start getting monsters like the TREE sequence.
| AlotOfReading wrote:
| Handwaving here, but I think longest running machines can't
| follow a specific structure in general.
|
| Rough sketch of an argument:
|
| Let's construct a number from all intermediate states of the
| machine concatenated. The number of digits of this number
| should correspond to the runtime (sketchy). We only care
| about the halting machines, so it's finite. We know that it
| must be unique because if a smaller machine computes the same
| number, we could get a bigger number by simply running the
| smaller program and doing other nonsense. That means the
| biggest programs are komolgorov optimal, and the numbers
| themselves should be k-trivial and thus _nearly_ but not
| quite computable. Since they 're not computable, the programs
| themselves can't follow a structure to generate them (since
| that would be computable in turn for larger values).
| mikewarot wrote:
| This all sounds like extreme Code Golf to me.
|
| Here's a tangent to explore:
|
| A BitGrid[1] (my personal hobby horse) only has 4 bits of state
| per cell, so a 4x4 grid of cells can't count more than 2^64, no
| matter what. Finding the highest it could count would be
| interesting. For small grids, the edge connections would dominate
| the outcome.
|
| [1] https://esolangs.org/wiki/Bitgrid
|
| [2] https://github.com/mikewarot/Bitgrid
| ziofill wrote:
| There are only so many Turing machines that we can possibly
| describe with a not too large amount of symbols such as
| 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC. The fact that some of
| these can make such a crazy large number of steps before halting
| to me is mind blowing.
| tromp wrote:
| There are 2^60 such 3 state 4 symbol Turing machines. A 49-bit
| lambda term whose output (normal form) exceeds Graham's Number
| should blow your mind even more.
| ziofill wrote:
| 2^60 is very little! Is it known what fraction of them has an
| insanely large run time?
| kingofthecob wrote:
| If you know, you know I guess. I certainly have no idea.
| casercaramel144 wrote:
| I was curious as to how it works, so I implemented here:
| turingmachine.io/?import-gist=c862f28918f3d889f964797694d28fcc
|
| If you run it for a bit you see what's going on, State B turns
| 0's into 2's and 1's into 1's transitioning to C and state C
| turns 3 -> 2's and transitions to A. So you just iteratively
| lengthen your run of 3's exponentially since it requires a full
| pass through all the 3's to fix a 2->1.
| tux3 wrote:
| It's fairly easy to make a turing machine that goes exponential
| and blows up forever.
|
| But the really tricky part to understand is why it eventually
| _stops_. After an unimaginably high number of steps.
| fsmv wrote:
| Is it not true that BB(5) > BB(3,4)? On the
| https://bbchallenge.org site it said they're trying to prove or
| disprove the conjecture that BB(5) is about 47 million but
| BB(3,4) is apparently much bigger than that.
___________________________________________________________________
(page generated 2024-05-23 23:00 UTC)