On time hierarchies

摘要

For fixed k ⩾ 2 we tighten the time hierarchy for k-tape Turing machines. Also for fixed k ⩾ 2 we exhibit infinite hierarchies of languages recognizable by k-tape machines with machines with increasing amount of time on the same amount of space.