Размышления о суб-Тьюринговой интерактивной вычислимости
Article Sidebar
Опубликован:
02.07.2025
Ключевые слова:
логика вычыслимости, интерактивное вычисление, игровая семантика
Main Article Content
Аннотация
В статье содержится описание возможного нового направления для логики вычислимости, сосредоточенного на вычислимости без бесконечной памяти или других невозможных для обладания вычислительных ресурсов. Новый подход рассматривает такие ресурсы как внешние, а не внутренние для вычислительных устройств. Они могут и должны быть учтены явно в антецедентах логических формул, выражающих вычислительные задачи.
Скачивания
Данные скачивания пока не доступны.
Article Details
Как цитировать
Japaridze G. Размышления о суб-Тьюринговой интерактивной вычислимости // Логические исследования / Logical Investigations. 2025. Т. 31. № 1. C. 97-109.
Выпуск
Раздел
Неклассические логики
Copyright (c) 2025 Giorgi Japaridze
Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.
Литература
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.