Multi-track Turing machine

Last updated

A Multitrack Turing machine is a specific type of multi-tape Turing machine.

Contents

In a standard n-tape Turing machine, n heads move independently along n tracks. In an n-track Turing machine, one head reads and writes on all tracks simultaneously. A tape position in an n-track Turing Machine contains n symbols from the tape alphabet. It is equivalent to the standard Turing machine and therefore accepts precisely the recursively enumerable languages.

Formal definition

A multitrack Turing machine with -tapes can be formally defined as a 6-tuple, where

Sometimes also denoted as , where .

A non-deterministic variant can be defined by replacing the transition function by a transition relation.

Proof of equivalency to standard Turing machine

This will prove that a two-track Turing machine is equivalent to a standard Turing machine. This can be generalized to a n-track Turing machine. Let L be a recursively enumerable language. Let be standard Turing machine that accepts L. Let M' is a two-track Turing machine. To prove it must be shown that and .

If the second track is ignored then M and M' are clearly equivalent.

The tape alphabet of a one-track Turing machine equivalent to a two-track Turing machine consists of an ordered pair. The input symbol a of a Turing machine M' can be identified as an ordered pair of Turing machine M. The one-track Turing machine is:

with the transition function

This machine also accepts L.

References