A Linear-Size Block-Partition Fibonacci Encoding for Gödel Numbering

Read full text Summarise with VIRAT
Authors: Zoltán Sóstai
Cited by: 0
References: 4

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

We construct an encoding of finite strings over a fixed finite alphabet as natural numbers, based on a block partition of the Fibonacci sequence. Each position in the string selects one Fibonacci number from a dedicated block, with unused indices between blocks guaranteeing non-adjacency. The encoded number is the sum of the selected Fibonacci numbers, and Zeckendorf's theorem guarantees that this sum uniquely determines the selection. The encoding is injective, the string length is recoverable from the code, and the worst-case digit count of the encoded number grows as $Θ(m)$ for strings of length $m$, matching the information-theoretic lower bound up to a constant factor. We also prove that the natural right-nested use of Rosko's (2025) binary carryless pairing for sequence encoding has worst-case $Θ(2^m)$ digit growth, an exponential blowup that the block-partition construction avoids entirely.

Fields of Study & Subjects

Algorithms and Data Compression semigroups and automata theory Computability Logic AI Algorithms

Publication details

Journal / source
arXiv (Cornell University)
Publication date
26 March 2026
Language
EN
Document type
Preprint