How to Optimize Rust for Slowness: Inspired by New Turing Machine Results

a year ago

The article explores how to write Rust programs that run for an extraordinarily long time, focusing on absurdly slow execution.
It introduces several rule sets to constrain program behavior, such as infinite loops, finite memory, and Turing machines.
Rule Set 1 allows infinite loops, providing a trivial but uninteresting solution with `loop {}`.
Rule Set 2 requires programs to halt but allows finite memory, demonstrated with nested loops counting to `u128::MAX`.
Rule Set 3 introduces infinite, zero-initialized memory and uses a 5-state Turing machine that halts after 47 million steps.
Rule Set 4 escalates complexity with a 6-state Turing machine that runs for more than 10↑↑15 steps before halting.
Rule Set 5 demonstrates computing tetration (10↑↑15) in Rust without Turing machines, using only zero-initialized memory.
The article also covers optimization techniques for slow programs, including SIMD and parallel processing for visualization.
Key surprises include the simplicity of nested loops for long runtimes and the dramatic complexity jump from 5- to 6-state Turing machines.
The conclusion reflects on the insights gained about computation, memory, and minimal systems through these exercises.

Hasty Briefsbeta