Brady's algorithm - Revision history

Sligocki: Redirect to TNF

2024-11-16T03:24:03Z

Redirect to TNF

← Older revision		Revision as of 03:24, 16 November 2024
Line 1:		Line 1:
	~~Main article:~~ [[Tree Normal Form]].		#REDIRECT [[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>

	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/>~~

Sligocki: Link to main TNF article

2024-11-15T15:32:03Z

Link to main TNF article

← Older revision		Revision as of 15:32, 15 November 2024
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>

C7X: Can't get busy beavers for free

2024-11-15T10:39:10Z

Can't get busy beavers for free

← Older revision		Revision as of 10:39, 15 November 2024
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>		'''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>

	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>		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>

C7X: Create page

2024-11-15T10:32:19Z

Create page

New page

'''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>

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/>