Перечислимое множество

[werd]

Дано:
$\bigstar = $ recursively enumerable set
$\bigstar ={A \bigcap B , A \bigcup B , A }$
Нужно дать пример для $B$ которая не относится к $\bigstar$

Спасибо

[werd]

$B=\overline{A}$ подойдет?

[svv]

Нужно привести пример, когда $A, A \cap B , A \cup B$ -- рекурсивно перечислимые множества, а $B$ -- нет?

Профессор Снэйп!
Профессор Снэйп!

[werd]

svv в сообщении #589859 писал(а):

Нужно привести пример, когда $A, A \cap B , A \cup B$ -- рекурсивно перечислимые множества, а $B$ -- нет?

Профессор Снэйп!
Профессор Снэйп!

да.

[_hum_]

werd в сообщении #589826 писал(а):

$B=\overline{A}$ подойдет?

Ну, тогда ж по крайней мере нужно указать конкретное перечислимое $A$, дополнение к которому неперечислимо.

[werd]

_hum_ в сообщении #589889 писал(а):

werd в сообщении #589826 писал(а):

$B=\overline{A}$ подойдет?

Ну, тогда ж по крайней мере нужно указать конкретное перечислимое $A$, дополнение к которому неперечислимо.

Указать конкретное не получилось.
Есть что то конкретное на примете?

[Sonic86]

Есть теорема Поста: если множество и дополнение к нему рекурсивно перечислимы, то они рекурсивны.
Значит Вам достаточно будет взять рекурсивно перечислимое множество, не являющееся рекурсивным. Примеры таких множеств обязательно есть в книгах (например, в Мальцеве Матлогика есть). Скорее всего - множество значений универсальной функции всех одноместных функций подойдет. Есть и другие примеры.
Надеюсь, не наврал нигде

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

Sonic86 в сообщении #589956 писал(а):

Скорее всего - множество значений универсальной функции всех одноместных функций подойдет.

???

Множество значений - это весь натуральный ряд. Так что наврали

Нужно брать область определения.

Вообще, есть такое понятие - креативное множество. Их много, но они все вычислимо изоморфны. Вот любое из них и подойдёт.

[Sonic86]

Профессор Снэйп в сообщении #590007 писал(а):

???

Множество значений - это весь натуральный ряд. Так что наврали

Не, наврал где угодно, но только не здесь
Имелась ввиду такая конструкция: берем все одноместные примитивно-рекурсивные функции. Множество их счетно (правда ли? надо посмотреть...), потому мы их можем пронумеровать: $f_1(x),f_2(x),...$. Таким образом, существует функция $F(n,x):F(n,x)=f_n(x)$. Теперь используем диагональный метод: рассмотрим функцию $\xi(n)=F(n,n)+1$. Тогда она не примитивно-рекурсивна, от противного: Если $\xi(x)=f_i(x)=F(i,x)$ для некоторого $i$ для всех $x$, то $\xi(i)=F(i,i)+1=F(i,i)$.
Соответственно, множество значений $\xi(x)$ (это не $\mathbb{N}$) рекурсивно-перечислимо, но не рекурсивно. (или все-таки последний вывод необоснован? Множество у нас называется (примитивно)-рекурсивным, если его характеристическая функция (примитивно)-рекурсивна. $\xi(n)$ - не характеристическая для $E(\xi)$. Значит чего-то не хватает...)

Профессор Снэйп в сообщении #590007 писал(а):

Вообще, есть такое понятие - креативное множество.

Оно вроде даже в Мальцеве есть...

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

Sonic86 в сообщении #590011 писал(а):

Не, наврал где угодно, но только не здесь

Здесь бессмыслица. Если словесный мусор не считать враньём, то да, не наврали

-- Чт июн 28, 2012 21:02:15 --

Sonic86 в сообщении #590011 писал(а):

Оно вроде даже в Мальцеве есть...

Я бы не советовал читать книгу Мальцева. Она хороша, но изложение чересчур формальное. Настолько всё заформализовано, что за деревьями леса не видно.

-- Чт июн 28, 2012 21:04:55 --

Sonic86 в сообщении #590011 писал(а):

или все-таки последний вывод необоснован?

Более того, он просто неверен.

Для каждого $k \in \mathbb{N}$ функция, тождественно равная $k$ при всех значениях аргумента, будет примитивно рекурсивной. И, значит, любое $k$ войдёт в область значений функции $\xi$.

[Sonic86]

Профессор Снэйп в сообщении #590065 писал(а):

Для каждого $k \in \mathbb{N}$ функция, тождественно равная $k$ при всех значениях аргумента, будет примитивно рекурсивной. И, значит, любое $k$ войдёт в область значений функции $\xi$.

Ооо! Не ожидал, спасибо...

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

Можно ещё вот здесь почитать.

Я, когда это писал, ещё не до конца переболел мальцевским формализмом. Так что там всё довольно формально, хотя и не до такой степени, как в книге Мальцева.

[Sonic86]

Спасибо, сейчас почитаю

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

Раз уж возникло затруднение с определением вычислимо перечислимого (то есть рекурсивно перечислимого), но не вычислимого (то есть рекурсивного) множества, напишу самую простую (и самую классическую) конструкцию его построения.

Пусть $\varphi_x(y)$ - универсальная функция для класса всех одноместных вычислимых (или, что то же самое, частично рекурсивных) функций. Задаётся она, например, так:

$$ \varphi_x(y) = \begin{cases} z, &\text{если машина Тьюринга с номером } x, \text{получив на вход } y, \\ &\text{выдаёт результат } z \text{ через конечное число шагов}; \\ \text{не определено}, &\text{если машина Тьюринга с номером } x, \text{получив на вход } y, \\ &\text{никогда не останавливается}. \end{cases} $$

Теперь полагаем

$$ K = \{ x : \varphi_x(x) \text{ определено} \}. $$

Множество $K$ вычислимо перечислимо, так как является областью определения вычислимой функции. С другой стороны, если оно вычислимо, то вычислимой является функция

$$ f(x) = \begin{cases} \varphi_x(x) + 1, &x \in K; \\ 0, &x \not\in K. \end{cases} $$

Имеем $f(x) = \varphi_n(x)$ для некоторого $n \in \mathbb{N}$. Так как $f(x) = \varphi_n(x)$ определено для всех $x \in \mathbb{N}$, то определено и $\varphi_n(n)$. Но тогда $n \in K$ и $\varphi_n(n) = f(n) = \varphi_n(n) + 1$. Противоречие.