Despite all the reporting on BB(5) I had never seen anyone convey that equivalent high-level formulation from 1993, that's very cool!
EDIT: For fun I converted it to Rust and expected to see it spew a few million numbers into my terminal, but no, this equivalent loop actually terminates after 15 steps, which is fascinating given that the Turing machine takes 47 million steps:
let mut x = 0;
loop {
x = match x % 3 {
0 => 5 * x + 18,
1 => 5 * x + 22,
_ => break
} / 3;
}
EDIT 2: Of course the article mentions this in the next paragraph, which is what I get for being immediately nerd-sniped.
This is because your Rust program represents the numbers in binary, while the BB(5) champion Turing machine represents them in unary. And unary arithmetic is exponentially slower than place-value arithmetic, which is why we invented the latter. (There are other inefficiencies in the Turing machine, but that's the big conceptual one.)
Nitpicking: just as TMs can use binary or decimal arithmetic, so could Rust programs use unary. It's not an inefficiency in TMs per se, but I can see how it would help a TM to become a BB champion.
> could Rust programs use unary
By not using any math functions except for increment by one?
By representing all numbers with lists (or sets). 0 = [] 1 = [True] 2 = [True, True] Etc. Then for example addition becomes appending two lists together
What else comes to mind in terms of inefficiencies? I can think of quite a few but you seem to have deeper insight as to their ranking so I'm curious as to your thoughts.