Конструктивная математическая логика
Об алгорифмах, накрывающих данный алгорифм
А. В. Идельсон
Аннотация:
В работе Н. А. Шанина (РЖМат, 1964, 9А65) рассматривается отношение: "алгорифм
$\Phi_2$ является накрывающим для алгорифма
$\Phi_1$" и доказывается теорема о том, что, каков бы ни был алгорифм
$\Phi_1$, он является алгорифмом, перерабатывающим
$F$-числа в
$F$-числа тогда и только
тогда, когда существует алгорифм
$\Phi_2$, перерабатывающий дуплекс в дуплекс и являющийся накрывающим для алгорифма
$\Phi_1$. Аналогичная теорема доказывается в этой же работе для последовательностей
$F$-чисел и последовательностей дуплексов. В настоящей статье вводятся четыре
различных обобщения указанных отношений между алгорифмами, а именно отношения: "алгорифм
$\Phi_2$ накрывает (сильно накрывает,
$n$-накрывает, сильно
$n$-накрывает) с помощью алгорифмов списка
$\Pi$ алгорифм
$\Phi_1$ относительно списка родовых букв
$N$", и выясняется, каким условиям должны удовлетворять алгорифмы, чтобы для них были справедливы теоремы, являющиеся подходящими обобщениями вышеупомянутых теорем.
Теоремы записываются в виде формул языка
$\text{Я}_\Sigma^0$, рассмотренного в работе автора (РЖМат, 1966, 2А73), и доказываются описанием выводов этих формул в исчислении
$\mathbf{NK}_1^\Sigma$, которое изучалось в этой же статье.
Библ. – 4 назв.