О полиномиально-модульных возвратных последовательностях

Sergey Seraphimovich Marchenkov

doi:10.4213/dm1667

journal article Jan 01, 2022

О полиномиально-модульных возвратных последовательностях

Sergey Seraphimovich Marchenkov

Дискретная математика Vol. 34 No. 2 pp. 43-49 · Steklov Mathematical Institute

View at Publisher Save 10.4213/dm1667

Abstract

Рассмотрены возвратные последовательности над множеством целых чисел, у которых в качестве порождающих функций используются произвольные суперпозиции полиномиальных функций и функции $|x|$, - полиномиально-модульные возвратные последовательности. Показано, как вычисления на трехленточных машинах Минского можно промоделировать с помощью полиномиально-модульных возвратных последовательностей. На основе этого результата сформулированы алгоритмически неразрешимые проблемы, связанные с полиномиально-модульными возвратными последовательностями. Рассмотрены также возвратные последовательности, в которых в качестве порождающих функций используются функции, образованные некоторыми суперпозициями полиномиальных функций и функции $[\sqrt{x}]$. Для множества таких возвратных последовательностей указана алгоритмически неразрешимая проблема.

Topics

No keywords indexed for this article. Browse by subject →

References

10

[1]

Мальцев А. И. (1986)

[2]

Марченков С. С. "О сложности возвратных последовательностей" Дискретная математика (2003) 10.4213/dm193

[3]

10.1515/156939203322109122

[4]

Марченков С. С. "О сложности полиномиальных возвратных последовательностей" Проблемы передачи информации (2018)

[5]

10.1134/s0032946018030055

[6]

Марченков С. С., Савицкий И. В. (2018)

[7]

Матиясевич Ю. В. "Диофантово представление перечислимых предикатов" Изв. АН СССР. Сер. матем. (1971)

[8]

Матиясевич Ю. В. (1993)

[9]

Нечаев В. И. (1999)

[10]

Холл М. (1970)

Metrics

1

Citations

10

References

Details

Published: Jan 01, 2022
Vol/Issue: 34(2)
Pages: 43-49

Authors

S

Sergey Seraphimovich Marchenkov

Lomonosov Moscow State University

Funding

Russian Foundation for Basic Research Award: 19-01-00200

Cite This Article

Sergey Seraphimovich Marchenkov (2022). О полиномиально-модульных возвратных последовательностях. Дискретная математика, 34(2), 43-49. https://doi.org/10.4213/dm1667

О полиномиально-модульных возвратных последовательностях

You May Also Like