[37] A log-cost random access machine (log-cost RAM) has the following components: an infinite number of registers each capable of holding an integer and a finite sequence of labeled instructions including ‘output,’ ‘branch,’ ‘load/store,’ ‘add/subtract between two registers.’

The time cost for execution of each instruction is the sum of the lengths of the integers involved.

(a) Every tree machine with several tree tapes, each with one head, of time complexity t can be simulated online by a log-cost RAM of time complexity O(tlog t/ log log t). Show that this is optimal.

(b) Show that online simulating a linear-time log-cost RAM by a ddimensional Turing machine requires Ω(n1+1/d/ log n(log log n)1+1/d).

Comments. Source: [D.R. Luginbuhl, Ph.D. thesis, 1990, Univ. Illinois, Urbana-Champaign; M.C. Loui and D.R. Luginbuhl, SIAM J. Comput.

21:5(1992), 959–971; Math. Systems Theory, 25:4(1992), 293–308].