2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Нерекурсивные/невычислимые множества
Сообщение04.11.2022, 20:00 
Помогите понять.
Любое нерекурсивное множество невычислимо.
Это из теории множеств, в частности про ординал $\omega_{1}^{CK}$
А могут ли невычислимые множества быть рекурсивными (частично рекурсивными) ?
Например, $BB$, как невычислимая функция, мне представляется рекурсивной.
Это так ?

 
 
 
 Re: Нерекурсивные/невычислимые множества
Сообщение04.11.2022, 20:56 
Аватара пользователя
Vozduh в сообщении #1568951 писал(а):
Любое нерекурсивное множество невычислимо.

Если я правильно понял терминологию (вычислимость $=$ рекурсивная перечислимость), то все наоборот.
Vozduh в сообщении #1568951 писал(а):
могут ли невычислимые множества быть рекурсивными

(При том же условии) нет, не могут.

 
 
 
 Re: Нерекурсивные/невычислимые множества
Сообщение04.11.2022, 22:55 
пианист в сообщении #1568960 писал(а):
Если я правильно понял терминологию (вычислимость $=$ рекурсивная перечислимость), то все наоборот.

Вы знак "равно=" правильно, употребляете ?
пианист в сообщении #1568960 писал(а):
Если я правильно понял терминологию (вычислимость $=$ рекурсивная перечислимость), то все наоборот.

Это из учебника. И так понятно(ноль информации). Если не рекурсивно - значит невычислимо. Вас спросили про наоборот: если невычислимо, но рекурсивно (и есть практические примеры, например: $BB$), то что ??

 
 
 
 Re: Нерекурсивные/невычислимые множества
Сообщение05.11.2022, 09:08 
Аватара пользователя
Vozduh в сообщении #1568968 писал(а):
Вы знак "равно=" правильно, употребляете ?

Извините, пожалуйста, не понял ни Вашего ответа, ни того, правильно ли я понял терминологию (я, если что, ориентируюсь на книжечку Роджерса).
Дальше пишу, считая, что правильно понял термины "рекурсивный" (как в Роджерсе) и "вычислимый" (то же, что "рекурсивно перечислимый" в Роджерсе).
Если Ваши термины имели другой смысл, просто игнорируйте мои сообщения.
Vozduh в сообщении #1568968 писал(а):
И так понятно(ноль информации).

Вы написали неверное утверждение, что же я могу еще добавить, какую информацию?
Правильное "рекурсивное множество вычислимо".
Ну, могу еще контрпример привести: множество номеров алгоритмов, которые правильно отрабатывают свой номер.
Это множество нерекурсивно, но вычислимо (см. Роджерс, §5.2).

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group