Instruction-Limited Busy Beaver

From BusyBeaverWiki
Revision as of 21:47, 16 July 2025 by 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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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 reaches an undefined transition (unlike in the traditional Busy Beaver problem where the TM must make an explicit halting transition which adds one more step).

See Also

Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=Instruction-Limited_Busy_Beaver&oldid=2512"