💻 computer science

On the Complexity of the Bi-infinite Post Correspondence Problem

This paper establishes that the bi-infinite Post Correspondence Problem ( $\mathbb{Z}$ PCP) is $\Sigma^0_2$ -complete within the arithmetical hierarchy by presenting a chain of reductions from Turing machine non-halting and proving the $\Pi^0_1$ -completeness of several related infinite and shifted variants.

Original authors: Olivier Finkel, Vesa Halava

Published 2026-06-10✓ Author reviewed ⓘ

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Olivier Finkel, Vesa Halava

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a game with two infinite tape recorders, Recorder G and Recorder H. You have a deck of cards, and each card has two sides: a "G-side" and an "H-side." Each side contains a string of letters (like "apple" or "banana").

The game is simple: You must pick a sequence of cards and stack them up.

If you read the G-sides from top to bottom, you get one long string of letters.
If you read the H-sides from top to bottom, you get another long string.

The goal is to find a sequence of cards where the G-string and the H-string are exactly the same. This is the classic Post Correspondence Problem (PCP). It's a famous puzzle in computer science that turns out to be impossible to solve for every possible deck of cards; there is no general algorithm that can tell you "Yes, a solution exists" or "No, it's impossible" for every case.

The New Twist: The "Bi-infinite" Game

This paper introduces a more complex version of the game called the Bi-infinite Post Correspondence Problem (ZPCP).

Instead of starting at the top of a stack and going down, imagine the stack of cards goes on forever in both directions: infinitely to the left and infinitely to the right.

You are looking for an infinite sequence of cards stretching from $-\infty$ to $+\infty$ .
The rule is the same: The infinite G-string must match the infinite H-string.

However, there's a catch. Because the string is infinite in both directions, the two strings don't have to start at the exact same "zero" point. They can be shifted. Imagine the H-string is just the G-string, but someone slid it slightly to the left or right. If you can slide one to match the other perfectly, you've solved the puzzle.

The Big Question: How Hard is This?

Computer scientists classify problems based on how "hard" they are to solve, using a ladder called the Arithmetical Hierarchy.

Level 1 (The Bottom Rungs): Problems that are "undecidable" but can be proven by finding a single example (like the original PCP).
Level 2 (The Next Rung): Problems that are even harder. To prove they have a solution, you might need to check an infinite number of possibilities in a specific way.

The Paper's Discovery:
The authors, Olivier Finkel and Vesa Halava, proved that the Bi-infinite game (ZPCP) sits strictly on Level 2 of this ladder.

It is harder than the standard PCP (Level 1).
It is not at the very top of the universe of problems; it has a specific, manageable complexity.
Crucially, they proved it is not in the "easy" parts of Level 1. It requires a more complex type of logic to determine if a solution exists.

How Did They Prove It? (The "Time Machine" Analogy)

To prove this, the authors built a bridge between this card game and the behavior of a Turing Machine (a theoretical computer that can simulate any algorithm).

The Time Machine: Imagine a Turing Machine as a robot reading a tape. If the robot runs forever without stopping, it's "non-terminating." If it stops, it "halts."
The Translation: The authors created a special set of rules (a "semi-Thue system") that acts like a translator. They showed that:
- If the robot runs forever, you can build an infinite card stack that solves the Bi-infinite game.
- If the robot stops, you cannot build such a stack.
The "Reversibility" Trick: The key to their proof was making the translator "reversible." Imagine a movie played backward. If you can rewind the movie perfectly to the beginning, the system is reversible.
- They proved that for their specific card game, if you find a solution, you can "rewind" the steps back to the very start of the Turing Machine's run.
- If the machine had stopped (halted), the "rewind" would hit a wall (a state where no previous move is possible).
- This "rewind" ability forced the problem into that specific Level 2 complexity.

Other Findings

Along the way, they solved a few side-puzzles:

Injective Morphisms: They proved that even if you restrict the game so that every card is unique and no two cards produce the same letter pattern (making the game "injective"), the problem remains unsolvable and just as hard.
Fixed Shifts: They looked at versions where the shift between the two strings is fixed to a specific number (e.g., "The H-string is always exactly 5 letters to the right"). They proved these are also incredibly hard (Level 1 complete).

The Bottom Line

This paper is a map of the "difficulty landscape" of infinite word puzzles.

The standard PCP is a "Level 1" monster.
The Bi-infinite PCP (ZPCP) is a "Level 2" monster. It is strictly harder than the original, but not infinitely harder.
The authors used a clever "rewind" mechanism (reversibility) to show exactly where this new puzzle sits on the ladder of computational difficulty.

In short: Solving the infinite, two-way version of this card game is a specific type of "hard" that is one step above the original, unsolvable version, and the authors have pinned down exactly where it lives in the mathematical universe.

Technical Summary: On the Complexity of the Bi-infinite Post Correspondence Problem

Problem Definition
The paper investigates the computational complexity of the Bi-infinite Post Correspondence Problem (ZPCP). While the classical Post Correspondence Problem (PCP) asks for a non-empty finite word $w$ such that $g(w) = h(w)$ for two given morphisms, and the Infinite PCP ( $\omega$ PCP) seeks an infinite word, the ZPCP asks whether there exists a bi-infinite word $\alpha = \dots a_{-1}a_0a_1 \dots$ such that $g(\alpha) = h(\alpha)$ . Crucially, equality for bi-infinite words is defined up to a shift: $g(\alpha) = h(\alpha)$ if there exists an integer shift $\tau$ such that the letter at position $i$ in $g(\alpha)$ equals the letter at position $i+\tau$ in $h(\alpha)$ .

Previous work established that ZPCP is undecidable and resides within the class $\Sigma^0_2$ of the arithmetical hierarchy, but it was not strictly located within the hierarchy (i.e., it was not known if it was $\Pi^0_1$ -complete or strictly at level 2). The primary goal of this work is to determine the exact position of ZPCP within the arithmetical hierarchy.

Methodology
The authors establish a chain of reductions starting from the non-halting problem of deterministic Turing machines (TMs) on empty input, proceeding through semi-Thue systems, and finally reaching variants of the PCP. The methodology relies on several key technical constructions:

Reversible Semi-Thue Systems: The authors construct a specific semi-Thue system $S_M$ from a given Turing machine $M$ . This system is designed to be both $\Theta$ -deterministic and $\Theta$ -reversible. The reversibility property is critical for the final reduction to ZPCP, as it allows the simulation of computation steps in both forward and backward directions.
Injective Morphisms and Bounded Delay: The paper constructs morphisms $g$ and $h$ that simulate the semi-Thue system. A significant technical contribution is proving that these morphisms are of "bounded delay 2," which implies they are injective. This allows the authors to extend undecidability results to the class of injective morphisms.
Shifted Variants: The authors define and analyze "s-shift" variants of the problems ( $\omega$ PCP $_s$ and ZPCP $_s$ ), where the equality condition is fixed to a specific shift $s$ . They prove these variants are $\Pi^0_1$ -complete.
Desynchronization and Overlining: To handle the bi-infinite nature of ZPCP and eliminate trivial solutions, the authors employ a complex alphabet construction involving overlined and non-overlined copies of symbols, along with specific "desynchronization" markers ( $d^4$ and $f^4$ ). This forces any solution to alternate between forward and backward configurations, effectively simulating the semi-Thue system's derivation in both directions.

Key Contributions and Results

Complexity of $\omega$ PCP: The authors prove that the Infinite PCP ( $\omega$ PCP) is undecidable even when restricted to injective morphisms (specifically, morphisms of bounded delay 2). Furthermore, they establish that this restricted version is $\Pi^0_1$ -complete.
Complexity of Shifted Problems: The paper proves that for any natural number $s$ , the $s$ -shift infinite PCP ( $\omega$ PCP $_s$ ) and the $s$ -shift bi-infinite PCP (ZPCP $_s$ ) are $\Pi^0_1$ -complete.
Complexity of ZPCP: The main result concerns the standard ZPCP. The authors prove that ZPCP is $\Pi^0_1$ -hard. Combined with the known result that ZPCP is in $\Sigma^0_2$ and not in $\Pi^0_1$ , and the new proof that it is not in $\Sigma^0_1$ (due to $\Pi^0_1$ -hardness), they conclude that:
$\text{ZPCP} \in \Sigma^0_2 \setminus (\Pi^0_1 \cup \Sigma^0_1)$
This places the problem strictly at the second level of the arithmetical hierarchy.
Semi-Thue Systems: The non-termination problem for $\Theta$ -deterministic and $\Theta$ -reversible semi-Thue systems is shown to be $\Pi^0_1$ -complete.

Significance and Claims
The paper claims to have sharpened the understanding of the complexity landscape for Post Correspondence Problem variants. Specifically:

It resolves the ambiguity regarding the ZPCP's position in the arithmetical hierarchy, confirming it is not $\Pi^0_1$ -complete but strictly resides at level 2.
It demonstrates that the undecidability and $\Pi^0_1$ -completeness of infinite variants persist even under strong constraints, such as injectivity and bounded delay, which are often used to simplify decision problems.
The authors note that while they have located ZPCP at level 2, the question of whether it is $\Sigma^0_2$ -complete remains open.

The work relies on a rigorous sequence of reductions from Turing machine non-halting to semi-Thue non-termination, and finally to the various PCP variants, utilizing the reversibility of the constructed systems to handle the bi-infinite constraints.

The New Twist: The "Bi-infinite" Game

The Big Question: How Hard is This?

How Did They Prove It? (The "Time Machine" Analogy)

Other Findings

The Bottom Line

More like this