New pages

Jump to navigation Jump to search
New pages
Hide registered users | Show bots | Show redirects

19 December 2025

17 December 2025

  • 09:3509:35, 17 December 2025 Turing completeness (hist | edit) [772 bytes] Azerty (talk | contribs) (Created page with "A Turing-complete system is a system that can compute every computable functions. A Turing-complete system can be used to simulate any Turing machine or other Turing-complete systems. The halting problem is uncomputable on any Turing-complete system. To be Turing-complete, a system must be able to store unbounded memory, access it and must contain non-halting programs (like "while" loops or recursion). === List of Turing-complete systems === This list is non-exhaustiv...") Tag: Visual edit

9 December 2025

8 December 2025

  • 16:2016:20, 8 December 2025 Register machine (hist | edit) [1,885 bytes] Azerty (talk | contribs) (Created page with "Register machines, also known as Minsky machines, are a Turing-complete model of computation. Register machines contain a set of instructions and at least 2 registers. Each instruction in a program has a number, starting with 1. There are 2 types of instructions: * inc(c, n) add 1 to the register c then jumps to instruction n. * dec(c, n, m) jumps to instruction m if register c equal 0 else subtract 1 to the register c then jump to instruction n. The program halt if...") Tag: Visual edit

6 December 2025

5 December 2025

4 December 2025

2 December 2025

29 November 2025

28 November 2025

  • 12:4512:45, 28 November 2025 Busy Beaver for SKI calculus (hist | edit) [609 bytes] Azerty (talk | contribs) (Created page with "Busy Beaver for SKI calculus (we will call it BBSKI for now) is a variation of the Busy Beaver problem for lambda calculus. == Champions == {| class="wikitable" ! n !! Value !! Champion !! Discoverered by |- | 1 || = 1 || S || ? |- | 2 || = 2 || SS || ? |- | 3 || = 3 || SSS || ? |- | 4 || = 4 || SSSS || ? |- | 5 || = 6 || SSS(SS) || ? |- | 6 || >= 8 || SSS(SSS) || ? |} == See Also == [https://komiamiko.me/math/ordinals/2020/06/21/ski-numerals.html Lower bounds of this...")

23 November 2025

22 November 2025

19 November 2025

17 November 2025

15 November 2025

10 November 2025

  • 20:2520:25, 10 November 2025 Fractran (hist | edit) [27,225 bytes] Sligocki (talk | contribs) (Created page with "'''Fractran''' (originally styled FRACTRAN) is an esoteric model of computation invented by John Conway in 1987.<ref>Conway, John H. (1987). "FRACTRAN: A Simple Universal Programming Language for Arithmetic". ''Open Problems in Communication and Computation''. Springer-Verlag New York, Inc. pp. 4–26. <nowiki>http://doi.org/10.1007/978-1-4612-4808-8_2</nowiki></ref> In this model a program is simply a finite list of fractions, the program state is an integer. For more d...") Tag: Visual edit: Switched
  • 19:5819:58, 10 November 2025 1RB2RA3LB---2LB 2LA0LA4RB0RB1LA (hist | edit) [403 bytes] Sligocki (talk | contribs) (Created page with "{{machine|1RB2RA3LB---2LB_2LA0LA4RB0RB1LA}} {{stub}} {{TM|1RB2RA3LB---2LB_2LA0LA4RB0RB1LA}} appears to be a tetrational BB(2,5) probviously halting Cryptid. Racheline estimates the probability that it surpasses the current champion ({{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ}}) is 1/8. https://discord.com/channels/960643023006490684/1259770421046411285/1329809402378719273")

5 November 2025

28 October 2025

  • 18:0918:09, 28 October 2025 Generalized Collatz Function (hist | edit) [2,629 bytes] Sligocki (talk | contribs) (Created page with "A '''Generalized Collatz Function (GCF)''' is a function which naturally generalizes the classic Collatz function defined by Conway in his 1972 paper "Unpredictable iterations".<ref name=":0">John. H. Conway. 1972. [https://gwern.net/doc/cs/computable/1972-conway.pdf Unpredictable iterations]. In Proc. 1972 Number Theory Conf., Univ. Colorado, Boulder, pages 49–52.</ref> They are functions defined piecewise based upon the remainder of the input (modulo some value) wher...") Tag: Visual edit

26 October 2025

24 October 2025

22 October 2025

  • 18:0118:01, 22 October 2025 1RB1RF 0LC1RC 1RD1LC 1RZ0RE 1RA1LF 1RA0LE (hist | edit) [3,560 bytes] Sligocki (talk | contribs) (Created page with "{{machine|1RB1RF_0LC1RC_1RD1LC_---0RE_1RA1LF_1RA0LE}} {{TM|1RB1RF_0LC1RC_1RD1LC_---0RE_1RA1LF_1RA0LE}} == Analysis by Shawn Ligocki == https://discord.com/channels/960643023006490684/1239205785913790465/1430590536825442384 <pre> 1RB1RF_0LC1RC_1RD1LC_---0RE_1RA1LF_1RA0LE A> 10 -> 11 A> 0 1^n A> 00 -> 11 A> 1^n 0 for n >= 1 0 1^2k+3 A> 11 -> 1^4 0 1^2k+1 A> 0 1 A> 1^2 0 -> 1^5 Z> (Halt) 0 1 A> 1^3 0 -> 1^4 0 1 A> 0 1 A> 1^4 -> 1^5 A> 1 0 1^2k A> 11 -> 1^2k+3 A> A(...") originally created as "1RB1RF 0LC1RC 1RD1LC ---0RE 1RA1LF 1RA0LE"

19 October 2025

  • 14:1214:12, 19 October 2025 1RB2LB0LB 2LC2LA0LA 2RD1LC1RZ 1RA2LD1RD (hist | edit) [4,159 bytes] Polygon (talk | contribs) (Created page with "{{machine|1RB2LB0LB_2LC2LA0LA_2RD1LC1RZ_1RA2LD1RD}} {{TM|1RB2LB0LB_2LC2LA0LA_2RD1LC1RZ_1RA2LD1RD|halt}} is a pentational halting BB(4,3) TM. It was discovered in May 2024 by Pavel Kropitz as one of seven long running TMs and achieves a score of over <math>3 \uparrow\uparrow\uparrow 88574</math>. Polygon analysed the TM by hand in October 2025, providing its score. Pavel listed the halting tape as: <pre> 1 Z> 1^(162*3^((3*<(243*3^(6) - 5)/2; (<(54*3^((3b + 11)/2) - 2...")

12 October 2025

6 October 2025

5 October 2025

30 September 2025

  • 20:3720:37, 30 September 2025 Piecewise Affine Function (hist | edit) [6,210 bytes] Sligocki (talk | contribs) (Created page with "'''Linear-Inequality Affine Transformation Automata (LIATA)''' are a model for computation based upon applying affine transformations to vectors based on cases defined by linear inequalities. They are a generalization of the rules for BMO1 and were proven to be Turing complete. == Example == An example of a LIATA are the rules for BMO1:<math display="block">f(a,b) = \begin{cases} (a-b, 4b+2) & \text{if } a > b \\ (2a+1, b-a) & \text{if } a < b \\ \end{cases}</ma...") Tag: Visual edit originally created as "Linear-Inequality Affine Transformation Automata"
  • 17:1117:11, 30 September 2025 Bug Game (hist | edit) [6,416 bytes] Sligocki (talk | contribs) (Created page with "The '''Bug Game''' is an optimization game in which players design a 2d ''maze'' that a ''bug'' will be slowest to solve. The bug follows a relatively simple algorithm which preferentially visits locations less visited which is guaranteed to always eventually find a way to the destination (if such a path exists), but by exploiting the details of the tie-breaking logic, some mazes can trap the bug for a long time. You can play online at https://buglab.ru/ == History == T...")

29 September 2025

23 September 2025

Retrieved from "https://wiki.bbchallenge.org/wiki/Special:NewPages"