Name
Abstract | ||
|---|---|---|
The following problem in the computation of partial recursive functionals is considered: Minimizing the length of initial segments of input functions containing all function values requested by a machine computing a partial recursive functional. A recursive functional F is constructed such that any algorithm for F has unbounded redundancy, i.e. it requests function values on inputs unboundedly larger than those on which the output of F depends. However, for any recursive functional F such that the length of the segment on which F depends is itself a recursive functional, a non-redundant machine for F can be effectively constructed. Also considered are machines on 0-1 sequences for which it is shown that a machine realizing a given level of significance in a universal test of randomness must have unbounded redundancy. |
Year | DOI | Venue |
|---|---|---|
1983 | 10.1016/0304-3975(83)90036-1 | THEORETICAL COMPUTER SCIENCE |
DocType | Volume | Issue |
Journal | 23 | 3 |
ISSN | Citations | PageRank |
0304-3975 | 1 | 0.59 |
References | Authors | |
5 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dan Gordon | 1 | 210 | 21.44 |
| Eliahu Shamir | 2 | 28 | 12.96 |