Рекурсивно перечислимое множество

[gurukamu]

Ребята, как это доказывать?
Доказать, что множество $A$ рекурсивно перечислимо тогда и только тогда, когда
$x \in A \equiv \exists yR(x,y) $, где $R(x,y)$ - рекурсивный предикат.
Всю голову сломал, искал в Колмогорове и Мендельсоне, не нашел, дается как определение.

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

1) Если $R$ - рекурсивный предикат, то перечислять множество $\{ x : \exists y R(x,y) \}$ очень просто. Эффективно перечисляем все пары $\langle x, y \rangle \in \mathbb{N}^2$ и каждый раз, когда для пары $\langle x,y \rangle$ оказывается выполнен предикат $R(x,y)$, заносим число $x$ в список элементов этого множества.

2) Если $A$ рекурсивно перечислимо, то существует машина Тьюринга $T$, которая, принимая на вход натуральные числа, останавливается через конечное число шагов в точности на числах из $A$. И надо лишь заметить, что предикат $R(x,y) \Leftrightarrow $ "машина $T$, получив на вход $x$, останавливается за $y$ шагов", рекурсивен (даже примитивно рекурсивен).

P. S. Читайте Роджерса и в первую очередь Роджерса. Подряд, пока не станет казаться слишком сложно. И забудьте про другие книги!

[gurukamu]

Профессор Снэйп
Спасибо большое, друг!

-- 30.06.2012, 16:14 --

Профессор Снэйп
Еще вопрос, что значит "эффективно перечисляем"?

[gurukamu]

Профессор Снэйп
и еще тогда вопрос, если я не ошибаюсь, то это теорема Поста?

Цитата:

Множество $A$ рекурсивно тогда и только тогда, когда и $A$ и его дополнение $(N \diagdown A)$ - рекурсивно перечислимые множества.

В одну сторону.
Если множество $A$ и его дополнение $(N \diagdown A)$ рекурсивно перечислимые множества, то множество $A$ рекурсивно.
$C_R (x, \mu z[ C_{Ra} (x,z) \cdot C_{Rdop} (x,z)=0])$


$C_{Rdop} (x,z)$ - характеристическая функция для дополнения $(N \diagdown A)$.
$C_{Ra} (x,z)$ - характеристическая функция для $A$.

А в обратную как?

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

Ой, как многа букафф! Зачем они здесь?..

Не, ну вот видно, что человек изучает теорию в рамках чего-то суперпуперформального. И за деревьями не видит леса. И другим этот лес увидеть не даёт.

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

А по сути всё очень-очень просто!

gurukamu в сообщении #590681 писал(а):

...что значит "эффективно перечисляем"?

Это значит, что существует алгоритм перечисления. Другими словами, можно так запрограммировать машину Тьюринга, чтобы она, ничего не беря на вход, время от времени выписывала на ленте все числа из нашего множества. Неважно, в каком порядке, не важно, с повторениями или без.

gurukamu в сообщении #590722 писал(а):

А в обратную как?

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

Да очень просто! Получив на вход число, начинаем параллельно перечислять множество и его дополнение. И ждём, пока наше число не появится в одном из двух списков перечисляемых чисел. В зависимости от того, в каком из списков число появилось, даём ответ: "да" или "нет".

Обратно, пусть множество вычислимо. Как перечислять множество и дополнение к нему? Элементарно! Перебираем подряд все натуральные числа, и, рассматривая каждое число, за конечное время решаем, в какую из двух куч его кидать. И имеем процесс эффективного перечисления сразу двух множеств.

-- Пн июл 02, 2012 11:43:50 --

Прежде всего поймите одну простую, но фундаментальную вещь. Множество называется рекурсивно перечислимым, если его можно эффективно перечислять. То есть написать такую программу для машины, которая будет работать бесконечное число шагов и, время от времени, на некоторых шагах выдавать на гора числа, пополняя некий список. И вот этот список - это в точности список всех чисел из нашего множества.

А дальше всё уже можно формализовывать тысячью и одним способом. Но прежде чем кидаться в лес формальных определений, поймите суть!

-- Пн июл 02, 2012 11:51:15 --

(Оффтоп)

Если честно, то теорему Поста мне всегда было стыдно "теоремой" называть. Слишком пафосно оно звучит для столь элементарного утверждения. Подозреваю, что бедный Эмиль Пост давно покрылся в гробу несмываемой краской стыда.

[gurukamu]

Профессор Снэйп
Спасибо, становится более менее понятно!
То есть существует такая механическая процедура, которая позволяет вычислить значение функции, как только дан набор аргументов?

Цитата:

Если честно, то теорему Поста мне всегда было стыдно "теоремой" называть. Слишком пафосно оно звучит для столь элементарного утверждения. Подозреваю, что бедный Эмиль Пост давно покрылся в гробу несмываемой краской стыда.

Полностью согласен :)

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

gurukamu в сообщении #591297 писал(а):

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

Это Вы вот про что спросили?

Если про понятие вычислимой функции, то да: функция называется вычислимой, когда для неё существует такая процедура.

[gurukamu]

Профессор Снэйп
Хм.
Какие есть условия, которые мешают нам написать такую программу?

Цитата:

...которая будет работать бесконечное число шагов и, время от времени, на некоторых шагах выдавать на гора числа, пополняя некий список.

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

gurukamu в сообщении #591318 писал(а):

Какие есть условия, которые мешают нам написать такую программу?

Я не знаю, кто Вам там и где мешает.

А мне мешает постигнуть смысл Ваших глубокомысленных посланий полное отсутствие в них оного.

[AlexDem]

Размер программы должен быть конечен, например.

[gurukamu]

Профессор Снэйп
Уже неважно, экзамен сдал на 4:)

[Nemiroff]

(Оффтоп)

gurukamu в сообщении #592421 писал(а):

Уже неважно, экзамен сдал на 4:)

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

[gurukamu]

Nemiroff

(Оффтоп)

В том смысле неважно, что не надо постигать смысла.

Цитата:

"...мне мешает постигнуть смысл Ваших глубокомысленных посланий полное отсутствие в них оного

Ну, большинство предметов действительно в дальнейшем не нужны.

[svv]

(Оффтоп)

Основная масса человечества со страшной силой рвется назад в дикое состояние. Глупо пытаться этому препятствовать.

[JMH]

(Оффтоп)

Не только глупо но и вредно - дикость большинства увеличивает шансы меньшинства в эволюционной борьбе :)