New pages

Jump to navigation Jump to search
New pages
Hide registered users | Hide bots | Show redirects
  • 20:35, 19 August 2025 ‎Universal Turing Machine (hist | edit) ‎[1,684 bytes] ‎Sligocki (talk | contribs) (Created page with "A '''Universal Turing Machine''' (UTM) is a Turing Machine which can simulate any other TM (encoded onto input tape). The precise definition requires defining the encoding function to map simulated TMs and TM inputs into UTM initial tapes. Since a UTM can simulate any TM, the halting problem for any UTM is not computable. There is a common misconception that the Busy Beaver Functions will become uncomputable once we reach a domain with a UTM (since the general h...") Tag: Visual edit
  • 18:08, 8 August 2025 ‎1RB0RD 0LC1RA 0RA1LB 1RE1LB 1LF1LB ---1LE (hist | edit) ‎[1,345 bytes] ‎Sligocki (talk | contribs) (Created page with "{{machine|1RB0RD_0LC1RA_0RA1LB_1RE1LB_1LF1LB_---1LE}} {{TM|1RB0RD_0LC1RA_0RA1LB_1RE1LB_1LF1LB_---1LE}} is a non-halting BB(6) TM discovered by mxdys on 14 Sep 2024 ([https://discord.com/channels/960643023006490684/1239205785913790465/1284419946759323700 Discord]) and proven non-halting the next day ([https://discord.com/channels/960643023006490684/1239205785913790465/1284838151348551795 Discord]). It follows rules similar to {{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0...")
  • 18:43, 6 August 2025 ‎Tₘ function (hist | edit) ‎[984 bytes] ‎Qwerpiw (talk | contribs) (Created page with "Let M be a non-deterministic Turing machine which recognizes a language L, that is, for every input word u there is an accepting computation with input u if and only if u ∈ L. Let us assume that M terminates on every input. The simplest thing to assume is that if u ∈ L, the TM eventually gives "yes" and if u ∉ L, it gives "no". The smallest time (number of steps) of such a computation is denoted by T<sub>M</sub>(u) . For every n >= 1 we define T<sub>M</sub>(...") Tag: Visual edit: Switched originally created as "T M function"
  • 14:33, 5 August 2025 ‎1RB--- 0RC1RD 1LA0LA 1LE0RB 1LF1LE 1LC0LD (hist | edit) ‎[142 bytes] ‎N1vi (talk | contribs) (Created page with "{{machine|1RB---_0RC1RD_1LA0LA_1LE0RB_1LF1LE_1LC0LD}} 1D — CA, rule 30 or rule 110")
  • 14:06, 5 August 2025 ‎1RB1LE 1LC0RA 0RF0LD 1LE1LA 1RC0LB ---1RC (hist | edit) ‎[369 bytes] ‎N1vi (talk | contribs) (Created page with "thumb It is really interesting. I high likely doubt it halts, but it creates pseudo random spaces at the right. I ran it for ~860 million steps and the result is shown at the image. Though it might be a fractal.") Tag: Visual edit
  • 16:01, 2 August 2025 ‎TMBR: August 2025 (hist | edit) ‎[930 bytes] ‎Qwerpiw (talk | contribs) (Created page with "{{Stub}} this month in busy beaver for 2025 August") Tag: Visual edit
  • 21:43, 31 July 2025 ‎Doodle function (hist | edit) ‎[1,226 bytes] ‎Qwerpiw (talk | contribs) (Created page with "The '''doodle function''' is a function made by Lawrence Hollom. It is a two-argument function.<ref>https://web.archive.org/web/20230901195926/https://sites.google.com/a/hollom.com/extremely-big-numbers/home/doodle-function</ref> == Definition == The function revolves around a specific type of one-dimensional cellular automaton, in which state of a cell is determined by its own state and state of the cell to its right at previous generation (Hollom's original explanatio...") Tag: Visual edit: Switched
  • 15:59, 30 July 2025 ‎1RB0LD 1RC1RA 1LD0RB 1LE1LA 1RF0RC ---1RE (hist | edit) ‎[1,791 bytes] ‎Sligocki (talk | contribs) (Created page with "{{machine|1RB0LD_1RC1RA_1LD0RB_1LE1LA_1RF0RC_---1RE}} {{TM|1RB0LD_1RC1RA_1LD0RB_1LE1LA_1RF0RC_---1RE}} is a probviously halting BB(6) Cryptid analzyed by mxdys on 30 July 2025. == Analysis by mxdys == [https://discord.com/channels/960643023006490684/1239205785913790465/1400141896944320602] <pre> 1RB0LD_1RC1RA_1LD0RB_1LE1LA_1RF0RC_---1RE (a,b,c) := 0^inf 1^a 0 01^b 0 11^c+1 B> 0^inf (a,2+b,c) --> (a,b,3+c) (a+1,0,c) --> (a,c,2) (a+1,1,c) --> (a,c,6) (0,0,c...")
  • 03:17, 27 July 2025 ‎1RB1LA------ 1RC3LB1RB--- 2LA2LC---0LC (hist | edit) ‎[1,090 bytes] ‎Sligocki (talk | contribs) (Created page with "{{machine|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC}} {{TM|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC}} is the current BBi(8) champion. It runs for over <math>10^{1565}</math> steps and has a sigma score of exactly <math>\frac{3^{1642} - 11}{2}</math>. It was discovered by Nick Drozd on 26 July 2025 ([https://discord.com/channels/960643023006490684/1084047886494470185/1398753236835635252 Discord link]). == Analysis by Shawn Ligocki == <pre> A(a, b, c) = <A 2^a 0 3^b 1^...")
  • 18:34, 22 July 2025 ‎Meet-in-the-Middle Weighted Finite Automata Reduction (MITMWFAR) (hist | edit) ‎[389 bytes] ‎Sligocki (talk | contribs) (Created page with "'''Meet-in-the-Middle Weighted Finite Automata Reduction''' ('''MITMWFAR''') is a Turing machine decider. It is a variation of Finite Automata Reduction (FAR) based upon Weighted Finite Automata. This allows it to decide irregular TMs which cannot be decided by FAR or any other regular decider. See: https://github.com/Iijil1/MITMWFAR/tree/main Category:Deciders Category:Stub") Tag: Visual edit
  • 21:47, 16 July 2025 ‎Instruction-Limited Busy Beaver (hist | edit) ‎[17,284 bytes] ‎Sligocki (talk | contribs) (Created page with "An '''n-instruction Turing machine''' is a Turing machine with an arbitrary number of states and symbols, but limited to only ''n'' defined transitions/instructions in its transition table (all others are undefined). The '''Limited Instruction Busy Beaver''' (BBi(n)) problem is the Busy Beaver problem limited to n-instruction TMs. So BBi(n) is the longest runtime for all halting n-instruction TMs when started on a blank tape. A TM is considered to halt as soon as it...") originally created as "Limited Instruction Busy Beaver"
  • 21:00, 16 July 2025 ‎Terminating Turmite (hist | edit) ‎[987 bytes] ‎Sligocki (talk | contribs) (Created page with "A '''Terminating Turmite''' or '''Relative Movement Turing Machine''' is a Turing machine which uses relative directions instead of absolute ones. So instead of moving (L)eft or (R)ight, it (P)roceeds forward (for one step in the same direction as last move or (T)urns-around (move one direction in the opposite direction). TT(n,k) is the maximum steps of all halting n-state, k-symbol Terminating Turmites when started on a blank tape. It was coined by @creeperman7002 w...")
  • 20:41, 16 July 2025 ‎1RB2LA2LC--- 1LA2RB2RD--- 3RB1LC1RD0LA 3LA1RD1LC0RB (hist | edit) ‎[854 bytes] ‎Sligocki (talk | contribs) (Created page with "{{machine|1RB2LA2LC---_1LA2RB2RD---_3RB1LC1RD0LA_3LA1RD1LC0RB}} {{TM|1RB2LA2LC---_1LA2RB2RD---_3RB1LC1RD0LA_3LA1RD1LC0RB}} is a non-halting TT(2,4) TM that is "pretending to be" a probviously halting Cryptid. Rules by Shawn Ligocki: <pre> C(a, b, c) = 0^inf 3 2^a <C 1^b 2^c 3 0^inf = 0^inf 3 2^c 1^b D> 2^a 3 0^inf C(a+1, b, c) -> C(c, b+1, a) C(0, b, c+3) -> C(c, 0, b+6) C(0, b, 2) -> Halt(b+7) C(0, b, 1) -> C(b+5, 0, 2) C(0, b, 0) -> C(b+2, 0, 5) Start: C(1, 0, 2) @...")
  • 21:32, 15 July 2025 ‎TMBR: July 2025 (hist | edit) ‎[5,310 bytes] ‎Sligocki (talk | contribs) (Created page with "Category:This Month in Busy Beaver This Month in Busy Beaver for July 2025. == Champions == * (Late June) mxdys found a pair of new BB(6) champions pushing it into the pentational values: {{TM| 1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE}} (scoring over 2↑↑2↑↑2↑↑10) and {{TM|1RB1LC_1LA1RE_0RD0LA_1RZ1LB_1LD0RF_0RD1RB}} (scoring over 10↑↑11010000). * mxdys confirms dyuan's BB(2,5) champion {{TM|1RB3LA4RB0R...") originally created as "TMiBB: July 2025"
  • 02:59, 13 July 2025 ‎Reversible Turing Machine (hist | edit) ‎[3,607 bytes] ‎Sligocki (talk | contribs) (Created page with "A '''Reversible Turing Machine''' is a Turing machine for which the computation can always be run backwards from any step back to the original configuration. This property (called logical reversibility) has theoretical implications for the limits of computation. Specifically, non-reversible computation cannot scale beyond some limit due to the inherent entropy cost whereas reversible computations may be able to. == Definition == There does not seem to be a completel...") Tag: Visual edit: Switched
  • 16:43, 9 July 2025 ‎Maximum Consecutive Ones Function (hist | edit) ‎[2,967 bytes] ‎Sligocki (talk | contribs) (Created page with "The '''Maximum Consecutive Ones''' function (named <math>num(n)</math> by Ben-Amram) is a Busy Beaver function which measures the maximum number of consecutive 1s left on the tape at halt across all n-state 2-symbol Turing machines which leave all their 1s consecutively. Unlike <math>\Sigma(n)</math>, this allows some amount of order over the "API" of these TMs, so that their output can be used as inputs to another TM in some deterministic fashion. Note however,...") Tag: Visual edit: Switched
  • 21:05, 30 June 2025 ‎Busy Beaver Frontier (hist | edit) ‎[1,701 bytes] ‎Sligocki (talk | contribs) (Created page with "'''The Busy Beaver Frontier'''<ref>Scott Aaronson. 2020. [https://www.scottaaronson.com/papers/bb.pdf The Busy Beaver Frontier]. SIGACT News 51, 3 (August 2020), 32–54. https://doi.org/10.1145/3427361.3427369</ref> was a Busy Beaver survey article published by Scott Aaronson in 2020. It describes the Busy Beaver problem, introduced a number of variants (such as the Lazy Beaver and Beeping Busy Beaver) and made a number of conjectures. This article introduced ma...")
  • 05:53, 28 June 2025 ‎1RB--- 0RC0RE 1RD1RF 1LE0LB 1RC0LD 1RC1RA (hist | edit) ‎[3,193 bytes] ‎Peacemaker II (talk | contribs) (Created page with "{{machine|1RB---_0RC0RE_1RD1RF_1LE0LB_1RC0LD_1RC1RA}} {{TM|1RB---_0RC0RE_1RD1RF_1LE0LB_1RC0LD_1RC1RA}} is a probviously halting BB(6) Cryptid found by Racheline on 23 November 2024 ([https://discord.com/channels/960643023006490684/1239205785913790465/1309900024930635786 Discord link]). <pre> `1RB---_0RC0RE_1RD1RF_1LE0LB_1RC0LD_1RC1RA` is a probviously halting cryptid. just an exponential one, specifically at each step it simply multiplies the main number by...")
  • 10:35, 26 June 2025 ‎1RB1RA 1RC1RZ 1LD0RF 1RA0LE 0LD1RC 1RA0RE (hist | edit) ‎[2,549 bytes] ‎Mxdys (talk | contribs) (Created page with "{{machine|1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE}} {{TM|1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE|halt}} Current BB(6) Champion. Discovered by mxdys on 25 June 2025. It's in a family of 4 machines with the halting time and sigma score between 2↑↑2↑↑2↑↑9 and 2↑↑2↑↑2↑↑10: <pre> 1RB1RA_1RC---_1LD0RF_1RA0LE_0LD1RC_1RA0RE (hereafter referred to as TM1) 1RB---_1LC0RF_1RE0LD_0LC1RB_1RA1RE_1RE0RD (TM2) 1RB0LE_1RC1RB_1RD---_1LA0RF_0LA1RD_1RB0RE (T...") originally created as "1RB1RA 1RC--- 1LD0RF 1RA0LE 0LD1RC 1RA0RE"
  • 06:15, 17 June 2025 ‎1RB1LC 1LA1RE 0RD0LA 1RZ1LB 1LD0RF 0RD1RB (hist | edit) ‎[3,408 bytes] ‎Mxdys (talk | contribs) (Created page with "{{machine|1RB1LC_1LA1RE_0RD0LA_1RZ1LB_1LD0RF_0RD1RB}} {{TM|1RB1LC_1LA1RE_0RD0LA_1RZ1LB_1LD0RF_0RD1RB|halt}} Current BB(6) Champion. Discovered by mxdys on 16 June 2025. The halting t steps. It's in a family of 6 machines with the halting time and sigma score between 10↑↑11010000 and 10↑↑11011000: <pre> 1RB1LC_1LA1RE_0RD0LA_---1LB_1LD0RF_0RD1RB 1RB1LC_1LA1RE_0RD0LA_---1LB_1LE0RF_0RD1RB 1RB1LC_1LA1RD_1LA0LA_1LD0RE_0RF1RB_---1LB 1RB1LC_1LA1RD_1LA0LA_1LD0RE_0R...") Tag: Visual edit: Switched
  • 01:50, 11 June 2025 ‎1RB1RA 1LC1LE 1RE0LD 1LC0LF 1RZ0RA 0RA0LB (hist | edit) ‎[4,120 bytes] ‎Isokate (talk | contribs) (Created page with "{{Machine|1RB1RA_1LC1LE_1RE0LD_1LC0LF_---0RA_0RA0LB}} {{TM|1RB1RA_1LC1LE_1RE0LD_1LC0LF_1RZ0RA_0RA0LB}} is a tetrational halting BB(6) TM first discovered and analyzed by @poppuncher. It was shared on Discord on 5 Jun 2025 ([https://discord.com/channels/960643023006490684/1380384286942822561 Discord Link]). It is a translated counter that halts with a final sigma score of roughly <math>10 \uparrow \uparrow 6.96745</math>. == Analysis by @poppuncher == Most of the ini...")
  • 05:23, 7 June 2025 ‎1RB1RZ 0RC0RE 1LD1LA 1LC0LG 0RF1LF 0RD1LF 1LB0LE (hist | edit) ‎[1,599 bytes] ‎Sligocki (talk | contribs) (Created page with "{{machine|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LF_0RD1LF_1LB0LE}} {{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LF_0RD1LF_1LB0LE}} is a tetrational halting BB(7) TM with sigma score over $10 \uparrow\uparrow 519$. It was found by Andrew Ducharme on 6 Jun 2025 ([https://discord.com/channels/960643023006490684/1369339127652159509/1380710649306288180 Discord link]). == Analysis by Shawn Ligocki == This TM goes through 2 phases: Phase A and Phase B. <pre> A(a, b) = 0^inf <F 10 1^a 0...")
  • 21:29, 6 June 2025 ‎Rate of tape growth (hist | edit) ‎[1,112 bytes] ‎ISquillante (talk | contribs) (Add and fix whatever information you can. If someone knows citations, please add one for the O(n/log n) conj., thank you.)
  • 20:48, 2 June 2025 ‎1RB0LF 1RC1RB 1LD0RA 1LB0LE 1RZ0LC 1LA1LF (hist | edit) ‎[4,648 bytes] ‎Isokate (talk | contribs) (Created page with "{{TM|1RB0LF_1RC1RB_1LD0RA_1LB0LE_1RZ0LC_1LA1LF}} is a long running Halting BB(6) TM first analyzed by Katelyn Doucette on 1 Jun 2025 ([https://discord.com/channels/960643023006490684/1375512968569028648/1378916236104171562 Discord Link]). It is a shift overflow counter that halts with a final sigma score of roughly <math>10 \uparrow \uparrow 7.52390</math>. It is currently the second longest known running halting BB(6) TM. == Analysis by User:isokate|Katel...") Tag: Visual edit: Switched
  • 02:58, 25 May 2025 ‎1RB1RA 1LC1LE 0LD0LB 0RA0RF 0LC0RA 1RD--- (hist | edit) ‎[1,539 bytes] ‎C7X (talk | contribs) (Created page with "{{machine|1RB1RA_1LC1LE_0LD0LB_0RA0RF_0LC0RA_1RD---}} BB(6) cryptid, posted by mxdys on 26 July 2024<ref>https://discord.com/channels/960643023006490684/1239205785913790465/1266428071817379862</ref> and noticed by Racheline on 29 July 2024,<ref>https://discord.com/channels/960643023006490684/1239205785913790465/1267546343816171565</ref> which she referred to as "maybe pentational BB(6) cryptid". ==Analysis by Racheline== Posted by Racheline on 2 August 2024: A...")
  • 04:41, 22 May 2025 ‎1RB--- 0LC1RE 0LD1LC 1LE0RG 1RF0RC 1RC1RA 1RD0RB (hist | edit) ‎[850 bytes] ‎Sligocki (talk | contribs) (Created page with "{{machine|1RB---_0LC1RE_0LD1LC_1LE0RG_1RF0RC_1RC1RA_1RD0RB}} {{TM|1RB---_0LC1RE_0LD1LC_1LE0RG_1RF0RC_1RC1RA_1RD0RB}} is an nonhalting BB(7) TM with an infinite tetrational rule. == Analysis by Shawn Ligocki == <pre> 11 01^n D> 00 --> 01^n+2 D> 0^4 01^2n D> 0^3 --> 111 01 0001^n 01 D> 0 01^2n+1 D> 0^4 --> 1 11^2n+2 01 D> 1000101 D> 0^5 --> 0100^2 11 01 D> 00010 01^2n D> 0^4 --> 111 01 0001^n-1 0 1^5 01 D> 0001 0101^n D> $ --> 0101^2n+6 D> $ 0001^2 0 01...")
  • 03:27, 22 May 2025 ‎1RB1RF 0RC0RD 1LC1LD 1LE0RB 0RA1LG 1LC1RA ---0RF (hist | edit) ‎[1,435 bytes] ‎Sligocki (talk | contribs) (Created page with "{{machine|1RB1RF_0RC0RD_1LC1LD_1LE0RB_0RA1LG_1LC1RA_---0RF}} {{TM|1RB1RF_0RC0RD_1LC1LD_1LE0RB_0RA1LG_1LC1RA_---0RF}} is an nonhalting BB(7) TM with an infinite tetrational rule. == Analysis by Shawn Ligocki == Low level rules: <pre> 11 00^n C> 0^2 --> 00^n+2 C> 1101 00^n C> 0^3 --> 0 11^n+1 00^2 C> 0010 00^n C> 0^8 --> 01 11^n+1 0^3 1 00^2 C> 001 00^n C> 0^3 --> 01 11^n 00^2 C> 110 00^n C> 0^5 --> 0^2n+3 1 00^2 C> 0101 00^n C> 0 --> 1 Z> 1^2n+4 </p...")
Retrieved from "https://wiki.bbchallenge.org/wiki/Special:NewPages"