Growth Functions, Rates and Classes of String-Based Multiway Systems
Yorick Zeschke
Junior Research Affiliate
Wolfram Research, Inc.
yzeschke@gmail.com
Abstract
Inspired by the recently emerging Wolfram Physics Project where “Multiway Systems,” graph representations of abstract rewriting systems equipped with a causal structure, have played an important role in discrete models of spacetime and quantum mechanics, this paper establishes several more fundamental properties about the growth (number of states over steps in a system’s evolution) of string rewriting systems in general. While proving the undecidability of exactly determining a system’s growth function, we show several asymptotic properties all growth functions of arbitrary string rewriting systems share. Through an explicit construction, it is proven that string rewriting systems, while never exceeding exponential functions in their growth, are capable of growing arbitrarily slowly, that is, slower than the asymptotic inverse of every Turing-computable function. Additionally, an elementary classification scheme partitioning the set of string rewriting systems into finitely many nontrivial subsets is provided. By introducing arithmetic-like operations under which Multiway Systems form a weakened semiring structure, it is furthermore demonstrated that their growth functions, while always being primitively recursive, can approximate many well-known elementary functions classically used in calculus, which underlines the complexity and computational diversity of Multiway Systems. In the context of the Wolfram Physics Project, some implications of these findings are discussed as well.
Keywords: string rewriting systems; growth functions; Wolfram Physics Project
Cite this publication as:
Y. Zeschke, “Growth Functions, Rates and Classes of String-Based Multiway Systems,” Complex Systems, 31(1), 2022 pp. 123–164.
https://doi.org/10.25088/ComplexSystems.31.1.123
