HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Do Turing machines have memory registers?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
registersmemorymachinesturinghave

Problem

I am working on chapter one of the textbook Computational Complexity: a modern approach by Arora, S., & Barak, B. They begin by defining a turing machine (TM) and then prove equivalence between variations of TMs. They make the following claim.

Claim 1.6 Define a single-tape Turing machine to be a TM that has only one read-write
tape, that is used as input, work, and output tape. For every $f : \{0, 1\}^∗ → \{0, 1\}$ and time-constructible $T : \mathbb{N} → \mathbb{N}$, if $f$ is computable in time $T(n)$ by a TM $M$ using $k$ tapes, then it is computable in time $5kT(n)^2$ by a single-tape TM $M'$.

I understand how to "compress" the $k$ tapes $M$ has into $M'$ single-tape. However, when they describe how to simulate one step of $M$ on $M'$ I get confused. More specifically, they describe it as follows:

  • First it sweeps the tape in the left-to-right direction and records to its register the $k$ symbols that are marked by “$ˆ$”.



  • Then $M'$ uses $M$’s transition function to determine the new state,


symbols, and head movements and sweeps the tape back in the right-to-left direction
to update the encoding accordingly.

How can a TM have a register? I thought it was a finite automata with a tape and head only. They also mention TMs having a state register.

How much data can a register hold? In the proof, they imply the register can hold $k$ symbols. Are the registers typically stored on some separate tape or somewhere else?

Solution

A TM does not have a register, but a register has a fixed capacity.

Any amount of fixed capacity storage can be emulated by multiplying your states: your new states become $ \langle q, v \rangle$ where $q$ is an old state and $v$ a value stored in the register.

So a "TM with a register" is not a TM, but trivially equivalent to a normal TM, and I would expect your course notes to have this spelled out at some point.

Context

StackExchange Computer Science Q#144316, answer score: 19

Revisions (0)

No revisions yet.