lukaskalbertodt / beaver Goto Github PK

Basically just a personal reminder about what I planned on doing next.

• Change representation of Tm to use 5 bits per action, 10 per state. That allows us to fit everything into an u64 for up to N=6. So that will be the new and official "upper limit of N".
• Rewrite gen by first adding a trait that abstracts over different generators. It's still unclear whether we can/should use parts of Iterator. It also has to be considered how to best make this suitable for chunking into multiple threads.
  • num_tms(): returns the total number of TMs that generator will yield
  • for_all(impl FnMut(Tm)) or something like that
  • random_tm()
• Implement different generators. One should simply generate all TMs without any deduplication. But then there should be different generators that apply deduplication already.
  • Actions that transition to the halt state should only be generated with one "head move" direction, because that value doesn't matter.
  • Actions that transition to the halt state and write 0 could be ignored since they are not busy beaver, i.e. there trivially always exists a TM that writes one additional 1 to the tape.
  • One can just flip all "head move" directions of all states and get an equivalent TM, which produces the exact same result, just with a mirrored tape. To solve this, one can simply fix the direction of one action of one state. E.g. states[0].on_0.direction is never set to "right".
  • States can be permuted by just renaming states basically. It's still unclear how to avoid all of these duplicates, preferably very quickly.
• Adjust output, CLI args and run function to be able to use different generators
• Make it possible to visualize a run of one TM in a nice way.
• Add CLI mode to run/print a single TM.
• Experiment: code some new mode, that tries to generate long-running (but halting) TMs in Darwin-evolution like fashion, i.e. by letting the best produce offspring with random mutations. Could be a total failure, but it's interesting to try.