Некоторые проблемы разрешимости и выразимости для предиката делимости на два последовательных числа

  • Михаил Романович Старчак Санкт-Петербургский государственный университет, Санкт-Петербург, Россия
Ключевые слова: делимость на два последовательных числа, арифметическая выразимость, экзистенциальная теория натуральных чисел со сложением и делимостью, алгоритмическая разрешимость, слабые арифметики

Аннотация

Предикат делимости на два последовательных числа DW(x,y) ÷ x | y ∧ 1+x | y был предложен Л. ван ден Дрисом и А. Уилки в работе, посвященной изучению свойств подмножеств натуральных чисел, экзистенциально выразимых с помощью единицы, сложения и делимости. В настоящей работе доказывается неразрешимость множества истинных в натуральных числах экзистенциальных формул, записанных с помощью только DW и умножения, а также выразимость всех арифметических предикатов с помощью только сложения и DW или только DW и делимости. Кроме того, получены некоторые результаты о выразимости для DW и отношения порядка.

Биография автора

Михаил Романович Старчак, Санкт-Петербургский государственный университет, Санкт-Петербург, Россия

Старчак Михаил Романович, аспирант кафедры информатики СПбГУ; 199034 Санкт-Петербург, Университетская наб., 7/9, mikhstark@gmail.com

Литература

Бельтюков А. П. Разрешимость универсальной теории натуральных чисел со сложением и делимостью // Записки научных семинаров ЛОМИ. 1975. Т. 60. С. 15–28.

Lipshitz L. The Diophantine problem for addition and divisibility // Transactions of the American Mathematical Society. 1976. Vol. 235. P. 271–283. doi:10.2307/1998219

Lipshitz L. Some remarks on the Diophantine problem for addition and divisibility // Bull. Soc. Math. Belg. Ser. B. 1981. Vol. 33, no. 1. P. 41–52.

Lechner A., Ouaknine J., Worrell J. On the Complexity of Linear Arithmetic with Divisibility // Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science(LICS). 2015.

P. 667–676. doi:10.1109/LICS.2015.67

Haase C. On the complexity of model checking counter automata. Ph.D. Thesis. University of Oxford.

Bundala D., Ouaknine J. On parametric timed automata and one-counter machines // Information and

Computation. 2017. Vol. 253. P. 272–303. doi:10.1016/j.ic.2016.07.011

Van den Dries L., Wilkie A.J. The laws of integer divisibility, and solution sets of linear divisibility

conditions // The Journal of Symbolic Logic. 2003. Vol. 68, no. 2. P. 503–526. doi:10.2178/jsl/1052669061

Starchak M. R., Kosovskii N. K., Kosovskaya T. M. Some NP-Hard Problems for the Simultaneous

Coprimeness of Values of Linear Polynomials // Global Journal of Computer Science and Technology.

Vol. 17, no. 4. P. 21–25.

Korec I. A list of arithmetical structures complete with respect to the first-order definability //

Theoretical Computer Science. 2001. Vol. 257, no. 1–2. P. 115–151. doi:10.1016/S0304-3975(00)00113-4

Richard D. What are Weak Arithmetics? // Theoretical Computer Science. 2001. Vol. 257. P. 17–29.

Robinson J. Definability and decision problems in arithmetic // The Journal of Symbolic Logic. 1949.

Vol. 14. P. 98–114. doi:10.2307/2266510

Mostowski A. On direct products of theories // The Journal of Symbolic Logic. 1952. Vol. 17, no. 1.

P. 1–31. doi:10.2307/2267454

Матиясевич Ю. В. Диофантовость перечислимых множеств // Докл. АН СССР. 1970. Т. 191, № 2.

С. 278–282.

Матиясевич Ю. В. Десятая проблема Гильберта. М.: Физматлит. 1993.

Carmichael L. C. On the numerical factors of the arithmetic forms αn ±βn// Ann. Math. 1913. Vol. 15,

no. 2. P. 30–69. doi:10.2307/1967798

Woods A. Some problems in logic and number theory. PhD Thesis. University of Manchester. 1981.

Richard D. All arithmetical sets of powers of primes are first-order definable in terms of the

successor function and the coprimeness predicate // Discrete Mathematics. 1985. Vol. 53. P. 221–247.

doi:10.1016/0012-365X(85)90144-X

Lipshitz L. Quadratic forms, the five square problem, and diophantine equations // The collected

works of J. Richard Buchi (S. MacLane and Dirk Siefkes, eds.). Springer. 1990. P. 677 ¨ –680.

Косовский Н. К. О решении систем, состоящих одновременно из уравнений в словах и неравенств в длинах слов // Записки научных семинаров ЛОМИ. 1974. Т. 40. С. 24–29.

Опубликован
2018-12-28
Выпуск
Раздел
Информатика