Thoughts on sub-Turing interactive computability
##plugins.themes.bootstrap3.article.sidebar##
Published:
02.07.2025
##plugins.themes.bootstrap3.article.main##
Abstract
The article contains an outline of a possible new direction for Computability Logic, focused on computability without infinite memory or other impossible-to-possess computational resources. The new approach would see such resources as external rather than internal to computing devices. They could or should be accounted for explicitly in the antecedents of logical formulas expressing computational problems.
##plugins.generic.usageStats.downloads##
##plugins.generic.usageStats.noStats##
##plugins.themes.bootstrap3.article.details##
How to Cite
Japaridze G. Thoughts on sub-Turing interactive computability // Logicheskie Issledovaniya / Logical Investigations. 2025. VOL. 31. № 1. C. 97-109.
Issue
Section
Non-classical logics
Copyright (c) 2025 Giorgi Japaridze
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
References
Bauer, 2014 – Bauer, M. “A PSPACE-complete first order fragment of computability logic”, ACM Transactions on Computational Logic, 2014, Vol. 15, No. 1, pp. 1–12.
Blass, 1972 – Blass, A. “Degrees of indeterminacy of games”, Fundamenta Mathematicae, 1972, Vol. 77, No. 2, pp. 151–166.
Blass, 1992 – Blass, A. “A game semantics for linear logic”, Annals of Pure and Applied Logic, 1992, Vol. 56, No. 1–3, pp. 183–220.
Church, 1936 – Church, A. “An unsolvable problem of elementary number theory”, American Journal of Mathematics, 1936, Vol. 58, No. 2, pp. 345–363.
Felscher, 1985 – Felscher, W. “Dialogues, strategies and intuitionistic provability”, Annals of Pure and Applied Logic, 1985, Vol. 28, No. 3, pp. 217–254.
Girard, 1987 – Girard, J.-Y. “Linear logic”, Theoretical Computer Science, 1987, Vol. 50, No. 1, pp. 1–102.
Goldin et al., 2006 – Goldin, D., Smolka, S., Wegner, P. (eds.), Interactive Computation: The New Paradigm. Springer, Berlin, 2006.
Hintikka, 1973 – J. Logic, Language-Games and Information: Kantian Themes in the Philosophy of Logic. Clarendon Press, Oxford, 1973.
Japaridze, 2003 – Japaridze, G. “Introduction to computability logic”, Annals of Pure and Applied Logic, 2003, Vol. 123, No. 1–3, pp. 1–99.
Japaridze, 2020 – Japaridze, G. “Fundamentals of computability logic 2020”, Journal of Applied Logics – IfCoLoG Journal of Logics and their Applications, 2020, Vol. 7, pp. 1115–1177.
Kwon, 2014 – K. “Expressing algorithms as concise as possible via computability logic”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E97-A 2014, pp. 1385–1387.
Lorenzen, 1961 – Lorenzen, P. “Ein dialogisches Konstruktivit¨atskriterium”, in: Infinitistic Methods (Proc. Sympos. Foundations of Math., Warsaw 1959). Oxford: Pergamon Press, 1961, pp. 193–200.
Mezhirov, Vereshchagin, 2010 – Mezhirov, I., Vereshchagin, N. “On abstract resource semantics and computability logic”, Journal of Computer and Systems Sciences, 2010, Vol. 76, No. 5, pp. 356–372.
Sipser, 2013 – Sipser, M. Introduction to the Theory of Computation. Boston: Cengage Learning, 2013.
Qu et al., 2013 – Qu, M., Luan, J., Zhu, D., Du, M. “On the toggling-branching recurrence of computability logic”, Journal of Computer Science and Technology, 2013, Vol. 28, No. 2, pp. 278–284.
Turing, 1936 – Turing, A. “On Computable numbers with an application to the entsheidungsproblem”, Proceedings of the London Mathematical Society, 1936, Series 2, Vol. 42, No. 3, pp. 230–265.
Xu, Liu, 2012 – Xu, W., Liu, S. “Soundness and completeness of the cirquent calculus system CL6 for computability logic”, Logic Journal of the IGPL, 2012, Vol. 20, No. 1, pp. 317–330.
Blass, 1972 – Blass, A. “Degrees of indeterminacy of games”, Fundamenta Mathematicae, 1972, Vol. 77, No. 2, pp. 151–166.
Blass, 1992 – Blass, A. “A game semantics for linear logic”, Annals of Pure and Applied Logic, 1992, Vol. 56, No. 1–3, pp. 183–220.
Church, 1936 – Church, A. “An unsolvable problem of elementary number theory”, American Journal of Mathematics, 1936, Vol. 58, No. 2, pp. 345–363.
Felscher, 1985 – Felscher, W. “Dialogues, strategies and intuitionistic provability”, Annals of Pure and Applied Logic, 1985, Vol. 28, No. 3, pp. 217–254.
Girard, 1987 – Girard, J.-Y. “Linear logic”, Theoretical Computer Science, 1987, Vol. 50, No. 1, pp. 1–102.
Goldin et al., 2006 – Goldin, D., Smolka, S., Wegner, P. (eds.), Interactive Computation: The New Paradigm. Springer, Berlin, 2006.
Hintikka, 1973 – J. Logic, Language-Games and Information: Kantian Themes in the Philosophy of Logic. Clarendon Press, Oxford, 1973.
Japaridze, 2003 – Japaridze, G. “Introduction to computability logic”, Annals of Pure and Applied Logic, 2003, Vol. 123, No. 1–3, pp. 1–99.
Japaridze, 2020 – Japaridze, G. “Fundamentals of computability logic 2020”, Journal of Applied Logics – IfCoLoG Journal of Logics and their Applications, 2020, Vol. 7, pp. 1115–1177.
Kwon, 2014 – K. “Expressing algorithms as concise as possible via computability logic”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E97-A 2014, pp. 1385–1387.
Lorenzen, 1961 – Lorenzen, P. “Ein dialogisches Konstruktivit¨atskriterium”, in: Infinitistic Methods (Proc. Sympos. Foundations of Math., Warsaw 1959). Oxford: Pergamon Press, 1961, pp. 193–200.
Mezhirov, Vereshchagin, 2010 – Mezhirov, I., Vereshchagin, N. “On abstract resource semantics and computability logic”, Journal of Computer and Systems Sciences, 2010, Vol. 76, No. 5, pp. 356–372.
Sipser, 2013 – Sipser, M. Introduction to the Theory of Computation. Boston: Cengage Learning, 2013.
Qu et al., 2013 – Qu, M., Luan, J., Zhu, D., Du, M. “On the toggling-branching recurrence of computability logic”, Journal of Computer Science and Technology, 2013, Vol. 28, No. 2, pp. 278–284.
Turing, 1936 – Turing, A. “On Computable numbers with an application to the entsheidungsproblem”, Proceedings of the London Mathematical Society, 1936, Series 2, Vol. 42, No. 3, pp. 230–265.
Xu, Liu, 2012 – Xu, W., Liu, S. “Soundness and completeness of the cirquent calculus system CL6 for computability logic”, Logic Journal of the IGPL, 2012, Vol. 20, No. 1, pp. 317–330.