Cylindryfikacja

W teorii obliczalności cylindryczność jest konstrukcją, która łączy numerację cylindryczną z każdą numeracją . Pojęcie to zostało po raz pierwszy wprowadzone przez Jurija L. Erszowa w 1973 roku.

Definicja

$\ Displaystyle c (\ nu)$ uwagę numerację , cylindryczność jest zdefiniowana jako do ${$

${\ Displaystyle \ operatorname {Domena} (c (\ nu)): = \ {\ langle n, k \ rangle | n \ w \ operatorname {Domain} (\ nu )\}}$

${\ Displaystyle c (\ nu) \ langle n, k \ rangle: = \ nu (n)}$

gdzie $_$ _ _ _

Należy zauważyć, że operacja walcowania zwiększa arencję wejściową o 1.

Nieruchomości

• Biorąc pod uwagę dwie numeracje i ${\ Displaystyle \ mu}$$,$ to $nu \ leq \ mu \ Strzałka w prawo c (\ nu) \ leq _{1}c(\mu)}$
• ${\ Displaystyle \ nu \ równoważnik _ {1} c (\ nu)}$

• Yu. L. Ershov, „Teoria numeracji I”. Zeitschrift für mathematische Logik und Grundlagen der Mathematik 19 , 289-388 (1973).