2 papers
cs.CC2001
Two heads are better than two tapes
Tao Jiang, Joel Seiferas, Paul Vitanyi
We show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set {x2x'| x \in {0,1}^* and x' is a prefix of x} in real time, although it can do so…
cs.CC2001
Counting is Easy
Joel Seiferas, Paul Vitanyi
For any fixed , a remarkably simple single-tape Turing machine can simulate independent counters in real time. Informally, a counter is a storage unit that maintains a singl…