Michael Stephen Fiske

Michael Stephen Fiske

A mathematical concept is identified and analyzed that is implicit in the 2012 paper Turing Incomputable Computation, presented at the Alan Turing Centenary Conference (Turing-100, Manchester). The concept, called dynamic level sets, is distinct from mathematical concepts in the standard literature on dynamical systems, topology, and computability theory. A new mathematical object is explained and why it may have escaped prior characterizations, including the classical result of de Leeuw, Moore, Shannon, and Shapiro that probabilistic Turing machines (with bias $p$ where $p$ is Turing computable) compute no more than deterministic ones. A key mechanism underlying the concept is the Principle of Self-Modifiability, whereby the physical realization of an invariant logical level set is reconfigured at each computational step by an incomputable physical process.

Michael Stephen Fiske

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.