Motivation
A Post correspondence instance consists of pairs of finite words. The question is whether a nonempty sequence of pairs can be concatenated so that its top and bottom strings agree. This simple equality problem can encode an entire Turing-machine computation: one side lists configurations, while the other lists their successors.
We prove the reduction in two stages. A modified version first requires a designated tile to be used first. Its initial mismatch supplies the first machine configuration. A marker construction then removes that requirement and produces an ordinary instance whose tile words are all nonempty.
Problems and machine model
Definition 5.4.1
(Post correspondence and modified correspondence)
A PCP tile is a pair of nonempty words over a finite alphabet. A solution is a nonempty sequence of indices such that . Tiles may be reused. Modified PCP (MPCP) adds the condition .
Definition 5.4.2
(Normalized machine and configuration)
We reduce from deterministic Turing-machine acceptance, an undecidable problem established in the computability chapter. Use the standard equivalent model with a semi-infinite tape, a left boundary the head never crosses, a finite tape alphabet containing blank, and distinct accepting and rejecting halting states. The accepting state has no ordinary transition. State symbols and tape symbols are taken from disjoint finite alphabets, and the separator and closing markers are fresh. A configuration is a finite nonempty tape word with exactly one state symbol immediately before the scanned tape symbol. Trailing blanks can be omitted except when needed to represent the scanned cell.
Theorem 5.4.3
(Undecidability of modified correspondence)
There is a computable transformation from a machine and input to an MPCP instance with nonempty tile words such that the instance has a solution exactly when the machine accepts the input.
Theorem 5.4.4
(Undecidability of PCP with nonempty tiles)
MPCP with nonempty tile words reduces effectively to ordinary PCP with nonempty tile words. Consequently ordinary PCP is undecidable even under this nonemptiness convention.
The semi-infinite protected-boundary machine model is a standard equivalent Turing model; this chapter uses that model-equivalence fact as a prerequisite. Every state, tape symbol and fresh marker is encoded in the finite correspondence alphabet. Both theorems are proved below: first the tiles are built, then the two directions of the correctness argument are given, and finally the marker transformation is analyzed.
Tiles for computation histories
Fix a machine and input . Let be its initial configuration, including a blank if the input is empty. Introduce fresh separator and closing marker that do not occur in tape or state alphabets. The designated first tile is
Its bottom string is ahead of its top string by one configuration and a separator. Add copy tiles for every tape symbol and the separator tile . Do not add copy tiles for state symbols.
For a transition that, in state scanning , writes , enters state and moves right, add . Also add a right-boundary version , where denotes the blank tape symbol. The latter explicitly creates a scanned blank when the head moves beyond the represented right end.
For a transition that writes , enters and moves left, add for every tape symbol . This moves the state marker to the preceding cell while preserving that cell's symbol. The protected left boundary convention ensures that a legal transition never needs an unrepresented cell to the left.
For the accepting state and each tape symbol , add cleanup tiles and . Finally add the closing tile
All tile components are nonempty. Cleanup tiles are not machine steps; they are allowed only after the accepting state appears and gradually remove tape symbols around it.
From an accepting run to a solution
Proof
(An accepting run yields a solution)
After the forced first tile, the top is and the bottom is . Suppose the top has caught up through the separator before a configuration , while the bottom has the additional suffix . Use copy tiles for tape symbols away from the state marker and one appropriate transition tile at the marker. The top then appends , while the bottom appends its successor configuration and separator.
For a right move at the represented end, use the boundary tile to append a blank after the new state. For a left move, the tile containing the preceding tape symbol moves the state marker to the correct place. Repeating this procedure follows every step of a finite accepting computation.
Once appears, use cleanup tiles on successive configuration copies to remove one adjacent tape symbol at a time. Eventually the extra configuration is just . The closing tile makes the top append and the bottom append , so the two accumulated strings become equal.
Why a solution yields an accepting run
Proof
(A solution yields an accepting run)
Before any closing tile, the bottom contains exactly one more separator than the top. This is true after the first tile, and every copy, transition and cleanup tile contains the same number of separators on its two sides. Therefore equality is impossible without a closing tile.
The marker occurs only in closing tiles. In an equal pair of concatenations, the first occurrences of this marker must align. Removing any tiles after the first closing tile leaves a solution ending at that tile. Before it, equality forces the top to reproduce the bottom's initial configuration block and each successive block in order.
A copied block contains exactly one state symbol. Since state symbols have no copy tiles, a sweep past that symbol must use a machine-transition tile or an accepting cleanup tile. The surrounding tape symbols and separators are copied unchanged. Thus, before acceptance, each complete next block is a legal successor configuration. A right move at the end can explicitly add a blank; an omitted trailing blank only yields an unprocessable state immediately before the separator unless that state is accepting, in which case the machine has already accepted. Left-boundary moves are excluded by the normalized machine model.
Cleanup tiles can be used only after the state symbol has appeared. They preserve that state and remove adjacent tape symbols. The closing tile can match only when the outstanding configuration has been reduced to . Therefore any solution reaches the accepting state through a legal computation. A rejecting halt or a nonaccepting malformed boundary cannot be closed.
The construction has finitely many tiles and is computable from : it enumerates the finite transition table and tape alphabet and writes a finite word for each rule. This proves MPCP undecidable: a decider for these instances would decide machine acceptance.
Proof X-ray
Where each design choice is used
Three design choices carry the argument, and each is used at one identifiable place. First, every tile except the first and the closing tile has the same number of separators on its two sides, so the bottom always holds exactly one more separator than the top, and no solution can avoid the closing tile. Second, and least obviously, there are no copy tiles for state symbols. This turns an equality of strings, which looks static, into the rule that each configuration block is rewritten at its unique state symbol, so consecutive blocks are successor configurations. With copy tiles for state symbols, a block could pass its state symbol without any transition, and the next block would no longer be a legal successor. Third, the marker occurs only in the closing tile, which needs the outstanding block to be exactly . Cleanup tiles exist only for , so a rejecting or nonterminating computation offers no way to finish.
Remove the forced-first condition
Definition 5.4.5
(Marker maps and the transformed instance)
Let an MPCP instance have nonempty tiles over alphabet , with tile one designated. Choose fresh markers , and outside . For a word , define
Both maps preserve concatenation, and . Create ordinary PCP tiles:
- a special start tile ;
- for every original tile , an ordinary tile ;
- an end tile .
Every component is nonempty because original tile words are nonempty and the new marker words are nonempty.
Proof
(Solutions correspond under the marker transformation)
If the MPCP instance has solution with common concatenation , use the special start, ordinary tiles , then the end tile. The top is and the bottom is , which are equal.
Conversely, any ordinary PCP solution must start with the special start tile: an ordinary tile begins with on top and an original alphabet symbol on bottom, while the end tile begins with and ; only the special tile begins with the same fresh marker on both sides. Before the first end tile, a second special start cannot occur in an equal concatenation. Every ordinary tile adds an even length to each side, so after the start tile the top prefix has odd length () and the bottom prefix has even length (). A second would therefore sit at positions of opposite parity in the two strings, and the markers could not align.
An equal solution must contain the end tile: without it the whole top has odd length and the whole bottom has even length, by the same count, so they cannot be equal. At the first , equality forces
where are the top and bottom concatenations of tile one followed by the selected ordinary indices. Since and is injective, . The corresponding original index sequence starts with tile one and solves the MPCP instance. This completes the reduction to ordinary PCP.
Counterexample mode
Dropping the first-tile condition changes the answer
A tempting shortcut is to ask the ordinary question about the same tiles and expect the same answer as for MPCP. Take the alphabet and the tiles and , with tile designated. A sequence starting with tile has a top beginning with and a bottom beginning with , so the two sides never agree: the MPCP instance has no solution. As an ordinary PCP instance, however, the one-tile sequence is a solution, since . The answers differ, so the marker transformation is needed. It produces the start tile , the ordinary tiles and , and the end tile . Every solution must begin with the start tile, whose top and bottom differ in the third symbol, so the transformed instance has no solution, in agreement with the MPCP instance.
Worked examples
Worked example 5.4.6
(A single machine transition)
If has a right-moving transition that reads in state , writes and enters , the tile replaces the local configuration segment by . The state marker now precedes the symbol to the right, provided one is represented.
Worked example 5.4.7
(A left-moving transition)
For a left move that reads , writes and enters , a preceding tape symbol gives tile . The new state marker is immediately before , the newly scanned symbol.
Worked example 5.4.8
(Marker identity)
For , and . Thus . The final marker aligns the two staggered encodings.
Worked example 5.4.9
(A one-tile MPCP solution)
If the designated tile is , it alone solves the MPCP instance. The transformed sequence uses the special start tile and then the end tile. Its top and bottom both become .
Worked example 5.4.10
(A complete accepting run)
Let the machine have one transition: in state reading , write , enter and move right. The input is , so and the tape alphabet is . The tiles used, written (top, bottom), are:
- the first tile ;
- the right-boundary transition tile , needed because the head moves off the represented right end, so a blank must be written explicitly;
- the copy tiles and ;
- the cleanup tiles and ;
- the closing tile .
Using them in the order first tile, boundary tile, , , , , , closing tile, both the top and the bottom spell
The bottom writes the configurations , , and in turn, the top catches up one configuration behind, and the closing tile supplies the final against the lone .
Concept lensAlgorithmic
A solution as a walk through overhangs
Call the part by which the longer of two partial concatenations extends beyond the shorter their overhang. A tile can be appended exactly when the strings stay consistent, meaning that one remains a prefix of the other, and it produces a new overhang. A solution is then a walk of at least one tile that starts and ends at the empty overhang. In the complete accepting run above, the overhang after the first tile is , after the boundary tile it is , and after the closing tile it is empty.
Common mistakes
Common mistake
(Expecting each tile to balance by itself)
The top and bottom of a tile need not have equal length, and equality is required only after concatenating an entire nonempty sequence. The computation construction deliberately keeps the bottom ahead by one configuration until the closing tile.
Common mistake
(Copying a state symbol)
Copying state symbols freely would allow a configuration to pass through a sweep without applying a transition. State symbols are handled only by transition or accepting cleanup tiles, forcing the intended computation structure.
Summary
MPCP tiles encode a configuration on one side and its successor on the other; an accepting state enables cleanup and closure. A staggered-marker transformation forces the designated first tile in an ordinary PCP instance and preserves nonempty tile words. Together the reductions prove PCP undecidable from Turing-machine acceptance.
Exercises
Quick check
(What does the forced first tile place on the two sides of the MPCP construction?)
Compare what the top and the bottom of that tile contain.
Solution · Answer
The top is and the bottom is , so the bottom is ahead by the initial configuration and one separator.
Quick check
(Why are there no copy tiles for machine state symbols?)
Ask what a sweep over a configuration would be allowed to do at the state symbol.
Solution · Answer
Without copy tiles for state symbols, reproducing a configuration block forces a transition tile at its unique state symbol, or an accepting cleanup tile after acceptance. This prevents a nonaccepting configuration from being copied unchanged and passed off as the next step.
Quick check
(Verify that .)
Write out and first.
Solution · Answer
and , so and . Both sides are equal.
Quick check
(Why must a solution of the transformed ordinary instance use the special start tile first?)
Compare the first symbols on the top and bottom of each kind of tile.
Solution · Answer
An ordinary tile begins with on top and an original symbol on the bottom, and the end tile begins with on top and on the bottom. Only the special start tile begins with the same fresh symbol on both sides, so only it can start an equal pair of concatenations.