НГУ

Форумы НГУ
Текущее время: Сб сен 23, 2017 9:37 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
 Заголовок сообщения: Проблемы теории вычислимости
СообщениеДобавлено: Ср апр 26, 2006 9:31 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт сен 07, 2001 7:00 am
Сообщения: 2848
Откуда: Станислав Березнюк
На заседаниях спецсеминара "Теория вычислимости" 4 и 11 апреля 2006 года в рамках "Дня проблем" были озвучены ниженаписанные проблемы. Так как запись велась со слуха и на большой скорости, то в тексте наверняка есть ошибки - просьба к авторам проблем вносить исправления.

_________________
Мордор жил, Мордор жив, Мордор будет жить!


Последний раз редактировалось slb Ср апр 26, 2006 9:48 pm, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср апр 26, 2006 9:47 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт сен 07, 2001 7:00 am
Сообщения: 2848
Откуда: Станислав Березнюк
С.С.Гончаров

1.Необходимые и достаточные условия для существования
у \omega-категоричной теории вычислимой модели.

2.Необходимые и достаточные условия для существования у
\omega_1-категоричной сильно минимальной теории
вычислимой модели.

3.Верно ли, что если у сильно минимальной теории
есть вычислимая модель, то все остальные её модели -
0^{(2)}-вычислимы?

4.(Проблема Морли) Верно ли, что если теория - эренфойхтова
и разрешима, и все её типы разрешимы, то все её счётные
модели разрешимы?

5.(Ослабленный вариант проблемы Морли) Верно ли, что если теория -
эренфойхтова и имеет арифметическую сложность, и все её типы имеют
арифметическую сложность, то и все её счётные модели имеют
арифметическую сложность?

6.Верно ли, что все счётные модели любой эренфойхтовой теории
почти однородны?

7.Верно ли, что почти однородные модели наследственно разрешимой
эренфойхтовой теории разрешимы?

8.Известно, что если зафиксирована предикатная сигнатура, то можно
построить универсальную последовательность M_0, ..., M_n, ...
всех моделей этой сигнатуры. Какова сложность индексного множества
моделей Маккея? Моделей неконструктивного ранга, не являющихся
моделями Маккея?

9.Пусть M - вычислимая модель неконструктивного ранга. Верно ли, что для
любого конструктивного ординала \alpha существует вычислимая модель
M_{\alpha} вычислимого ранга такая, что M_{\alpha} элементарно
эквивалентна M?

10.Пусть M - вычислимая модель неконструктивного ранга. Верно ли, что
существует модель M', вычислимо изоморфная M? но не гиперарифметически
изоморфная M?

11.Оценить ранг Скотта автоматных структур.

12.Пусть \Psi_{\phi_1, ...\phi_n} - оператор, определяющий одну модель
в другой с помощью \Sigma-формул \phi_1, ..., \phi_n. Какие дополнительные
условия надо наложить на этот оператор, чтобы взаимно определимые модели
имели сравнимые ранги Скотта?

13.Пусть S_0 - семейство \Sigma^{-1}_2-множеств. Верно ли, что если
у этого семейства есть две неэквивалентные \Sigma^{-1}_2-вычислимые
нумерации, то у него есть бесконечное число \Sigma^{-1}_2-вычислимых нумераций?

14.Пусть S_0 - семейство \Sigma^{-1}_2-множеств. Всегда ли полурешётка
его вычислимых нумераций не является решёткой?

15.Известно, что если S - семейство \Sigma^0_n-множеств, а S_1 - семейство
\Sigma^0_{n+3}-множеств, то полурешётка Роджерса \Sigma_n-вычислимых
нумераций S неизоморфна полурешётке Роджерса \Sigma_{n+3}-вычислимых
нумераций S_1. Верно ли это же для n+1? Для n+2?

16.Доказать аналог теоремы Фридберга для \Sigma^1_1-множеств.

17.Существует ли вычислимая нумерация всех моделей отношений эквивалентности
с точностью до изоморфизма?


С.Ю.Подзоров

18.(Проблема Ершова) Пусть S_1 и S_2 - конечные семейства. Верно ли, что
их полурешётки Роджерса вычислимых нумераций изоморфны тогда и только
тогда, когда сами семейства изоморфны как частичные порядки без максимальных
элементов?

19.Верно ли, что следующий структуры изоморфны между собой?
а)Универсальная лахлановская решётка без наибольшего элемента
б)Полурешетки Роджерса \Sigma^0_2-вычислимых нумераций конечных семейств, состоящих из попарно не сравнимых по включению множеств
в)Полурешётка простых m-степеней
г)Полурешётка гиперпростых m-степеней

20.(Проблема локального описания R^0_n(S)) Описать все типы изоморфизма
интервалов R^0_n(S).

21.Верно ли, что если в S нет наименьшего по включению элемента, то
в R^0_{n+2}(S) нет наибольшего элемента?

22.Верно ли, что наибольший элемент в R^0_n(S) не является минимальным
накрытием никакого другого элемента?

23.Пусть M - 2-конструктивизируемая модель. Верно ли, что класс её
конструктивизаций невычислим? Эффективно бесконечен?


А.С.Морозов

24.Описать все группы вида Aut_c M, т.е группы, представимые как группа
вычислимых автоморфизмов некоторой вычислимой модели M.

25.Верно ли, что все вычислимые группы можно представить как группы
автоматных автоморфизмов автоматных моделей?

26.(Проблема Гончарова) Верно ли, что класс всех групп вида Aut_c M
замкнут относительно свободного произведения?

27.Совпадают ли абстрактные классы групп вида Aut_c M для вычислимых
и автоматных моделей?

28.[Точную формулировку автор обещал представить позднее]



В.Г.Пузаренко

29.Пусть имеется дескриптивное свойство P. Какие мощности допустимых множеств
можно представить с помощью этого свойства? В частности, насколько большие
кардиналы реализуемы с помощью свойства униформизации?

30.Верно ли, что если в допустимом множестве есть свойство редукции, то
есть и универсальная функция?

31.(Ю.Л.Ершов, 1996) Пусть T - разрешимая, модельно полная, полная,
\omega-категоричная теория конечной сигнатуры с разрешимым множеством
полных формул. Тогда для любого плотного линейного порядка L без концов
существует модель M теории T такая, что она \Sigma-определима в HF(L)
и мощность M равна мощности L.

32.Определим сигма-сводимость так: множество A сигма-сводится к множеству B
тогда и только тогда, когда для любой модели M из сигма-определимости
модели M в A следует сигма-определимость модели M в B. Через D_{\omega}
обозначим полурешётку степеней по сигма-сводимости. Будет ли она решёткой?

33.Известно, что полурешётка e-степеней изоморфно вкладывается в D_{\omega}.
Обозначим этот идеал через D_{\omega,I}. Как он соотносится с
D_{\omega,\hat{0}}?

34.Существует ли допустимое множество A такое, что его скачок эквивалентен
сам себе?



Ю.Л.Ершов

35.Известно, что элемент a полурешётки m-степеней L_m является решёточным
тогда и только тогда, когда любой идеал в \hat{a} - главный;
элемент a полурешётки вычислимых m-степеней L^0_m является решёточным
тогда и только тогда, когда любой вычислимый идеал в \hat{a} - главный.
Обозначим множество решёточных элементов в L_m через Lat(L_m).
Верно ли, что пересечение Lat(L_m) и L^0_m не совпадает с Lat(L^0_m)?

36.Разрешимы ли поле формальных степенных рядов над конечным полем F<<t>>
и поле рациональных функций от одной переменной над полем комплексных чисел C(x)?

37.Добавим к полю p-адических чисел все корни n-й степени из p.
Будет ли это поле разрешимым?



С.Ю.Подзоров

38.Стандартное определение сводимости нумераций таково: нумерация \nu
сводится к нумерации \mu тогда и только тогда, когда существует
вычислимая функция f такая, что \nu эквивалентна \mu*f.
Введём сводимость с оракулом: \nu a-сводится к \mu тогда и только тогда,
когда существует a-вычислимая функция f такая, что \nu эквивалентна \mu*f.
Какие существуют взаимосвязи между различными типами сводимости нумераций?

39.Слабая сводимость нумераций определяется так: \nu слабо сводится к \mu
тогда и только тогда, когда существует вычислимая функция f, действующая
из натурального ряда в множество всех конечных подмножеств натурального ряда,
такая, что для любого натурального числа x \nu(x) \in \mu(f(x)).
Какие существуют взаимосвязи между слабой и обычной сводимостями?

40.Верно ли, что если частично упорядоченное множество имеет
\Delta^0_2-представление, то для него есть и позитивное представление?

41.Рассмотрим конструктивизации натуральных чисел с естественным порядком.
Введём такую слабую сводимость: нумерация \nu слабо сводится к нумерации \mu
тогда и только тогда, когда существует вычислимая функция f такая, что
мощность отрезка [0,n] в нумерации \nu не превосходит мощности отрезка
[0,f(n)] в нумерации \mu. Какие структуры получаются?



С.С.Гончаров

42.Оценить ранг Скотта для автоустойчивых моделей и моделей конечной
размерности. Будут ли они хотя бы арифметическими?

43.Верно ли, что каждая автоустойчивая модель имеет семейство Скотта
из AE-формул?

44.Верно ли, что ранги Скотта автоустойчивых моделей и моделей конечной
размерности совпадают?

45.Если \alpha - предельный вычислимый ординал, то существует ли
вычислимая модель, которая \Sigma_{\alpha}-автоустойчива, но не имеет
\Sigma_{\alpha}-вычислимого семейства Скотта? Существует ли для
произвольного натурального n вычислимая модель M такая, что
dim_{\Sigma_{\alpha}} (M) = n?

46.Пусть булева алгебра B a-вычислима для n-low степени a. Будет ли B вычислимой,
если n>4?

47.Для каких классов существуют модели M такие, что M - не вычислима, но
вычислима относительно любой ненулевой степени?

48.Пусть T - разрешимая полная теория со счётным числом счётных моделей.
Будет ли её простая модель разрешимой? Существует ли у неё однородная
разрешимая модель?

48'.(Ю.Л.Ершов) Те же вопросы, с заменой "разрешимая" на "конструктивная".

49.Пусть T - \omega_1-категоричная теория, но не \omega-категоричная.
Известно, что её модели образуют цепочку M_0 < M_1 < ... < M_{\omega}.
Обозначим через Sp_{Con}(T) множество {n| M_n - вычислима}.
Какие множества могут реализовываться как Sp_{Con}(T)? В частности,
может ли реализоваться произвольное конечное множество?

50.Пусть T - \omega_1-категоричная теория с вычислимой моделью. Верно ли,
что T имеет арифметическую сложность?

51.Существует ли \omega-категоричная теория конечной алгоритмической размерности?

52.Верно ли для \omega_1 -категоричной теории, что если какая-то её модель
автоустойчива, то и все элементарно вкладывающиеся в неё модели тоже
автоустойчивы?



А.Г.Мельников

53.Можно ли классифицировать множества, которые являются монотонно аппроксимируемыми?

_________________
Мордор жил, Мордор жив, Мордор будет жить!


Последний раз редактировалось slb Чт апр 27, 2006 5:04 pm, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт апр 27, 2006 1:43 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Проблема 19, в пункте б) ерунда написана. Надо так:

б) Полурешетки Роджерса $\Sigma^0_2$-вычислимых нумераций конечных семейств, состоящих из попарно не сравнимых по включению множеств.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт апр 27, 2006 5:05 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт сен 07, 2001 7:00 am
Сообщения: 2848
Откуда: Станислав Березнюк
Коба писал(а):
Проблема 19, в пункте б) ерунда написана. Надо так:

б) Полурешетки Роджерса $\Sigma^0_2$-вычислимых нумераций конечных семейств, состоящих из попарно не сравнимых по включению множеств.


Fixed.

_________________
Мордор жил, Мордор жив, Мордор будет жить!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс авг 27, 2006 9:32 pm 
Не в сети
Редкий гость

Зарегистрирован: Ср авг 23, 2006 11:32 am
Сообщения: 3
Какие успехи достигнуты в решении проблемы Кука?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 30, 2008 11:42 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
freeneutron писал(а):
Какие успехи достигнуты в решении проблемы Кука?


:) :)

Пустили в действие дубинку из бамбука,
Тюк прямо в темя - и нету Кука.


Ну а если более по теме, то имею сообщить, что проблемы 19 и 20 уже решены.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB