<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="en">
	<id>https://wiki.bbchallenge.org/w/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=Mathmasterzach</id>
	<title>BusyBeaverWiki - User contributions [en]</title>
	<link rel="self" type="application/atom+xml" href="https://wiki.bbchallenge.org/w/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=Mathmasterzach"/>
	<link rel="alternate" type="text/html" href="https://wiki.bbchallenge.org/wiki/Special:Contributions/Mathmasterzach"/>
	<updated>2026-11-18T19:41:11Z</updated>
	<subtitle>User contributions</subtitle>
	<generator>MediaWiki 1.43.5</generator>
	<entry>
		<id>https://wiki.bbchallenge.org/w/index.php?title=Register_machine&amp;diff=7905</id>
		<title>Register machine</title>
		<link rel="alternate" type="text/html" href="https://wiki.bbchallenge.org/w/index.php?title=Register_machine&amp;diff=7905"/>
		<updated>2026-06-25T13:07:44Z</updated>

		<summary type="html">&lt;p&gt;Mathmasterzach: MBB 6 decided. Added analysis of current MBB 8 champion.&lt;/p&gt;
&lt;hr /&gt;
&lt;div&gt;&#039;&#039;&#039;Register machines&#039;&#039;&#039;, also known as &#039;&#039;&#039;Minsky machines&#039;&#039;&#039;, are a [[Turing complete|Turing-complete]] model of computation.&lt;br /&gt;
&lt;br /&gt;
Register machines contain a set of instructions and a set of registers. The instructions are labelled A, B, C, and so on. The registers are numbered 0, 1, 2, and so on. There are 2 types of instructions:&lt;br /&gt;
&lt;br /&gt;
* inc(c, n) adds 1 to the register c then jumps to instruction n.&lt;br /&gt;
* dec(c, n, m) jumps to instruction m if register c equals 0, else subtract 1 to the register c then jump to instruction n.&lt;br /&gt;
&lt;br /&gt;
The program halts if it reaches an undefined instruction. Here we label an undefined instruction with &amp;lt;code&amp;gt;*&amp;lt;/code&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
== Register Busy Beaver ==&lt;br /&gt;
The Register Busy Beaver function, denoted MBB(n,r), returns the maximum number of instructions executed by a register machine with n instructions and r registers when started in instruction A and all registers initialized to 0. MBB(n) = MBB(n,n) (unlimited registers).&lt;br /&gt;
{| class=&amp;quot;wikitable&amp;quot;&lt;br /&gt;
!Domain&lt;br /&gt;
!Halting Time&lt;br /&gt;
!Champion&lt;br /&gt;
|-&lt;br /&gt;
|MBB(1)&lt;br /&gt;
|1&lt;br /&gt;
|&amp;lt;code&amp;gt;0+*&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|MBB(2)&lt;br /&gt;
|3&lt;br /&gt;
|&amp;lt;code&amp;gt;0+B_0-B*&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|MBB(3)&lt;br /&gt;
|5&lt;br /&gt;
|&amp;lt;code&amp;gt;0+B_0+C_0-C*&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|MBB(4)&lt;br /&gt;
|10&lt;br /&gt;
|&amp;lt;code&amp;gt;0+B_1+C_0-BD_1-C*&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|MBB(5)&lt;br /&gt;
|24&lt;br /&gt;
|&amp;lt;code&amp;gt;0-DB_0+C_1-ED_1+A_1-B*&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|MBB(6)&lt;br /&gt;
|49&lt;br /&gt;
|&amp;lt;code&amp;gt;0+B_1-FC_1+D_0-CE_0+A_1-A*&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|MBB(7)&lt;br /&gt;
|≥231&lt;br /&gt;
|&amp;lt;code&amp;gt;0+B_0+C_0+D_1-GE_1+F_0-EC_1-A*&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|MBB(8)&lt;br /&gt;
|≥3394&lt;br /&gt;
|&amp;lt;code&amp;gt;0+B_0+C_1-GD_1+E_0-DF_2-HG_2+A_2-D*&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|MBB(9)&lt;br /&gt;
|≥9870&lt;br /&gt;
|&amp;lt;code&amp;gt;0+B_0+C_0+D_1-IE_1+F_0-GI_0-HC_0-E*_0+A&amp;lt;/code&amp;gt;&lt;br /&gt;
|}&lt;br /&gt;
&lt;br /&gt;
MBB(9) is likely unoptimal.&lt;br /&gt;
&lt;br /&gt;
== Analysis ==&lt;br /&gt;
The current best MBB(8) machine can be described at a high level as follows:&lt;br /&gt;
 Let S(z) = F:[0, 2z+1, z]&lt;br /&gt;
 &lt;br /&gt;
 Start: F:[0, 9, 4] = S(4)&lt;br /&gt;
 S(2k) = S(5k+2)&lt;br /&gt;
 S(2k+1) = Halt&lt;br /&gt;
&lt;br /&gt;
This results in the sequence: &amp;lt;code&amp;gt;S(4), S(12), S(32), S(82), S(207)&amp;lt;/code&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
== Cryptids ==&lt;br /&gt;
No [[Cryptids]] have been found via exhaustive search, but [[Hydra]] has been hand coded into a 10-instruction, 3-register Minsky machine: &amp;lt;code&amp;gt;0-BF_1+C_1+D_0-EH_1+A_2+G_2+I_2-I*_0+J_1-IA&amp;lt;/code&amp;gt; which can be interpreted the following way:&amp;lt;sup&amp;gt;[https://discord.com/channels/960643023006490684/1243312334907375676/1446694179337011325]&amp;lt;/sup&amp;gt;&lt;br /&gt;
 Let S(h,w) = A:[h-3,0,w]&lt;br /&gt;
 &lt;br /&gt;
 Start: A:[0,0,0] = S(3,0)&lt;br /&gt;
 S(2k,0) = A:[2k-3,0,0] -&amp;gt; Halt&lt;br /&gt;
 S(2k,w+1) = A:[2k-3,0,w+1] -&amp;gt; A:[3k-3,0,w] = S(3k,w)&lt;br /&gt;
 S(2k+1,w) = A:[2k-2,0,w] -&amp;gt; A:[3k-2,0,w+2] = S(3k+1,w+2)&lt;br /&gt;
&lt;br /&gt;
[[Category:functions]]&lt;/div&gt;</summary>
		<author><name>Mathmasterzach</name></author>
	</entry>
</feed>