|
This article is cited in 2 scientific papers (total in 2 papers)
Generic amplification of recursively enumerable sets
A. N. Rybalov Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, ul. Pevtsova 13,
Omsk, 644099 Russia
Abstract:
Generic amplification is a method that allows algebraically undecidable problems to generate problems undecidable for almost all inputs. It is proved that every simple negligible set is undecidable for almost all inputs, but it cannot be obtained via amplification from any undecidable set. On the other hand, it is shown that every recursively enumerable set with nonzero asymptotic density can be obtained via amplification from a set of natural numbers.
Keywords:
algorithmically undecidable problem, generic amplification, undecidable set, simple negligible set, recursively enumerable set.
Received: 19.04.2017 Revised: 15.04.2018
Citation:
A. N. Rybalov, “Generic amplification of recursively enumerable sets”, Algebra Logika, 57:4 (2018), 448–455; Algebra and Logic, 57:4 (2018), 289–294
Linking options:
https://www.mathnet.ru/eng/al858 https://www.mathnet.ru/eng/al/v57/i4/p448
|
|