Dyson-Schwinger equations in the theory of computation

Abstract

Following Manin's approach to renormalization in the theory of computation, we investigate Dyson-Schwinger equations on Hopf algebras, operads and properads of flow charts, as a way of encoding self-similarity structures in the theory of algorithms computing primitive and partial recursive functions and in the halting problem.

Additional Information

© 2015 American Mathematical Society. The first author was supported for this project by the Summer Undergraduate Research Fellowship (SURF) program of Caltech, through a Herbert J. Ryser fellowship. The second author is partially supported by NSF grants DMS-0901221, DMS-1007207, DMS-1201512, and PHY-1205440. The second author acknowledges MSRI for hospitality and support. The authors are especially grateful to Joachim Kock for many helpful comments and suggestions that significantly improved the paper.

Attached Files

Submitted - 1302.5040v2.pdf

Files

Additional details