Register machine: Difference between revisions
Jump to navigation
Jump to search
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..." |
→Register Busy Beaver: Improved lower bounds and remade programs notation. |
||
| Line 19: | Line 19: | ||
!Champion | !Champion | ||
|- | |- | ||
| | |MBB(1) | ||
|1 | |1 | ||
|<code> | |<code>0+Z</code> | ||
|- | |- | ||
| | |MBB(2) | ||
|3 | |3 | ||
|<code> | |<code>0+B_0-B*</code> | ||
|- | |- | ||
| | |MBB(3) | ||
|5 | |5 | ||
|<code> | |<code>0+B_0+C_0-C*</code> | ||
|- | |- | ||
| | |MBB(4) | ||
| | |10 | ||
|<code> | |<code>0+B_1+C_0-BD_1-C*</code> | ||
|- | |- | ||
| | |MBB(5) | ||
| | |24 | ||
|<code> | |<code>0-DB_0+C_1-ED_1+A_1-B*</code> | ||
|- | |- | ||
| | |MBB(6) | ||
| | |49 | ||
|<code> | |<code>0+B_1-FC_1+D_0-CE_0+A_1-A*</code> | ||
|} | |} | ||
Revision as of 20:45, 9 December 2025
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.
| Domain | Lower Bound | Champion |
|---|---|---|
| MBB(1) | 1 | 0+Z
|
| MBB(2) | 3 | 0+B_0-B*
|
| MBB(3) | 5 | 0+B_0+C_0-C*
|
| MBB(4) | 10 | 0+B_1+C_0-BD_1-C*
|
| MBB(5) | 24 | 0-DB_0+C_1-ED_1+A_1-B*
|
| MBB(6) | 49 | 0+B_1-FC_1+D_0-CE_0+A_1-A*
|