patternModerate
Do Turing machines have memory registers?
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:
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?
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.
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.