🌀 The Rondanini Convergence Problem

Undecidable Formal Named Formulation

Informal Description

Each positive integer n secretly encodes a computer program P_n.

We let two processes unfold in parallel:

1. We run the program P_n on input n.
2. We repeatedly apply the Collatz rule to n:

n ↦
3n + 1   if n is odd
n / 2     if n is even

Does this combined process eventually output 1?

Formal Definition

Fix a universal programming language and a standard encoding of programs by natural numbers.

For each positive integer n:

• Let P_n be the program whose encoding is n.
• Execute P_n on input n.
• Simultaneously iterate the Collatz map on n.

Define the function R(n) as follows:

If P_n(n) halts → R(n) = 1
If P_n(n) never halts and Collatz(n) reaches 1 → R(n) = 0
If P_n(n) never halts and Collatz(n) never reaches 1 → undefined (diverges)

The Decision Problem

For a given integer n, determine whether R(n) = 1.

Theorem (Undecidability)

The Rondanini Convergence Problem is undecidable.

There exists no algorithm that correctly determines R(n) for all positive integers n.

Proof Sketch

The definition embeds the Halting Problem:

Suppose Collatz always reaches 1 (widely believed).
Then R(n) = 1 iff P_n(n) halts, and R(n) = 0 otherwise.
Deciding R would decide the Halting Problem.

Even if Collatz does not always reach 1,
R(n) = 1 still requires knowing whether P_n(n) halts.
No algorithm can determine this for all n.

∴ The Rondanini Convergence Problem is undecidable.  ∎

Interpretation

This problem mixes:

• A simple arithmetic dynamical system (Collatz)
• A computational process (program execution)

Although Collatz itself is unproven but believed to converge, the undecidability here does not depend on the Collatz conjecture being true or false. The impossibility arises from embedding universal computation into the definition.

Status

Type: Undecidable (by reduction from the Halting Problem)
Nature: Artificial but mathematically rigorous
General Solution: Impossible