RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1971 Volume 20, Pages 263–271 (Mi znsl2414)

A pseudo-rundamental sequence not equivalent to any monotone sequence

G. S. Tseitin


Abstract: An algorithmic sequence $\varphi$ of rational numbers is called pseudo-fundamental if
$$ \forall m\rceil\rceil\exists n\forall kl(k>n\& l>n\supset|\varphi_k-\varphi_l|<2^{-m}). $$
Two sequences $\varphi$ and $\psi$ are called equivalent if
$$ \forall m\rceil\rceil\exists n\forall l(l>n\supset|\varphi_l-\psi_l|<2^{-m}). $$

A pseudo-fundamental sequence is constructed that is not equivalent to any monotonous sequence (it is the difference of two bounded increasing sequences). The construction is based on two recursively enumerable sets with incomparable degrees of unsolvability or on a weaker result proved independently.



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024