Compose Turing-Machine Subroutines

Construct a decider from two machines and account for output length, time, and reusable space.

Problem

Machine $M_f$ maps $x$ to $f(x)$ in time $t_f(n)$ and work space $s_f(n)$. Machine $M_g$ decides whether $f(x)\in B$ in time $t_g(m)$ and space $s_g(m)$ on inputs of length $m$. Construct a multitape decider for $A=\{x:f(x)\in B\}$ and derive honest time and space bounds. State the assumptions needed when the intermediate output tape is reused.

Prerequisites

Know the unit definitions and how resources are measured against encoded input length. Distinguish a conditional theorem, a reduction, and an algorithm.

Hint 1

A machine cannot write more than a constant number of symbols per step.

Hint 2

Let $\ell(n)$ be a separate bound on $|f(x)|$ before composing resource functions.

Hint 3

For space, distinguish the read-only original input, stored intermediate string, and reusable work tapes.

Full solution

Use separate tapes for the original input, the intermediate value, and scratch work. First simulate $M_f$ on $x$ and leave $y=f(x)$ on the intermediate tape. Reset the scratch tapes and simulate $M_g$ with $y$ as its input. Accept exactly when that simulation accepts. Because both component machines halt, the composition halts, and its correctness is immediate:

Let $\ell(n)=\max_{|x|=n}|f(x)|$. In every conventional TM model with constant-size alphabet, writing one output symbol costs at least one step up to a constant, so $\ell(n)=O(t_f(n))$. It is nevertheless clearer to keep $\ell$ explicit. On a multitape machine the direct bound is

The last term covers positioning or copying if $M_g$ expects its input in a standard place; it is absorbed by the other terms in usual models. Thus one may report $O(t_f(n)+t_g(\ell(n)))$, and then substitute $\ell(n)=O(t_f(n))$ when the resource functions are monotone. If both times and $\ell$ are polynomial, their composition is polynomial.

For space, the intermediate string physically occupies $\ell(n)$ cells. During the first phase the machine uses $s_f(n)$ scratch cells in addition to output. Those scratch tapes can be erased or simply reused in phase two; space is maximum simultaneous occupancy, not the sum over time. During phase two the occupancy is the stored $y$ plus $s_g(|y|)$ scratch cells. Therefore

If the convention charges the output tape to $M_f$'s space, then $\ell(n)\le s_f(n)$ and the formula simplifies to $O(\max\{s_f(n),s_g(\ell(n))\})$. If output space is excluded, that simplification is invalid unless $M_g$ can consume a streamed representation.

On a single-tape TM, simulating the multitape construction can introduce a polynomial time overhead, but it does not invalidate a polynomial-time conclusion. The exact formula depends on the selected machine model, which is why the construction and accounting convention must be stated. The robust result is closure under composition with explicit control of intermediate length.

Checkpoints

Check both logical directions, halting of every relevant branch, and that output length and construction time are polynomial in the encoded input length.

Common mistakes

• Substituting $t_g(n)$ instead of $t_g(|f(x)|)$.
• Adding phase spaces rather than taking their maximum.
• Omitting the stored intermediate string when output space is free.

Sources and verification

• Merged summary, pp. 14-20
• 2026 transcript 2
• Sipser 3e, secs. 3.2 and 7.1
• Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Provenance and confidence

The exercise is an original synthesis. Confidence reflects verification of the mathematical claim against the textbook sources listed above; course sources are used only where direct coverage is identified.