О некоторых медленно сходящихся системах преобразований термов

Л. Д. Беклемишев; Оноприенко А. А.

doi:10.4213/sm8519

Публикации

?

О некоторых медленно сходящихся системах преобразований термов

Математический сборник. 2015. Т. 206. № 9. С. 3–20.

Беклемишев Л. Д., Оноприенко А. А.

Формулируются системы преобразований термов, число шагов работы которых на произвольном входе конечно, но не ограничивается никакой вычислимой функцией, доказуемо тотальной в арифметике Пеано PА. Тем самым, утверждение о сходимости таких систем не доказуемо в PA. Эти системы получаются из независимого комбинаторного утверждения, известного как принцип червя; их также можно рассматривать как вариант хорошо известной игры Геракла и гидры, введенной Дж. Парисом и Л. Кирби.

Библиография: 16 названий.

Научное направление: Математика Компьютерные науки

Приоритетные направления: компьютерно-математическое математика

Язык: русский

Полный текст

DOI

Ключевые слова: Worm principle formal arithmetic формальная арифметика term rewriting systems преобразование термов принцип червя

PrimeKV: Preserving critical KV cache without attention scores for long-context inference

Чжан Ч., Ильвовский Д. А., Neurocomputing 2027 Vol. 710

Добавлено: 5 ноября 2026 г.

Presheaf structures governed by oriented matroids and pseudohyperplane arrangements

Лысков Д. Д., Coron B., / Series math "arxiv.org". 2026.

Добавлено: 5 ноября 2026 г.

Обобщение матричной теоремы о деревьях для пар деревьев

Ретинский В. И., Функциональный анализ и его приложения 2026 Т. 60 № 4 С. 83–100

Приведено обобщение матричной теоремы о деревьях на случай перечисления пар остовных деревьев. Это обобщение включает в качестве частных случаев и унифицирует сразу несколько известных ранее результатов, в частности классическую теорему Кирхгофа, теорему Масбаума–Вайнтроба о перечислении 3-деревьев, а также аналог матричной теоремы о деревьях для перечисления 4-элементов Кирхгофа. ...

Добавлено: 5 ноября 2026 г.

Спаривания на алгебре рядов Лорана над кольцом

Левашев В. А., Математические заметки 2026 Т. 120 № 5 С. 843–846

Пусть 𝐴 – коммутативное ассоциативное кольцо с единицей и 𝐴((𝑡)) = 𝐴[[𝑡]][𝑡−1] – кольцо рядов Лорана над 𝐴. Алгебра 𝐴((𝑡)) имеет естественную топологию, где 𝐴 – подмодули вида 𝑡𝑚𝐴[[𝑡]] образуют базу окрестностей нуля. Пусть также Ω1𝐴((𝑡))/𝐴 – модуль кэлеровых 1-дифференциалов 𝐴((𝑡)) над 𝐴. ...

Добавлено: 5 ноября 2026 г.

Spectral structure of the mixed Hessian of the dispersionless Toda τ-function

Алексеев О. В., Letters in Mathematical Physics 2026 Vol. 116 No. 5 Article 132

Добавлено: 5 ноября 2026 г.

A Multimodal Framework for Aphasia Severity Classification in Russian

Колмогорова А. В., Ekaterina Yavshitz, Margolina A. и др., Association for Computational Linguistics, 2026.

Добавлено: 4 ноября 2026 г.

An Enhanced Higher Green's Function on the Modular Curve

Сахарова Н. Е., / Series arXiv "math". 2026. No. 2610.17258.

Добавлено: 4 ноября 2026 г.

Modular Arrangements

Левин А. М., Сахарова Н. Е., / Series arXiv "math". 2024. No. 2412.17795.

Добавлено: 4 ноября 2026 г.

On chaotic axiom A diffeomorphisms with codimension one saddles and basic sets

Жужома Е. В., Медведев В. С., Regular and Chaotic Dynamics 2026 Vol. 31 No. 5 P. 732–742

Добавлено: 3 ноября 2026 г.

Nonsingular structurally stable chaotic 3-flows of attractor-repeller type

Жужома Е. В., Медведев В. С., Yu B. и др., Chaos 2026 Vol. 36 No. 6 P. 063111–063118

Добавлено: 3 ноября 2026 г.

Classification of surface A-diffeomorphisms with no zero-dimensional basic sets

Жужома Е. В., Zhirov A. Y., Russian Journal of Nonlinear Dynamics 2026 Vol. 22 No. 2 P. 403–414

Добавлено: 3 ноября 2026 г.

Modelling optimal implementation of an arbitrary N-qubit quantum gate within the generalized Bloch vectors formalism

Elena R. Loubenets, Sergey Kuznetsov, Quantum Information Processing 2026 Vol. 25 Article 358

Добавлено: 3 ноября 2026 г.

On nonsingular structural stable chaotic 3-flows of attractor-repeller type

Жужома Е. В., Medvedev V. S., Yu B., Mathematical notes 2025 Vol. 118 No. 2 P. 421–423

Добавлено: 3 ноября 2026 г.

Findings of the Association for Computational Linguistics: EMNLP 2026

Association for Computational Linguistics, 2026.

Добавлено: 3 ноября 2026 г.

PULSE: Psychological Characteristics Unified Learning via Speech-based Estimation

Абдулкадиров Т. Н., Рюмина Е. В., Рюмин Д. А. и др., Expert Systems with Applications 2026 Vol. 334 P. 1–29

Добавлено: 3 ноября 2026 г.

Smale–Williams attractors at dissipative perturbations of an integrable Hamiltonian system

Казаков А. О., Kulagin N., Lerman L. и др., Chaos 2026 Vol. 36 No. 11 P. 1–24

Добавлено: 2 ноября 2026 г.

Interpretable GNN with Stable Concepts as Neurons

Кузнецов С. О., CEUR Workshop Proceedings 2026 Vol. Vol-4247 P. 27–32

Добавлено: 2 ноября 2026 г.

Точно решаемые циклические q-цепочки Дарбу

Смирнов С. В., Дынников И. А., Успехи математических наук 2002 Т. 57 № 6 С. 183–184

Изучаются точно решаемые циклические q-цепочки Дарбу, обобщающие q-осциллятор ...

Добавлено: 1 ноября 2026 г.

Циклические q-цепочки Дарбу

Смирнов С. В., Алгебра и анализ 2003 Т. 15 № 5 С. 228–253

В работе построен дискретный q-аналог одевающей цепочки Веселова–Шабата (являющейся обобщением гармонического осциллятора). Показано, что, как и в непрерывном случае, соответствующие операторные соотношения позволяют полностью определить дискретный спектр операторов цепочки: в данном случае он состоит из нескольких q-арифметических прогрессий. В этой работе удалось реализовать циклическую q-цепочку ограниченными разностными самосопряженными операторами, причем спектр каждого из них дискретен, а собственные векторы образуют ...

Добавлено: 1 ноября 2026 г.

Полудискретные цепочки Тоды

Смирнов С. В., Теоретическая и математическая физика 2012 Т. 172 № 3 С. 387–402

Изучаются интегрируемые условия обрыва для полудискретной цепочки Тоды. Построено представление Лакса для полудискретного аналога цепочек, соответствующих простым алгебрам Ли серии C. Введены нелокальные переменные, в терминах которых записываются симметрии бесконечной полудискретной цепочки, и классифицируются условия обрыва определенного вида, совместимые с симметриями бесконечной цепочки. ...

Добавлено: 1 ноября 2026 г.

Algorithmic overlaps in the Baxter–Wu model: cluster dynamics under Novotny–Evertz updates

Пиле Я. Э., Щур Л. Н., Nuclear Physics B 2026 No. 0550-3213 Article 117706

Добавлено: 1 ноября 2026 г.

Tensor term logic for categorial grammars: simple unification of commutative and noncommutative structure

Sergey Slavnov, / Series math "arxiv.org". 2026.

Добавлено: 29 октября 2026 г.

A Three-Party W-State Quantum Secret Sharing Protocol with X-Gate Encoding and Forbidden-Outcome Detection

Timur Teregulov, Elena R. Loubenets, / Series Quantum Physics "arXiv". 2026. No. 2609.31472.

Добавлено: 28 сентября 2026 г.

Pairings on the algebra of Laurent series over a ring

Левашев В. А., / Series arXiv "math". 2026. No. 2609.06010.

Добавлено: 24 сентября 2026 г.