Н. Т. Когабаев, О. В. Кудинов, Р. Миллер, “Вычислимая размерность $I$-деревьев бесконечной высоты”, Алгебра и логика, 2004, том 43, номер 6,страницы 702

Эта публикация цитируется в 4 статьях

Вычислимая размерность $I$-деревьев бесконечной высоты

Н. Т. Когабаев^a, О. В. Кудинов^a, Р. Миллер^b

^a Институт математики им. С. Л. Соболева СО РАН
^b Cornell University

Аннотация: Изучаются вычислимые деревья с выделенным начальным поддеревом (кратко, $I$-деревья). Доказывается, что все $I$-деревья бесконечной высоты не являются вычислимо категоричными, и, более того, они имеют эффективно бесконечную вычислимую размерность.

Ключевые слова: вычислимое дерево с выделенным начальным поддеревом, вычислимая размерность, вычислимо категоричная модель, ветвящаяся модель, эффективно бесконечная вычислимая размерность.

УДК: 510.53+512.562

Поступило: 19.02.2003
Окончательный вариант: 04.06.2004