Miller, David (2003) Solution to a generalization of the busy beaver problem. UNSPECIFIED. (Unpublished)

Preview

PDF WRAP-Solution-to-a-generalization-of-the-busy-beaver-problem-Miller-2003.pdf - Other - Requires a PDF viewer. Download (200Kb) | Preview

Request Changes to record.

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:	Date Event 9 January 2003 Completion
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:	Other

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads