Stochastic Turing Machines obtained from ensembles of Wang tiling
Cenap Özel, Patrick Linker, Mustafa Tahsin Yılmaz · 2025
We propose a novel generalization of the saddle-point method for evaluating high-dimensional oscillatory integrals, particularly arising in contexts such as statistical field theories and computational complexity models. Our method builds upon the recursive insertion of unity via delta functionals, enabling a multistage approximation that adapts to the structure of critical points. In particular, this method is applied to a path-integral formulation of a Random Turing Machine based on Wang tile ensembles, capturing stochastic computational evolution. We demonstrate that our approach, while conservative in assumptions, exhibits superior accuracy and depth when applied to integrals with strongly fluctuating integrands. Furthermore, we show that our generalized method can be hybridized with resurgence techniques at the leaf nodes of the critical-point tree. This allows the method to interpolate between traditional saddle-point methods and modern transseries expansions. The theoretical underpinnings are situated alongside recent developments by Linker and Ozel (2025), who provided a formal analysis of generalized saddle-point approximations in multidimensional contexts.