Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 231-243 |
Number of pages | 13 |
Journal | Journal of Computer and System Sciences |
Volume | 28 |
Issue number | 2 |
DOIs | |
State | Published - Apr 1984 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics