On the Computability of Ordered Fields

английский

Аннотация

В статье развиваются общии методы для структур вычислимых действительных чисел, порожденных классами всюду определенных вычислимых (рекурсивных) функций со специальными ограничениями на базисные операции с целью исследования следующих проблем: является ли порожденная структура вещественно замкнутым полем, существует ли вычислимое представление порожденной структуры. Доказана серия теорем, позволяющих утверждать, что не существует  вычислимых представлений не только  для полиномиально вычислимых действительных чисел, но и для $\mathcal{E}_n$-вычислимых действительных чисел, где $\mathcal{E}_n$ является уровнем в иерархии Гжегорчика при $n\geq 2$. Мы также предложили критерий вычислимой представимости архимедова упорядоченного поля.