TMBR: October 2025: Difference between revisions
Jump to navigation
Jump to search
→Theory: Update PAF/LIATA section |
RobinCodes (talk | contribs) Corrected 2x5 holdout count from 67 to 64 machines. Used appropriate source formatting in "Theory" section (for consistency and structure) |
||
| (4 intermediate revisions by one other user not shown) | |||
| Line 17: | Line 17: | ||
* [[BB(4,3)|BB(4,3):]] | * [[BB(4,3)|BB(4,3):]] | ||
**Polygon analysed the remaining | **Polygon analysed the remaining [[BB(4,3)#Potential Champions|potential champions]] discovered by Pavel Kropitz in May 2024, discovering that {{TM|1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_0RB2RA2RD|halt}} is the new BB(4,3) champion with a score of over <math>10 \uparrow^{4} 4</math>. | ||
== Holdouts == | == Holdouts == | ||
[[File:BB(6) holdouts decrease over time.png|alt=BB(6) Holdouts count decrease overtime.|thumb|BB(6) Holdouts count decrease overtime.]] | [[File:BB(6) holdouts decrease over time.png|alt=BB(6) Holdouts count decrease overtime.|thumb|BB(6) Holdouts count decrease overtime.]] | ||
{| class="wikitable" | |||
|+BB Holdout Reduction by Domain | |||
!Domain | |||
!New Holdout Count | |||
!Previous Holdout Count | |||
!Holdout Reduction | |||
!% Reduction | |||
|- | |||
|[[BB(6)]] | |||
|1618 | |||
|1691 | |||
|73 | |||
|4.3% | |||
|- | |||
|[[BB(7)]] | |||
|20,405,295 | |||
|22,801,601 | |||
|2,396,306 | |||
|10.5% | |||
|- | |||
|[[BB(4,3)]] | |||
|9,401,447 | |||
|460,916,384 | |||
|451,514,937 | |||
|98.0% | |||
|- | |||
|[[BB(3,4)]] | |||
|15,136,283 | |||
|434,787,751 | |||
|419,651,468 | |||
|96.6% | |||
|- | |||
|[[BB(2,6)]] | |||
|870,085 | |||
|873,469 | |||
|3384 | |||
|0.4% | |||
|} | |||
* [[BB(6)|BB(6):]] | * [[BB(6)|BB(6):]] | ||
** @mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1429892916763033601 shared a new holdouts list on October 20th,] consisting of 1618 machines up to equivalence, or 3067 individual machines. This means 73 newly solved machines, a 4% reduction. | ** @mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1429892916763033601 shared a new holdouts list on October 20th,] consisting of 1618 machines up to equivalence, or 3067 individual machines. This means 73 newly solved machines, a 4% reduction. | ||
| Line 32: | Line 70: | ||
**[[User:XnoobSpeakable|XnoobSpeakable]] and [[User:WarpedWartWars|Lúkos]] are running filters in the domain under [[BB(3,4)#Phase 2|Phase 2]], reducing the holdout count from 434,787,751 to 15,136,283. (96.6% reduction) | **[[User:XnoobSpeakable|XnoobSpeakable]] and [[User:WarpedWartWars|Lúkos]] are running filters in the domain under [[BB(3,4)#Phase 2|Phase 2]], reducing the holdout count from 434,787,751 to 15,136,283. (96.6% reduction) | ||
*[[BB(2,5)|BB(2,5):]] | *[[BB(2,5)|BB(2,5):]] | ||
**[https://discord.com/channels/960643023006490684/1259770421046411285/1428501877947109437 Peacemaker II gave an informal proof of a machine never halting], making the informal holdout count | **[https://discord.com/channels/960643023006490684/1259770421046411285/1428501877947109437 Peacemaker II gave an informal proof of a machine never halting], making the informal holdout count 64. | ||
*[[BB(2,6)|BB(2,6):]] | *[[BB(2,6)|BB(2,6):]] | ||
**Andrew Ducharme has completed [[BB(2,6)#Stage 3|Stage 3 of Phase 2]], reducing the number of holdouts from 873,469 to 870,085. (0.39% reduction) | **Andrew Ducharme has completed [[BB(2,6)#Stage 3|Stage 3 of Phase 2]], reducing the number of holdouts from 873,469 to 870,085. (0.39% reduction) | ||
| Line 41: | Line 79: | ||
* @Bard proved that 3 dimension PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1420457986564030641] | * @Bard proved that 3 dimension PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1420457986564030641] | ||
* @star proved that 2 dimension PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1421271424588451915] | * @star proved that 2 dimension PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1421271424588451915] | ||
* Shawn Ligocki wrote up a proof sketch that 2-region PAF are Turing complete: https://discord.com/channels/960643023006490684/1239205785913790465/1422772752980639866 | * Shawn Ligocki wrote up a proof sketch that 2-region PAF are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1422772752980639866 <nowiki>[3]</nowiki>] | ||
* It was discovered that Amir Ben-Amram had already proven that 2-dim and 2-region PAF were Turing complete in 2015. | * It was discovered that Amir Ben-Amram had already proven that 2-dim and 2-region PAF were Turing complete in 2015. | ||
* BMO1 is a 2-dim, 2-region PAF so this provides some sense for the difficulty of the problem. | * BMO1 is a 2-dim, 2-region PAF so this provides some sense for the difficulty of the problem. | ||
Latest revision as of 20:58, 28 October 2025
| Prev: September 2025 | This Month in Beaver Research | Next: November 2025 |
This edition of TMBR is in progress and has not yet been released. Please add any notes you think may be relevant (including in the form a of a TODO with a link to any relevant Discord discussion).
TODO: BB(3x3) month
Misc
TODO: Add the mechanical Turing Machine. discord source: https://discord.com/channels/960643023006490684/1362008236118511758/1425889021653160026 and onwards
TODO: Add the method used by @Bricks to measure susceptibility to block-analysis. discord source: https://discord.com/channels/960643023006490684/1239205785913790465/1430227817957953638 also results: https://docs.google.com/spreadsheets/d/1j00LBxxp9W7uz1wZdMIvDCZ56eReuH0IGO9Z8-yybcQ/edit?usp=sharing
Blog Posts
- 22 Oct 2025. Ben Brubaker. Why Busy Beaver Hunters Fear the Antihydra.
- ? Oct 2025. Katelyn Doucette. Building the Busy Beaver Ladder.
Champions
- BB(4,3):
- Polygon analysed the remaining potential champions discovered by Pavel Kropitz in May 2024, discovering that
1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_0RB2RA2RD(bbch) is the new BB(4,3) champion with a score of over .
- Polygon analysed the remaining potential champions discovered by Pavel Kropitz in May 2024, discovering that
Holdouts
_holdouts_decrease_over_time.png)
| Domain | New Holdout Count | Previous Holdout Count | Holdout Reduction | % Reduction |
|---|---|---|---|---|
| BB(6) | 1618 | 1691 | 73 | 4.3% |
| BB(7) | 20,405,295 | 22,801,601 | 2,396,306 | 10.5% |
| BB(4,3) | 9,401,447 | 460,916,384 | 451,514,937 | 98.0% |
| BB(3,4) | 15,136,283 | 434,787,751 | 419,651,468 | 96.6% |
| BB(2,6) | 870,085 | 873,469 | 3384 | 0.4% |
- BB(6):
- @mxdys shared a new holdouts list on October 20th, consisting of 1618 machines up to equivalence, or 3067 individual machines. This means 73 newly solved machines, a 4% reduction.
- @Bricks shared a machine which they thought could be susceptible to block-analysis based on a method they call Subtape Saturation Heuristic. Shawn Ligocki's analysis, simulated by @Bricks showed the machine to halt with a sigma score of 4,419,340,317.
- Analysis by Racheline showed a machine to be non-halting.
- BB(7):
- Andrew Ducharme has continued reducing the number of holdouts with Stage 4 of Phase 2. Afterwards, Terry Ligocki ran Stage 5 of Phase 2. Initially, in the beginning of the month there were 22,801,601 holdouts, and 20,405,295 holdouts remain. (10.51% reduction)
- BB(4,3):
- Terry Ligocki has begun Phase 2 of holdout reduction, reducing the number of holdouts from 460,916,384 to 9,401,447. (97.96% reduction)
- BB(3,4):
- XnoobSpeakable and Lúkos are running filters in the domain under Phase 2, reducing the holdout count from 434,787,751 to 15,136,283. (96.6% reduction)
- BB(2,5):
- Peacemaker II gave an informal proof of a machine never halting, making the informal holdout count 64.
- BB(2,6):
- Andrew Ducharme has completed Stage 3 of Phase 2, reducing the number of holdouts from 873,469 to 870,085. (0.39% reduction)
Theory
Piecewise Affine Functions (PAF) were explored as a generalization of the BMO1 rules:
- @Bard proved that 3 dimension PAF are Turing complete: [1]
- @star proved that 2 dimension PAF are Turing complete: [2]
- Shawn Ligocki wrote up a proof sketch that 2-region PAF are Turing complete: [3]
- It was discovered that Amir Ben-Amram had already proven that 2-dim and 2-region PAF were Turing complete in 2015.
- BMO1 is a 2-dim, 2-region PAF so this provides some sense for the difficulty of the problem.
Deciders
TODO: Add -d's cpp quick_sim project. Discord source: https://discord.com/channels/960643023006490684/1226543091264126976/1426265937455222794
TODO: Add Katelyn's inductive project. Discord source:https://discord.com/channels/960643023006490684/1369339127652159509/1419016459560161280 https://discord.com/channels/960643023006490684/1095740122139480195/1427714010697961534