Вычислимая представимость счетных линейных порядков

Данная работа посвящена изучению алгоритмических свойств счетных линейных порядков на основе построения эффективных представлений этих структур на множестве натуральных чисел. В 1991 г. К. Джокуш и Р. Соар построили низкий линейный порядок, не имеющий вычислимого представления. Ранее, в 1989 г., Р. Доуни и М. Мозес показали, что каждый низкий дискретный линейный порядок имеет вычислимую копию. Естественно спросить, для каких еще порядковых типов представление в низкой степени достаточно для существования вычислимого представления. Этот вопрос, а точнее программу исследований, сформулировал в 1998 г. Р. Доуни: описать такие порядковые свойства $P$, что для любого низкого линейного порядка $L$ из выполнимости $P(L)$ следует существование вычислимого представления. В этой работе изложен подробный обзор основных результатов в этом направлении, которые в основном получены автором этой работы либо самостоятельно, либо в соавторстве.