3 ms·
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
by kibwen 1y ago
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;
}
OEIS link: https://oeis.org/A386909 https://oeis.org/A386909
EDIT 2: Of course the article mentions this in the next paragraph, which is what I get for being immediately nerd-sniped.
- ameliaquining 1y agoThis 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.)
- achierius 1y agoWhat 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.
- tgv 1y agoNitpicking: 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.
- rini17 1y ago> could Rust programs use unary By not using any math functions except for increment by one?
- JulianChastain 1y agoBy representing all numbers with lists (or sets). 0 = [] 1 = [True] 2 = [True, True] Etc. Then for example addition becomes appending two lists together