Data structures for distributed counting (Q794431)

A new type of data structures for a redundant representation of integers is presented. Contrary to binary representation, not only the right end, but every second position in the representation is able to accept orders to increase or decrease the integer value by 1. The new data structures are applied to produce a tight hierarchy for k-tape Turing machines. For every \(k\geq 2\) and every function \(t_ 2\) time-constructable on a k-tape Turing machine, there is a language accepted by such a machine in time \(t_ 2\), but not accepted in any time \(t_ 1\) with \(t_ 1(n)=o(t_ 2(n))\).