Register machine - Revision history

Bard at 05:11, 26 March 2026

2026-03-26T05:11:07Z

← Older revision		Revision as of 05:11, 26 March 2026
Line 39:		Line 39:
	\|<code>0-DB_0+C_1-ED_1+A_1-B*</code>		\|<code>0-DB_0+C_1-ED_1+A_1-B*</code>
	\|-		\|-
	\|MBB(6)		\|MBB(6,2)
	\|49*		\|≥49
	\|<code>0+B_1-FC_1+D_0-CE_0+A_1-A*</code>		\|<code>0+B_1-FC_1+D_0-CE_0+A_1-A*</code>
	\|}		\|}
	~~Entries in the Halting Time column marked with * are only proved to be a lower bound, not the actual value of MBB(n).~~

	== Cryptids ==		== Cryptids ==

Sligocki: Link Turing complete

2025-12-17T17:00:20Z

Link Turing complete

← Older revision		Revision as of 17:00, 17 December 2025
Line 1:		Line 1:
	'''Register machines''', also known as '''Minsky machines''', are a Turing-complete model of computation.		'''Register machines''', also known as '''Minsky machines''', are a [[Turing complete\|Turing-complete]] model of computation.

	Register machines contain a set of instructions and at least 2 registers.		Register machines contain a set of instructions and at least 2 registers.

Polygon: Added category:functions

2025-12-10T20:50:19Z

Added category:functions

← Older revision		Revision as of 20:50, 10 December 2025
Line 53:		Line 53:
	S(2k,w+1) = A:[2k-3,0,w+1] -> A:[3k-3,0,w] = S(3k,w)		S(2k,w+1) = A:[2k-3,0,w+1] -> A:[3k-3,0,w] = S(3k,w)
	S(2k+1,w) = A:[2k-2,0,w] -> A:[3k-2,0,w+2] = S(3k+1,w+2)		S(2k+1,w) = A:[2k-2,0,w] -> A:[3k-2,0,w+2] = S(3k+1,w+2)

			[[Category:functions]]

Sligocki: Add Hydra

2025-12-10T03:59:51Z

Add Hydra

← Older revision		Revision as of 03:59, 10 December 2025
Line 1:		Line 1:
	Register machines, also known as Minsky machines, are a Turing-complete model of computation.		'''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.		Register machines contain a set of instructions and at least 2 registers.
Line 13:		Line 13:

	== Register Busy Beaver ==		== Register Busy Beaver ==
	The Register Busy Beaver function, denoted MBB(n), returns the maximum number of instructions executed by a register machine with ~~2 counters~~.		The Register Busy Beaver function, denoted MBB(n,r), returns the maximum number of instructions executed by a register machine with n states and r registers when started in state A and all registered initialized to 0. MBB(n) = MBB(n,n) (unlimited registers).
	{\| class="wikitable"		{\| class="wikitable"
	!Domain		!Domain
Line 44:		Line 44:
	\|}		\|}
	Entries in the Halting Time column marked with * are only proved to be a lower bound, not the actual value of MBB(n).		Entries in the Halting Time column marked with * are only proved to be a lower bound, not the actual value of MBB(n).

			== Cryptids ==
			No [[Cryptids]] have been found via exhaustive search, but [[Hydra]] has been hand coded into a 10-state, 3-register Minsky machine: <code>0-BF_1+C_1+D_0-EH_1+A_2+G_2+I_2-I*_0+J_1-IA</code> which can be interpreted the following way:<sup>[https://discord.com/channels/960643023006490684/1243312334907375676/1446694179337011325]</sup>
			Let S(h,w) = A:[h-3,0,w]

			Start: A:[0,0,0] = S(3,0)
			S(2k,0) = A:[2k-3,0,0] -> Halt
			S(2k,w+1) = A:[2k-3,0,w+1] -> A:[3k-3,0,w] = S(3k,w)
			S(2k+1,w) = A:[2k-2,0,w] -> A:[3k-2,0,w+2] = S(3k+1,w+2)

Bard: MBB(1)-MBB(5) are proved, not just a lower bound, assuming the accuracy of my program.

2025-12-10T03:35:12Z

MBB(1)-MBB(5) are proved, not just a lower bound, assuming the accuracy of my program.

← Older revision		Revision as of 03:35, 10 December 2025
Line 16:		Line 16:
	{\| class="wikitable"		{\| class="wikitable"
	!Domain		!Domain
	!~~Lower Bound~~		!Halting Time
	!Champion		!Champion
	\|-		\|-
Line 40:		Line 40:
	\|-		\|-
	\|MBB(6)		\|MBB(6)
	\|49		\|49*
	\|<code>0+B_1-FC_1+D_0-CE_0+A_1-A*</code>		\|<code>0+B_1-FC_1+D_0-CE_0+A_1-A*</code>
	\|}		\|}
			Entries in the Halting Time column marked with * are only proved to be a lower bound, not the actual value of MBB(n).

Azerty: /* Register Busy Beaver */

2025-12-09T20:45:42Z

← Older revision		Revision as of 20:45, 9 December 2025
Line 13:		Line 13:

	== Register Busy Beaver ==		== Register Busy Beaver ==
	The Register Busy Beaver function, ~~currently~~ denoted ~~CBB~~(n), returns the maximum number of instructions executed by a register machine with 2 counters.		The Register Busy Beaver function, denoted MBB(n), returns the maximum number of instructions executed by a register machine with 2 counters.
	{\| class="wikitable"		{\| class="wikitable"
	!Domain		!Domain

Azerty: /* Register Busy Beaver */ Improved lower bounds and remade programs notation.

2025-12-09T20:45:19Z

← Older revision		Revision as of 20:45, 9 December 2025
Line 19:		Line 19:
	!Champion		!Champion
	\|-		\|-
	\|~~RBB~~(1)		\|MBB(1)
	\|1		\|1
	\|<code>~~A- > H, 1~~</code>		\|<code>0+Z</code>
	\|-		\|-
	\|~~RBB~~(2)		\|MBB(2)
	\|3		\|3
	\|<code>A- ~~> H, 2 / A+ > 1~~</code>		\|<code>0+B_0-B*</code>
	\|-		\|-
	\|~~RBB~~(3)		\|MBB(3)
	\|5		\|5
	\|<code>A+ ~~> 2 / B~~- ~~> H, 3 / B+ > 1~~</code>		\|<code>0+B_0+C_0-C*</code>
	\|-		\|-
	\|~~RBB~~(4)		\|MBB(4)
	\|8		\|10
	\|<code>B+ ~~> 2 / B~~+ ~~> 3 / A+ > 4 / B~~- ~~> 3, H~~</code>		\|<code>0+B_1+C_0-BD_1-C*</code>
	\|-		\|-
	\|~~RBB~~(5)		\|MBB(5)
	\|11		\|24
	\|<code>B+ ~~> 2 / B~~+ ~~> 3 / A+ > 4 / A+ > 5 /~~ B~~- > 3, H~~</code>		\|<code>0-DB_0+C_1-ED_1+A_1-B*</code>
	\|-		\|-
	\|~~RBB~~(6)		\|MBB(6)
	\|15		\|49
	\|<code>B+ ~~> 2 / B~~+ ~~> 3 / B~~+ ~~> 4 / A+ > 5 /~~ A~~+ > 6 / B- > 4, H~~</code>		\|<code>0+B_1-FC_1+D_0-CE_0+A_1-A*</code>
	\|}		\|}

Azerty: 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..."

2025-12-08T16:20:50Z

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..."

New page

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 it reaches an undefined instruction. Here we represent it with the letter H.

== Register Busy Beaver ==
The Register Busy Beaver function, currently denoted CBB(n), returns the maximum number of instructions executed by a register machine with 2 counters.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|RBB(1)
|1
|<code>A- > H, 1</code>
|-
|RBB(2)
|3
|<code>A- > H, 2 / A+ > 1</code>
|-
|RBB(3)
|5
|<code>A+ > 2 / B- > H, 3 / B+ > 1</code>
|-
|RBB(4)
|8
|<code>B+ > 2 / B+ > 3 / A+ > 4 / B- > 3, H</code>
|-
|RBB(5)
|11
|<code>B+ > 2 / B+ > 3 / A+ > 4 / A+ > 5 / B- > 3, H</code>
|-
|RBB(6)
|15
|<code>B+ > 2 / B+ > 3 / B+ > 4 / A+ > 5 / A+ > 6 / B- > 4, H</code>
|}