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

[vladislavmsk77]

Задание:
Доказать, что прообраз рекурсивно перечислимого множества при отображении рекурсивной функции рекурсивно перечислим.

Раздали задания, пытаюсь доказать:
Определяем рекурсивно перечислимое множество в терминах вычислимой рекурсивной функции(например, как область определения вычислимой рекурсивной функции)
Функция $f$ с натуральными аргументами и значениями вычислима тогда и только тогда, когда ее график является перечислимым множеством пар натуральных чисел. Пусть $f$ вычислима. Тогда существует алгоритм, перечисляющий ее область определения, то есть печатающий все $x$, на которых $f$ определена. Если теперь для каждого из таких x вычислять еще и значение $f(x)$, получим алгоритм, перечисляющий множество $F$. Прообраз множества $A$ при $f$ определяется как множество всех тех $n$, при которых $f(n) $ определено и принадлежит $A$.
Теорема:Прообраз перечислимого множества при вычислимой функции перечислимы.


Ребят, помогите пожалуйста!!!
3 года назад сдавал зачет по матлогике, в этом году выяснятся, что должен был быть зачет с оценкой...
Заранее огромное спасибо!!!

[_hum_]

может, по определению - попробовать построить перечисляющий алгоритм на основе того, что у вас уже есть перечисляющий алгоритм образа, и сама отображающая функция задается алгоритмически?

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

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- отсутствуют собственные содержательные попытки решения задач(и).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Anton_Peplov]

По-моему, вы не указали простого определения, которое здесь все решает.
Множество называется $B$ перечислимым, если существует такой алгоритм $A$, получающий на вход натуральные числа, что:
1. Для любого натурального числа на входе результат принадлежит $B$.
2. Для любого элемента $b \in B$ найдется такое натуральное $n$, что, получив на вход $n$, алгоритм выдаст $b$.
Иными словами, применяемый ко всем натуральным числам подряд, такой алгоритм:
а) ни на одном числе не зациклится
б) будет выдавать в результате только элементы $B$
в) рано или поздно выдаст любой элемент $B$.

Этот алгоритм называется алгоритмом, перечисляющим $B$.

По условию у нас есть алгоритм, перечисляющий $B$ и алгоритм, перечисляющий график функции $f$, т.е. множество всех пар $\{x, f(x)\}$. Сделайте из них алгоритм, перечисляющий прообраз $B$. Это просто.