next up previous contents
Next: Multiple tape TM Up: Ben's presentation Previous: instantaneous description of Turing

Two-way infinite tape

A two way infinite tape TM can move indefinitely in either direction. This can be shown to be equivalent to a one way infinite tape TM by the following argument: It is clear that two one-way infinite tape TMs can be used to simulate a two-way infinite tape. If these are lined up ``side by side'' and the two tapes are interleaved, then a single one-way infinite TM can be constructed which is equivalent.