Brady's algorithm: Difference between revisions
(Can't get busy beavers for free) |
(Link to main TNF article) |
||
| Line 1: | Line 1: | ||
Main article: [[Tree Normal Form]]. | |||
'''Brady's algorithm''' is an algorithm for finding long-running Turing machines, given a set of [[deciders]]. It was first introduced by Allen Brady in his 1964 PhD dissertation "[https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/zk51vk21c Solutions of restricted cases of the halting problem applied to the determination of particular values of a non-computable function]".<ref name="DrozdBrady">Something Something Programming, "[https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html Brady's Algorithm for Program Generation]" (2022). Accessed 15 November 2024.</ref> | '''Brady's algorithm''' is an algorithm for finding long-running Turing machines, given a set of [[deciders]]. It was first introduced by Allen Brady in his 1964 PhD dissertation "[https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/zk51vk21c Solutions of restricted cases of the halting problem applied to the determination of particular values of a non-computable function]".<ref name="DrozdBrady">Something Something Programming, "[https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html Brady's Algorithm for Program Generation]" (2022). Accessed 15 November 2024.</ref> | ||
Revision as of 15:32, 15 November 2024
Main article: Tree Normal Form.
Brady's algorithm is an algorithm for finding long-running Turing machines, given a set of deciders. It was first introduced by Allen Brady in his 1964 PhD dissertation "Solutions of restricted cases of the halting problem applied to the determination of particular values of a non-computable function".[1]
The algorithm works by building a pile of incomplete Turing machine rulesets. Each partially specified Turing machine in the pile is run until either a decider rules out the machine, in which case it is removed from the pile, or an undefined transition is reached, in which case all extensions of the ruleset at that point are added to the pile. (All extensions assuming a restriction: the maximum state number appearing in the ruleset cannot increase by more than one.) The record-setting longest machines are logged as output, and these are the busy beaver candidates.[1] Brady describes this algorithm sequentially rather than using a pile, and draws an analogy to building a tree of machines.[2]
References
- ↑ 1.0 1.1 Something Something Programming, "Brady's Algorithm for Program Generation" (2022). Accessed 15 November 2024.
- ↑ A. H. Brady, "The Conjectured Highest Scoring Machines for Rado's Σ(k) for the Value k = 4". In IEEE Transactions on Electronic Computers, vol. EC-15, no. 5, pp. 802-803, Oct. 1966, doi: 10.1109/PGEC.1966.264572.