Milan Rosko — Logician & Designer

Main site; index.html

On Carryless Pairing.

The algorithm bellow emerges solely from addition and bounded recursion. We demonstrate the core mechanism and the pairing function.

(i) First, a chosen set of Fibonacci terms is aggregated into a single numerical value.

(ii) In a second step, the selection itself is discarded, and only the resulting sum is returned to a Greedy Algorithm.

(iii) Finally, the original terms are recovered from the sum alone within a bounded number of steps.

This round-trip, from arbitrary input to canonical additive and back, utilizes Binet’s Formula, the Hurwitz Satz, and Zeckendorf’s Theorem to yield a stable, reversible, and fully bounded finitary encoding–decoding scheme.

(iv) The structure can be used to realize a constructive (hence injective) arithmetical pairing function:

$$ \pi_{\mathrm{CL}}^{\tau}(x,y) = \!\!\!\!\! \sum_{e\in Z(x)\subseteq\tau_x}\!\!\!\!\! F_{2e} \;+\;\!\!\!\!\! \sum_{j\in Z(y)\subseteq\tau_y}\!\!\!\!\! F_{\,B(x)+(2j-1)}. $$

Key Materials:

A Fibonacci-Based Gödel Numbering; arXiv
The Fractal Logic of 'Phi'-adic Recursion; arXiv

Secondary Literature:

Fibonacci and Lucas Numbers; DOI
Computability and Logic; DOI
On “Zeckendorf's Theorem”; Wikipedia

Step 1. We select (at least 2) integers that our javascript decomposes uniquely into non-consecutive Fibonacci summands.

Waiting for summands.

Step 2. We forget the supporting Fibonacci indices...

...and reconstruct them via a series of local search problems.

Waiting for command.

Step 3. We can use this correspondance to create an injective $\Delta_0$ pairing function. We select 2 arbitrary natural numbers.

$x \in \mathbb{N}:$

$y \in \mathbb{N}:$

Waiting for input.

Step 4. Inverse is given by bounded search in subpolynomial-time.

$n \in \mathbb{N}:$

Waiting for input.

Remark. The pairing $\pi_{\mathrm{CL}}^\tau$ is finitary and correctness relies on the uniqueness and stability of Zeckendorf decompositions (cf. 'Phi'-adic Logic) under exact order. The apperant division at the reversal is a $\mathcal{O}(\log n)$ search problem. However, if one realizes the procedure in a numerical model that is not an exact copy of $\{\,\mathbb{N},\, +,\, \le\,\}$ (with $\Delta I$) then the underlying invariants might not be preserved, e.g. IEEE-754 floating-point past $2^{53}$. This highlights a persistent key bias in contemporary computation.

Acknoledgment. Thanks are due to Albert Visser University of Utrecht for timely criticism and guidance.

Illustration: Recurrence relations are computationally expressive.