Name
Abstract | ||
|---|---|---|
Consider Turing machines that read and write the symbols 1 and 0 on a one-dimensional tape that is infinite in both directions,
and halt when started on a tape containing all O's. Rado'sbusy beaver function ones(n) is the maximum number of 1's such a machine, withn states, may leave on its tape when it halts. The function ones(n) is noncomputable; in fact, it grows faster than any computable function.
Other functions with a similar nature can also be defined. The function time(n) is the maximum number of moves such a machine may make before halting. The function num(n) is the largest number of 1's such a machine may leave on its tape in the form of a single run; and the function space(n) is the maximum number of tape squares such a machine may scan before it halts.
This paper establishes a variety of bounds on these functions in terms of each other; for example, time(n) ≤ (2n − 1) × ones(3n + 3). In general, we compare the growth rates of such functions, and discuss the problem of characterizing their growth behavior
in a more precise way than that given by Rado. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1007/BF01192693 | Mathematical Systems Theory |
Keywords | Field | DocType |
Turing Machine,Computable Function,Bell System Technical Journal,Marked Zone,Blank Tape | Creatures,Discrete mathematics,Combinatorics,Busy beaver,Computer science,Turing machine,Multitape Turing machine,Beaver,Computable function | Journal |
Volume | Issue | ISSN |
29 | 4 | 0025-5661 |
Citations | PageRank | References |
2 | 0.46 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amir M Ben-Amram | 1 | 327 | 30.52 |
| Bryant A. Julstrom | 2 | 376 | 45.64 |
| Uri Zwick | 3 | 3586 | 257.02 |