Skip to content

Simulating Turing machines for the Busy Beaver game

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT
Notifications You must be signed in to change notification settings

LukasKalbertodt/beaver

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

80 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Busy Beaver

An application that analyses/simulates all possible N-state Turing machines with tape alphabet = {0, 1}, where N is given as command line argument. All TMs are generated, then categorized based on static analysis or their runtime behavior. Finally, a summary of all results is printed. This is related to the Busy Beaver game.

Features:

  • Nice output, including histogram
  • Fairly fast (on a Ryzen 3600, N=4 with its 11 billion TMs, 5.5 billion deduplicated, runs in roughly half a minute)
  • Static analysis: state graph reachability check
  • Can detect and categorize ≈97% of non-halting TMs (for N=4)

Potential goals for future development

  • Optimize
  • More smart analysis techniques
  • Print states of certain TMs (e.g. the winning one)
  • Show trace of the winning TM

Note that this is just a hobby project which I don't expect to be useful to anyone. If you are still interested, PRs are always welcome.


License

Licensed under either of Apache License, Version 2.0 or MIT license at your option. Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this project by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

About

Simulating Turing machines for the Busy Beaver game

Topics

Resources

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT

Stars

Watchers

Forks