Combining Determinism and Indeterminism

Abstract:Our goal is to construct mathematical operations that combine indeterminism measured from quantum randomness with computational determinism so that non-mechanistic behavior is preserved in the computation. Formally, some results about operations applied to computably enumerable (c.e.) and bi-immune sets are proven here, where the objective is for the operations to preserve bi-immunity. While developing rearrangement operations on the natural numbers, we discovered that the bi-immune rearrangements generate an uncountable subgroup of the infinite symmetric group (Sym$(\mathbb{N})$) on the natural numbers $\mathbb{N}$. This new uncountable subgroup is called the bi-immune symmetric group. We show that the bi-immune symmetric group contains the finitary symmetric group on the natural numbers, and consequently is highly transitive. Furthermore, the bi-immune symmetric group is dense in Sym$(\mathbb{N})$ with respect to the pointwise convergence topology. The complete structure of the bi-immune symmetric group and its subgroups generated by one or more bi-immune rearrangements is unknown.

Logic (math.LO); Computational Complexity (cs.CC); Computation and Language (cs.CL); Group Theory (math.GR)

arXiv:2009.03996 [math.LO]

(or arXiv:2009.03996v5 [math.LO] for this version)

From: Michael S. Fiske [view email] [v1] Wed, 2 Sep 2020 01:30:00 UTC (10 KB) [v2] Thu, 10 Sep 2020 20:49:50 UTC (11 KB) [v3] Mon, 21 Sep 2020 20:00:10 UTC (13 KB) [v4] Thu, 19 Nov 2020 18:22:48 UTC (15 KB) [v5] Tue, 3 Nov 2026 23:09:10 UTC (21 KB)