?
On maximal subgroups of the group of recursive permutations
Moscow University Computational Mathematics and Cybernetics. 2016. Vol. 40. No. 3. P. 128–132.
Kolmakov E.A., Marchenkov S. S.
Bauwens B. F., Blinnikov I., , in: Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, ProceedingsVol. 12159.: Springer, 2020. P. 130–141.
It is known that the normalized algorithmic information distance is not computable and not semicomputable. We show that for all 𝜀<1/2, there exist no semicomputable functions that differ from N by at most 𝜀. Moreover, for any computable function f such that |lim𝑡𝑓(𝑥,𝑦,𝑡)−N(𝑥,𝑦)|≤𝜀 and for all n, there exist strings x, y of length n such that ...
Added: February 5, 2021
Ianovski E., Miller R., Ng K. M. et al., Journal of Symbolic Logic 2014 Vol. 3 No. 79 P. 859–881
We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relations R, S, a componentwise reducibility is defined by
R ≤ S ⇔ ∃f ∀x, y [x R y ↔ f (x) S f (y)].
Here, f is taken from a suitable class of effective functions. For us the relations will be on natural numbers, and f must be computable. We show that there is ...
Added: February 25, 2019
Day A., Fellows M., Greenberg N. et al., Berlin: Springer, 2017.
Added: October 26, 2018
Avdoshin S. M., Набебин А. А., М.: ДМК Пресс, 2019.
The book contains the necessary information from the algorithm theory, graph theory, combinatorics. It is considered partially recursive functions, Turing machines, some versions of the algorithms (associative calculus, the system of substitutions, grammars, Post's productions, Marcov's normal algorithms, operator algorithms). The main types of graphs are described (multigraphs, pseudographs, Eulerian graphs, Hamiltonian graphs, trees, bipartite ...
Added: August 24, 2018
Сутырин П. Г., Vylitok A., В кн.: Сборник научных трудов SWorld по материалам международной научно-практической конференцииТ. 1. Вып. 3.: [б.и.], 2014. С. 57–60.
В работе рассматриваются вопросы последовательного изучения теории и практики алгоритмизации и программирования, дается обзор основных теоретических формализомов и некоторых широко используемых языков программирования. ...
Added: October 27, 2015