|
|
| (2 intermediate revisions by 2 users not shown) |
| Line 1: |
Line 1: |
| '''Brady's algorithm''' is an algorithm for finding long-running Turing machines. 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>
| | #REDIRECT [[Tree Normal Form]] |
| | |
| 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.<ref name="DrozdBrady" /> Brady describes this algorithm sequentially rather than using a pile, and draws an analogy to building a tree of machines.<ref>A. H. Brady, "[https://ieeexplore.ieee.org/document/4038890 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.</ref>
| |
| | |
| ==References==
| |
| <references/>
| |