The P System and the Grammatical Origin of Prime Numbers

Introduction: Hypothesis of a Dynamic Ontology for Numbers

Number Theory has traditionally investigated the properties of prime numbers within a framework that assumes the sequence of natural numbers as a static, pre-existing, and linearly ordered entity (1, 2, 3, ...). From this perspective, prime numbers appear as special elements with a complex distribution, whose pattern has been the subject of study for centuries. The starting point of this research is an alternative hypothesis that does not question the properties observed within this framework, but the static nature of the framework itself.

This research is based on an alternative ontological hypothesis: prime numbers constitute the only fundamental numerical entities, which I define in this work as Promoters, and composite numbers are structural effects that emerge from the combinatorial interaction of the Promoters themselves. This perspective suggests that the nature of numbers is intrinsically dynamic. They do not "exist" in a fixed sequence, but "emerge" according to an order of constructive necessity.

A direct consequence of this hypothesis is that the linear order with which we are accustomed to counting (n → n+1) represents one of the possible readings of this structure, but not necessarily the fundamental order of its generation. I hypothesize the existence of a deterministic "Order of Emergence", dictated by the interactions between Promoters, which describes the chronology with which each numerical structure – both prime and composite – is generated. This process sometimes shows a non-linear characteristic, where the effect (the generation of a composite like 4) precedes the full certification of its apparent cause (the emergence of prime 3 as a structural "gap").

To investigate this dynamic vision, it was necessary to develop a formal language capable of describing not only quantities, but relationships, genealogies, and internal architectures of numbers. For this reason, I developed the P System, a theoretical framework and symbolic language whose purpose is to make explicit the grammatical rules that govern the generation of numbers.

In the following sections, I will describe the empirical methodology that led me to this hypothesis, the formalization of the P System as a language, the definition of a "Selective Propagation" algorithm that follows from it, and its experimental validation through a high-performance implementation. The goal is not to refute existing models, but to offer a complementary perspective that focuses on the generative nature of numbers, rather than on the properties of their final state.

Research Methodology: From Empirical Investigation to Initial Formalization

Once the hypothesis of a dynamic and generative nature of numbers was postulated, the next necessary step in the research was to develop an empirical model to analyze the structural relationships between Promoters and the composites they generate. The objective was to make observable what I hypothesized to be a complex structure of generative dependencies, where each promoter gives rise to a "family" of composites that intersects and interacts with others.

For this purpose, I built a relational map, called the PTM Table (Prime Transitional Model). This tool was not conceived as a computational algorithm, but as an observation environment. For each natural number n, the table records a set of qualitative and not just quantitative attributes:

• Its prime factorization, which represents its fundamental structure.
• The genealogical affiliation (χ_k), which indicates the primary promoter from which it descends.
• A vector of topological metrics, i.e., an early version of the Morphogenetic Signature, to classify the complexity of its internal architecture.

The goal of this mapping was to make explicit the connections, overlaps, and "zones of influence" of each promoter, which remain implicit in traditional arithmetic. The analysis of this map allowed the observed dynamics to be formalized in an initial computational model.

The First Model: The Transitional Sieve (PTM)

The Prime Transitional Model was the first attempt to translate the generative logic observed in the map into code. Its architecture is that of a sieve, but its operating principle is aligned with the constructivist hypothesis.

Its logic is as follows:

1. A set of base Promoters is identified (the primes up to √N).
2. All "transitions" that these promoters generate within a given interval are calculated, i.e., all their products.
3. These transitions are used to "mark" the positions of composite numbers.
4. Numbers that remain unmarked are, by definition, the new promoters that emerged in that interval.

This algorithm, despite being an arithmetic implementation, represented a crucial step, validating the effectiveness of the generative approach. However, it also made evident the need for a more powerful language, capable of operating directly on structures and genealogies rather than on their numerical values. This awareness marked the beginning of the development of the P System as a formal language.

The Birth of Symbolic Language: Structure, Quality, and Measure

The analysis of the PTM relational map, while effective, still operated with numerical quantities. To investigate the pure structure underlying these quantities, the need for a new language emerged. A language that would not describe "how much", but "how" and "from what" a structure is formed. The objective of my research became to represent the interaction and genealogy of numbers, not their magnitude. From this need, symbols, operators, and a new alphabet for a new grammar are born.

Symbols (π_k) and Operators (⊗, ↑): The Alphabet and Syntax

The first step was to define the basic elements of this language.

Symbols (π_k): I introduced the symbol π to represent a Promoter. π₁ is not an alias for the number "2", but is the first primary promoter of the system, the origin of the first genealogical family. π₂ is the second, π₃ the third, and so on. They are the fundamental and irreducible elements of the language.

Operators (⊗, ↑): To describe interactions, I defined two fundamental grammatical operators, the "verbs" of the language:

• The Composition operator (⊗) describes the interaction between two or more distinct genealogical families. The structure of number 6, for example, is represented as ⦅π₁ ⊗ π₂⦆.
• The Self-Interaction operator (↑) describes a promoter interacting with itself or with its own family. The structure of 4 is ⦅π₁↑2⦆.

Through these elements, each natural number can be uniquely described not as a quantity, but as a grammatical expression that reveals its constructive history.

The Morphogenetic Signature (φ): The Metric of Structure

Once numbers were translated into symbolic structures, a method was needed to measure and classify them objectively, without resorting to their numerical value. For this, I developed the Morphogenetic Signature, a function φ that maps each structure to a vector of 5 parameters, describing its qualitative identity:

• δ (Deltamorphism): The structural complexity, given by the total number of π symbols in its expression.
• ν (Variety): The number of unique promoters that compose it.
• φ (Frequency): The maximum occurrence of a single promoter.
• ρ (Ramification): A measure of the complexity of its genealogy (ρ = φ - ν).
• ω (Orbit): The number of genealogical families (χ_k) involved in its creation.

This signature makes explicit deep structural differences that arithmetic does not highlight. Take for example the numbers 6 and 8:

• 6, symbol ⦅π₁ ⊗ π₂⦆, has signature (δ=2, ν=2, φ=1, ρ=-1, ω=2). It is a "flat" structure (δ=2) but "wide" (ν=2), born from the interaction of two distinct families.
• 8, symbol ⦅π₁↑3⦆, has signature (δ=3, ν=1, φ=3, ρ=2, ω=1). It is a "deep" structure (δ=3) but "narrow" (ν=1), generated entirely by the first family.

Although numerically close, the P System describes them as genealogically and qualitatively different creatures. 6 is structurally more akin to 15 (⦅π₂ ⊗ π₃⦆), while 8 is akin to 27 (⦅π₂↑3⦆).

The Second Model and Its Empirical Validation

The union of these concepts gave birth to the second computational model of my research: a Purely Grammatical Generator. The purpose of this model was to demonstrate that it was possible to construct the sequence of numerical structures and their signatures by operating in a purely abstract world, without the need to pre-assign numerical values to the symbols π_k.

This program simulated a symbolic operating environment capable of generating a sequence, calculating its signature, and identifying "gaps" to promote new π_k based solely on internal construction rules.

To validate the correctness of this approach, the model's output was compared with real numerical data. The following table shows an excerpt of the results, demonstrating that the count of grammatical promoters generated by the model perfectly coincides with the prime counting function π(x).

The success and correctness of this grammatical model demonstrated that the symbolic approach was not only valid, but also complete. However, its implementation was not yet computationally optimized for extreme numerical scales. This paved the way for the final phase of the research: the formalization of an algorithm that would translate this theoretical purity into computational performance.

The Formalization of the P System: Fundamental Postulates and Theorems

To transform the computational model into a complete theory, I defined the logical architecture of the P System through a system of rigorous postulates and theorems. This formalization constitutes the theoretical core of my research.

Fundamental Postulates

The P System is based on a series of postulates that define its nature and operational boundaries. The most important are:

Key Structural Theorems

From these postulates derive theorems that guarantee the robustness of the system.

This theoretical scaffolding provides the rigorous basis for the final algorithm, which is nothing more than the most efficient computational implementation of the generative dynamics described by this grammar.

The Genealogical Engine: Formalization of Dynamic Competition

The postulates and theorems described in the previous section provide the axiomatic foundations of the P System. Now we can build on these foundations to rigorously define the mathematical engine that governs the emergence process of numbers. While the Selective Genealogical Algorithm (SGA), which will be presented later, is the computational implementation of this process, here we formalize its abstract logic.

To do this, we define the P System as a generative state automaton, a formal system that deterministically evolves from one state to the next.

Definition of the Formal P System

The P System can be described as a quintuple:

Each component has a precise role:

• Σ (The Alphabet of Structures): It is the (infinite) set of all well-formed symbolic expressions that the system can generate. It includes both the irreducible primary promoters (π₁, π₂, …) and all possible composite structures generated from them through grammatical operators (e.g., ⦅π₁↑2⦆, ⦅π₁ ⊗ π₂⦆, etc.).
• Γ (The Set of States): It is the set of all possible states that the system can assume. A state S ∈ Γ is defined by the pair S = (N, C), where N is the last natural number whose structure has been determined and C is the set of "pending tasks", which represents the frontier of future interactions.
• Φ (The Signature Function): It is the Morphogenetic Signature function, which maps each structure σ ∈ Σ to a qualitative vector of 5 parameters.
  Φ: Σ → ℤ⁵
  This function acts as a tool to analyze and classify the internal complexity of each structure generated by the system.
• S₀ (The Initial State): It is the axiomatic origin of the generative process. The initial state is defined as S₀ = (N=1, C={(4, π₁)}), where the first promoter π₁ has as its first and only pending task the generation of its self-interaction, 2×2=4.
• T (The Transition Function): It is the heart of the system, the engine that makes it evolve from state Sₙ to state Sₙ₊₁. This function mathematically embodies the concept of "genealogical competition".

The Transition Function T and Genealogical Competition

The function T: Γ → Γ describes a single step of the generative process. Given a starting state Sₙ = (Nₙ, Cₙ), the transition to the next state Sₙ₊₁ occurs through the following deterministic steps:

1. Winner Selection: The system analyzes the set of pending tasks Cₙ and selects the "winning" pair (k*, p*) that satisfies the minimum construction condition. The winner is the task whose product k is the smallest among all tasks in the queue, thus representing the most imminent composition event.
   k* = min{kᵢ | (kᵢ, pᵢ) ∈ Cₙ}
2. Gap Identification and Emergence of New Promoters: The system compares the value of the "winning" composite k* with the last analyzed number Nₙ. If k* > Nₙ + 1, a constructive gap has occurred. All integers in the interval (Nₙ, k*) cannot be generated by the interactions of existing promoters. By Postulate 1 (Constructive Primacy of Grammar), these numbers must be, by necessity, the newly emerged promoters.
   Pₙₑw = {p | p ∈ ℕ, Nₙ < p < k*}
3. State Update: The system state is updated to reflect the outcome of the competition and the possible emergence of new promoters.
   • The new "boundary" of the known world becomes Nₙ₊₁ = k*.
   • The new set of pending tasks, Cₙ₊₁, is calculated as follows:
     • Removal: The winning task (k*, p*) is removed from Cₙ.
     • Propagation: The "winning" promoter p* is placed back in the queue with its next task. The new pair will be (k* + p*, p*).
     • Initiation: For each new promoter pⱼ emerged in step 2, its first task is placed in the queue, which is always its self-interaction: (pⱼ², pⱼ).

The recursive application of the transition function T starting from S₀ generates the entire ordered sequence of promoters and composites, revealing the genealogical structure of the set of natural numbers. This formalization demonstrates that the process, while generating a sequence that locally appears complex and unpredictable, is governed by a deterministic and computable order.

Extension of the P Language: Exploratory Applications in Various Domains

The formalization of the P System has produced a language endowed with a coherent internal grammar and a rich operational apparatus. At this point in the research, a natural question arose: is the system's ability to describe generative structures limited only to the domain of Number Theory, or is its formalism general enough to be applied to other complex systems?

To investigate this possibility, I undertook a series of case studies, applying the grammar of the P System to various domains. The objective was not to provide complete models of these fields, but to evaluate the flexibility and coherence of the language as a structural analysis tool.

The Complete Operational Apparatus of the P System

At the base of these experiments is the complete set of nine grammatical operators that I defined for the P System. While the Composition (⊗) and Self-Interaction (↑) operators are sufficient for generating primes, the complete apparatus allows for much richer manipulation of symbolic structures, essential for modeling complex dynamics. The operators are:

• ⊗ — Ordered Composition: The non-commutative interaction between two or more structures to generate a new one.
• ↑ — Symbolic Power: The iteration of a single symbol, which increases its structural depth.
• ∪ — Structural Union: The merging of two compatible structures into a single entity that inherits all components.
• ∩ — Structural Intersection: The extraction of the sub-structure common to two or more symbols.
• ⊖ — Grammatical Subtraction: The coherent removal of a sub-structure from a larger one.
• ≡ — Morphological Equivalence: The operator that verifies structural and signature identity between two symbols.
• ∂ — Local Derivation: A transformation or "mutation" that minimally modifies a structure, allowing its evolution.
• ∫ — Symbolic Integration: The insertion of a structure σ within a larger grammatical context Σ.
• ↔ — Bidirectional Co-implication: A symmetric relation that establishes a co-validity link between two structures.

Case Studies: Symbolic Modeling

Using this language, I developed several preliminary application models. In each experiment, the fundamental entities of a domain (e.g., particles, atmospheric parameters) were translated into symbols π_k, and their interactions were governed by the operators of the P System. Among these, include:

• A symbolic meteorological system, capable of deducing complex events such as "heavy rain" from the grammatical coherence of symbols representing pressure, humidity, and other parameters.
• A model for particle physics, in which each particle emerges as a stable symbolic structure, the result of the combination of promoters that describe its quantum properties.
• An application in the field of cryptography, which led to the development of an encryption scheme (P-Signature) where the Morphogenetic Signature is an integral part of the encoding process.

These preliminary case studies suggest that the P System framework possesses such generality and internal coherence that it can be applied to various domains. This is a fascinating area of research that I am continuing to explore.

The Selective Genealogical Algorithm (SGA): The Final Formalization

The theoretical analysis and empirical investigation described in the previous sections have converged in the design of a final algorithm, the Selective Genealogical Algorithm (SGA). This algorithm is not an eliminative sieve in the classical sense, but a generative and constructive engine, whose logic is the faithful computational translation of the dynamic process of "propagation and emergence".

The SGA logic can be formalized in the following pseudocode:

Box 1: Pseudocode of the Selective Genealogical Algorithm.

The following diagram illustrates the system state at instant n. The algorithm does not analyze n in a vacuum, but compares its value with the "task" at the top of the Propagation Queue, which represents the next inevitable composite. The interaction between these two components determines whether n is a new Promoter (an emergence) or a Composite (a propagation).

Figure 1: Logical schema of the interaction between the Walk and the Propagation Queue.

Algorithm Architecture

The SGA operates as a finite state automaton whose function is to "populate" the number line, not linearly (n → n+1), but by jumping from one generative "event" to the next. To do this, it uses two main data structures:

• The List of Promoters (P): An ordered and dynamic list of promoters (prime numbers) discovered up to a given moment. This list expands during execution.
• The Propagation Queue (C): A priority queue (computationally implemented as a min-heap) that contains future "tasks". Each element of the queue is a tuple (product, promoter) that represents the next minimum composite that a given promoter is destined to generate. The queue always maintains at the top, with immediate access, the task with the lowest product, i.e., the most imminent composition event.

The main loop of the algorithm consists of continuously extracting the highest priority task from the queue, analyzing the numerical "gap" that has been created to discover new promoters, and finally updating the queue with new tasks generated both by the promoter that has just "worked" and by the newly discovered promoters.

Key Properties of the SGA

This architecture gives the algorithm its unique properties:

• Selectivity: The algorithm never calculates all possible combinations. The priority queue mechanism ensures that only the operation that produces the next minimum composite is executed at any given time. The generative path is unique and mandatory, and does not require memory of past products to avoid duplicates.
• Memory Efficiency: The Propagation Queue does not store all composites, but only one future task for each active promoter. Its size grows very slowly (in proportion to π(N)), making the algorithm robust on extreme numerical scales.
• Determinism: The process is entirely deterministic. Given the same inputs, it will always produce the exact same sequence of emergences and propagations.

Positioning with Respect to the State of the Art

It is useful to position the SGA with respect to classical sieves. Unlike the Sieve of Eratosthenes, which is eliminative and operates on a memory array of size N, the SGA is constructive and, in its segmented version, has a much lower memory requirement (O(√N)). Compared to the Sieve of Atkin, which is more complex and optimizes the marking of composites based on quadratic forms, the SGA adopts a different logic, based on a dynamic "scheduling" of multiplication events through a priority queue. Although all these algorithms have similar theoretical complexity (O(N) in the most optimized versions), the SGA distinguishes itself by deriving from a grammatical theoretical framework and by its intrinsically selective implementation.

Experimental Validation and Performance Analysis

To validate the effectiveness and correctness of the theoretical model, I translated the SGA logic into a high-performance implementation using the Rust programming language, applying a block strategy (segmented sieve) to further optimize memory management.

Correctness Verification

Tests were performed on a consumer-class laptop (Apple MacBook Pro, 2021, M1, 16GB RAM). The primary validation metric is the correctness of the prime number count. Table 2 compares the algorithm's results with the official values of the prime counting function π(x).

The data demonstrate a perfect correspondence, validating the logical consistency of the algorithm.

Performance and Scalability Analysis

Table 3 reports the execution times to reach the indicated limits.

The most significant analysis concerns scalability. With each 10-fold increase in the limit, the execution time increased by a factor of about 10-11 times up to 100 billion, and only 8.2 times to reach 1000 billion. This near-linear trend (O(N log log N)) demonstrates extremely high computational efficiency and the absence of significant bottlenecks, even on extreme numerical scales.

Conclusions and Future Perspectives

In this work, I introduced and formalized the P System, a theoretical framework based on a constructivist hypothesis for the nature of natural numbers. The main contributions of this research are three: first, the presentation of a new definition of primality, not based on divisibility but on non-constructibility within a formal grammar and characterized by a specific Morphogenetic Signature; second, the discovery of a deterministic generative process ("Selective Propagation") that governs the order of emergence of numbers; third, the development of a derived algorithm, the Selective Genealogical Algorithm (SGA).

The validity of the theoretical framework is corroborated by experimental results. The ability to translate the logic of the P System into the SGA algorithm, which not only correctly reproduces the prime counting function π(x) but also demonstrates exceptional computational efficiency, provides solid empirical validation to the model. The Rust implementation of the SGA calculated the 37,607,912,018 prime numbers up to 10¹² in approximately 28 minutes on consumer-class hardware, demonstrating the power and scalability of the approach.

The future perspectives of this research unfold along two main and complementary directions. The first is engineering and applicative in nature: it involves further optimization of the SGA and the application of the P System framework to other domains, as has been preliminarily explored in the field of cryptography with the P-Signature scheme. The second is a path of fundamental theoretical research: the objective is the development of a purely symbolic computational engine, operating without any arithmetic "bridge", and the expansion of SyntaxOS, an operating system conceived to be entirely based on the generative grammar of the P System.

In conclusion, the P System offers an alternative framework for analyzing the fundamental structure of numbers, interpreting them as entities emerging from a grammatical process. The complete documentation of the project, including implementations and datasets, is maintained in a public archive for review and collaboration by the scientific community.

Appendix: Rust Implementation Code