Разрешимые/перечислимые множества

[gepa]

1.Всякое разрешимое множество перечислимо
2.Обратное не верно

Вопрос заключается в том, как это доказать/пояснить, дополнений/ и без определения перечислимого множества как алгоритма, который печатает все элементы данного множества

Опр-я которые давались у нас:
Множество М разрешимо, если его характеристическая функция $\mathcal{X} (n1, n2, . . , nk) = \left\{ \begin{array}{l} $1, если (n1, n2, . . , nk) $\in$ М \\$ 0, если (n1, n2, . . , nk) \notin$М $\end{array} $ вычислима

Множество М перечислимо, если функция $\mathfrak{T}(n1, n2, . . , nk) = \left\{ \begin{array}{l} $1, если (n1, n2, . . , nk) \in$М \\ $не определено, если $(n1, n2, . . , nk) \notin$М \end{array} вычислима

заранее спасибо

[Xaositect]

gepa в сообщении #209917 писал(а):

без использования полухарактеристических функций/дополнений/ и без определения перечислимого множества как алгоритма, который печатает все элементы данного множества

gepa в сообщении #209917 писал(а):

Множество М перечислимо, если функция $\mathfrak{T}(n1, n2, . . , nk) = \left\{ \begin{array}{l} $1, если (n1, n2, . . , nk) \in$М \\ $не определено, если $(n1, n2, . . , nk) \notin$М \end{array} вычислима

Так это же и есть полухарактеристическая функция.
Как же без нее, если она в определении есть.

Для каких целей это Вам нужно?

[gepa]

Xaositect писал(а):

Так это же и есть полухарактеристическая функция.
Как же без нее, если она в определении есть.

Для каких целей это Вам нужно?

у нас она так не называлась, а везде где я искал, просто писали полухар-кая ф-ция, без ее определения

для целей чтобы сдать разобраться и сдать этот вопрос

[Профессор Снэйп]

gepa писал(а):

Вопрос заключается в том, как это доказать/пояснить, дополнений/ и без определения перечислимого множества как алгоритма, который печатает все элементы данного множества

Чего?

А вообще

1) Возьмите вычислимую функцию, определённую в единице и неопределённую в нуле, и рассмотрите её суперпозицию с характеристической функцией множества

2) Рассмотрите множество проблемы остановки