Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-23T16:04:13.048Z Has data issue: false hasContentIssue false
  • English
  • Français

Encodings of Turing machines in linear logic

Published online by Cambridge University Press:  10 June 2020

James Clift  and
Daniel Murfet Open the ORCID record for Daniel Murfet [Opens in a new window]
James Clift
Affiliation:
Department of Mathematics, University of Melbourne, Melbourne, Australia
Daniel Murfet*
Affiliation:
Department of Mathematics, University of Melbourne, Melbourne, Australia
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The Sweedler semantics of intuitionistic differential linear logic takes values in the category of vector spaces, using the cofree cocommutative coalgebra to interpret the exponential and primitive elements to interpret the differential structure. In this paper, we explicitly compute the denotations under this semantics of an interesting class of proofs in linear logic, introduced by Girard: the encodings of step functions of Turing machines. Along the way we prove some useful technical results about linear independence of denotations of Church numerals and binary integers.

Keywords

linear logicdifferential linear logicTuring machines
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 30 , Issue 4 , April 2020 , pp. 379 - 415
Copyright
© The Author(s) 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Arora, S. and Barak, B. (2009). Computational Complexity: A Modern Approach, Cambridge University Press.CrossRefGoogle Scholar
Benton, N., Bierman, G., de Paiva, V. and Hyland, M. (1992). Term Assignment for Intuitionistic Linear Logic, Technical report 262, Computer Laboratory, University of Cambridge.CrossRefGoogle Scholar
Clift, J. and Murfet, D. (2017). Cofree Coalgebras and Differential Linear Logic, arXiv preprint [arXiv:1701.01285].Google Scholar
Clift, J. and Murfet, D. (2018). Derivatives of Turing machines in Linear logic, arXiv preprint [arXiv:1805.11813].Google Scholar
Drensky, V. and Formanek, E. (2004). Polynomial Identity Rings, Birkhäuser.CrossRefGoogle Scholar
Ehrhard, T. and Regnier, L. (2003). The Differential λ-Calculus. Theoretical Computer Science 309 1–41.CrossRefGoogle Scholar
Ehrhard, T. (2016). An Introduction to Differential Linear Logic: Proof-Nets, Models and Antiderivatives, arXiv preprint [arXiv:1606.01642].Google Scholar
Girard, J.-Y. (1987). Linear logic. Theoretical Computer Science 50 (1) 1–102.CrossRefGoogle Scholar
Girard, J.-Y. (1995). Light linear logic. Information and Computation 143 (2) 175–204.CrossRefGoogle Scholar
de la Harpe, P. (2000). Topics in Geometric Group Theory, The University of Chicago Press.Google Scholar
Hyland, M. and Schalk, A. (2003). Glueing and orthogonality for models of linear logic. Theoretical Computer Science 294 183–231.CrossRefGoogle Scholar
Mairson, H. and Terui, K. (2003). On the computational complexity of cut-elimination in linear logic. In: Blundo, C. and Laneve, C. (eds.) Theoretical Computer Science. ICTCS 2003. Lecture Notes in Computer Science, vol. 2841, Springer, Berlin, Heidelberg.Google Scholar
Melliès, P.-A. (2009). Categorical semantics of linear logic. In: Interactive Models of Computation and Program Behaviour, Panoramas et Synthèses, vol. 27, Société Mathématique de France.Google Scholar
Murfet, D. (2015). On Sweedler’s cofree cocommutative coalgebra. Journal of Pure and Applied Algebra 219 5289–5304. arXiv preprint [arXiv:1406.5749].CrossRefGoogle Scholar
Murfet, D. (2014). Logic and Linear Algebra: An Introduction, arXiv preprint, [arXiv:1407.2650].Google Scholar
Rogozhin, Y. (1996). Small universal Turing machines. Theoretical Computer Science 168 215–240.CrossRefGoogle Scholar
Roversi, L. (1999). A P-time completeness proof for light logics. In: Flum, J. and Rodriguez-Artalejo, M. (eds.) Computer Science Logic. CSL 1999. Lecture Notes in Computer Science, vol. 1683, Springer, Berlin, Heidelberg, 469–483.Google Scholar
Sipser, M. (2006). Introduction to the Theory of Computation, Thomson Course Technology.Google Scholar
Sweedler, M. (1969). Hopf Algebras, W. A. Benjamin.Google Scholar
Turing, A. M. (1937). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society 2 (1) 230–265.CrossRefGoogle Scholar