Data structures for distributed counting

摘要

The main tool to obtain a tight deterministic time hierarchy for Turing machines is a new data structure for fast distributed counting. The data structure representes an integer in a redundant manner, and it is able to accept orders from many places to increase or decrease the integer value by 1. With the help of the new data structure, it is shown that the slightest increase in computation time allows k-tape Turing machines (for fixed k ⩾ 2) to solve new problems.