The Library
Solution to a generalization of the busy beaver problem
Tools
Miller, David (2003) Solution to a generalization of the busy beaver problem. UNSPECIFIED. (Unpublished)
|
PDF
WRAP-Solution-to-a-generalization-of-the-busy-beaver-problem-Miller-2003.pdf - Other - Requires a PDF viewer. Download (200Kb) | Preview |
Abstract
Let ϕ be a fixed numerical function. If the k-state Turing machine M with input string ϕ(k) (that is, started in its initial state scanning the leftmost 1 of a single string of ϕ(k) 1s on an otherwise blank tape) produces the output string m (that is, halts in its halting state scanning the leftmost 1 of a single string of m 1s on an otherwise blank tape), we shall say that the ϕ-fecundity of M is m. If M halts in any other position or state, or fails to halt, its ϕ-fecundity is 0.
Since there are only finitely many k-state Turing machines, there is one that is at least as ϕ-fecund as any other. Let fϕ(k) be the ϕ-fecundity of the most ϕ-fecund k-state machine.
Item Type: | Scholarly Text | ||||
---|---|---|---|---|---|
Subjects: | B Philosophy. Psychology. Religion > B Philosophy (General) Q Science > QA Mathematics |
||||
Divisions: | Faculty of Social Sciences > Philosophy | ||||
Library of Congress Subject Headings (LCSH): | Computer science, Turing machines, Computable functions | ||||
Official Date: | 9 January 2003 | ||||
Dates: |
|
||||
Number of Pages: | 2 | ||||
Status: | Not Peer Reviewed | ||||
Publication Status: | Unpublished | ||||
Reuse Statement (publisher, data, author rights): | This paper belongs to the author. Please note that unpublished papers are subject to correction, revision, and modernization, without explicit notice. No version, current or obsolete, of any of these papers and lectures should be cited in print without the author's written permission. | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Copyright Holders: | D. W. Miller | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year