New pages
Jump to navigation
Jump to search
- 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
- 17:03, 13 August 2025 1RB1LE 1LC0RA 1RB1LD 1LC0LC 1RF0LB ---1RE (hist | edit) [55 bytes] Qwerpiw (talk | contribs) (Redirected page to 1RB1LC 1LA1RE 0RD0LA 1RZ1LB 1LD0RF 0RD1RB) Tag: New redirect
- 17:02, 13 August 2025 1RB1LC 1LA1RD 1LA0LA 1LF0RE 0RF1RB ---1LB (hist | edit) [55 bytes] Qwerpiw (talk | contribs) (Redirected page to 1RB1LC 1LA1RE 0RD0LA 1RZ1LB 1LD0RF 0RD1RB) Tag: New redirect
- 17:01, 13 August 2025 1RB1LC 1LA1RD 1LA0LA 1LD0RE 0RF1RB ---1LC (hist | edit) [55 bytes] Qwerpiw (talk | contribs) (Redirected page to 1RB1LC 1LA1RE 0RD0LA 1RZ1LB 1LD0RF 0RD1RB) Tag: New redirect
- 17:01, 13 August 2025 1RB1LC 1LA1RD 1LA0LA 1LD0RE 0RF1RB ---1LB (hist | edit) [55 bytes] Qwerpiw (talk | contribs) (Redirected page to 1RB1LC 1LA1RE 0RD0LA 1RZ1LB 1LD0RF 0RD1RB) Tag: New redirect
- 17:00, 13 August 2025 1RB1LC 1LA1RE 0RD0LA ---1LB 1LE0RF 0RD1RB (hist | edit) [55 bytes] Qwerpiw (talk | contribs) (Redirected page to 1RB1LC 1LA1RE 0RD0LA 1RZ1LB 1LD0RF 0RD1RB) Tag: New redirect
- 16:59, 13 August 2025 1RB0RF 1RC1RB 1RD--- 1LE0RA 1RB0LF 0LE1RD (hist | edit) [55 bytes] Qwerpiw (talk | contribs) (Redirected page to 1RB1RA 1RC1RZ 1LD0RF 1RA0LE 0LD1RC 1RA0RE) Tag: New redirect
- 16:58, 13 August 2025 1RB0LE 1RC1RB 1RD--- 1LA0RF 0LA1RD 1RB0RE (hist | edit) [55 bytes] Qwerpiw (talk | contribs) (Redirected page to 1RB1RA 1RC1RZ 1LD0RF 1RA0LE 0LD1RC 1RA0RE) Tag: New redirect
- 16:57, 13 August 2025 1RB--- 1LC0RF 1RE0LD 0LC1RB 1RA1RE 1RE0RD (hist | edit) [55 bytes] Qwerpiw (talk | contribs) (Redirected page to 1RB1RA 1RC1RZ 1LD0RF 1RA0LE 0LD1RC 1RA0RE) Tag: New redirect
- 10:30, 11 August 2025 Champion (hist | edit) [23 bytes] Polygon (talk | contribs) (Created a redirect to "Champions") Tag: New redirect
- 05:24, 11 August 2025 Σ(6,2) (hist | edit) [19 bytes] Xl643 (talk | contribs) (Redirected page to BB(6)) Tag: New redirect
- 05:21, 11 August 2025 S(6,2) (hist | edit) [19 bytes] Xl643 (talk | contribs) (Redirected page to BB(6)) Tag: New redirect
- 05:20, 11 August 2025 Σ(6) (hist | edit) [19 bytes] Xl643 (talk | contribs) (Redirected page to BB(6)) Tags: New redirect Visual edit: Switched
- 05:19, 11 August 2025 S(6) (hist | edit) [19 bytes] Xl643 (talk | contribs) (Redirected page to BB(6)) Tag: New redirect
- 03:58, 11 August 2025 Bonus cryptid (hist | edit) [45 bytes] Int-y1 (talk | contribs) (Redirected page to 1RB3RB---3LA1RA 2LA3RA4LB0LB1LB) Tag: New redirect
- 19:56, 10 August 2025 0RB1RB 1LC0RA 1RE1LF 1LF1RE 0RD1RD 1LG0LG ---1LB (hist | edit) [21 bytes] ADucharme (talk | contribs) (make BB(7)-compiled Bigfoot redirect to Bigfoot page) Tag: New redirect
- 03:24, 9 August 2025 FAR (hist | edit) [45 bytes] Sligocki (talk | contribs) (Redirected page to Finite Automata Reduction (FAR)) Tags: New redirect Visual edit
- 03:24, 9 August 2025 CTL (hist | edit) [40 bytes] Sligocki (talk | contribs) (Redirected page to Closed Tape Language (CTL)) Tags: New redirect Visual edit
- 03:24, 9 August 2025 CPS (hist | edit) [39 bytes] Sligocki (talk | contribs) (Redirected page to Closed Position Set (CPS)) Tags: New redirect 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
- 10:23, 2 August 2025 TT (hist | edit) [33 bytes] Int-y1 (talk | contribs) (Redirected page to Terminating Turmite) Tag: New redirect
- 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...")
- 01:37, 30 July 2025 BBS (hist | edit) [68 bytes] Sligocki (talk | contribs) (Redirected page to Non-halting Turing machine#Translated cycler preperiod) Tags: New redirect Visual edit
- 01:34, 30 July 2025 BBP (hist | edit) [65 bytes] Sligocki (talk | contribs) (Redirected page to Non-halting Turing machine#Translated cycler period) Tags: New redirect Visual edit
- 02:05, 28 July 2025 BBB (hist | edit) [33 bytes] Int-y1 (talk | contribs) (Redirected page to Beeping Busy Beaver) Tag: New redirect
- 03:27, 27 July 2025 1RB2LA1RA1RA 1LB1LA3RB--- (hist | edit) [39 bytes] Sligocki (talk | contribs) (Redirected page to 1RB2LA1RA1RA 1LB1LA3RB1RZ) Tags: New redirect Visual edit
- 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^...")
- 19:31, 26 July 2025 Initial Busy Beaver (hist | edit) [31 bytes] Qwerpiw (talk | contribs) (Referring to <math>BB_{init}(n, m, T)</math>) Tag: New redirect
- 19:20, 26 July 2025 Σi (hist | edit) [45 bytes] Qwerpiw (talk | contribs) (Redirected page to Instruction-limited busy beaver) Tag: New redirect
- 10:17, 25 July 2025 BBi (hist | edit) [45 bytes] Int-y1 (talk | contribs) (Redirected page to Instruction-Limited Busy Beaver) Tag: New redirect
- 18:36, 22 July 2025 Bouncers (hist | edit) [21 bytes] Sligocki (talk | contribs) (Redirected page to Bouncer) Tags: New redirect Visual edit
- 18:34, 22 July 2025 MITMWFAR (hist | edit) [78 bytes] Sligocki (talk | contribs) (Redirected page to Meet-in-the-Middle Weighted Finite Automata Reduction (MITMWFAR)) Tags: New redirect Visual edit: Switched
- 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"
- 06:53, 13 July 2025 Bbchallenge (hist | edit) [35 bytes] Sligocki (talk | contribs) (Redirected page to Busy Beaver Challenge) Tags: New redirect Visual edit
- 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
- 02:46, 13 July 2025 Turing Machine (hist | edit) [28 bytes] Sligocki (talk | contribs) (Redirected page to Turing machine) Tag: New redirect
- 16:43, 9 July 2025 Num (hist | edit) [47 bytes] Sligocki (talk | contribs) (Redirect) Tags: New redirect Visual edit
- 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"
