Пусть

и

- две программы. Пусть

. Определим функцию

, которая применяет

ко всем символам

, за исключением "

", "

" и "

". Если существует биективная

такая, что

, то будем называть такие алгоритмы эквивалентными. Очевидно, что в каждом элементе фактор-множества существует единственная программа с алфавитом вида

. Обозначим множество всех таких программ через

. Попробуем доказать, что

- перечислимое множество. И вот как это сделать? Каждый элемент

- это слово в бесконечном алфавите

, где

- множество символов "

", "

" и "

".
Еще раз. Если Вы хотите говорить о перечислимости множества

Я хочу выяснить перечислимо оно или нет.
то Вы должны тем или иным образом научиться кодировать любую строку из множества

в каком-то глобальном конечном алфавите (общем для всех НАМ). И это легко.
Подскажите как это сделать?
неужели у Вас вызывает сложности запись натурального числа в конечном алфавите?
Не вызывает. И что из этого следует? Что если я запишу каждое натуральное число в алфавите

, то отсюда сразу следует, что каждое слово из

можно будет закодировать в этом алфавите? Что-то мне так не кажется.
-- 05.02.2014, 12:03 --Например, как перебрать

? Последнее - счетное объединение счетных множеств вида




и т.п.
(графически тоже представьте себе процесс перебора и сами множества

)
С НАМ такая же фигня.
С рациональными числами понятно. И даже с

понятно. А вот с НАМ - нет.

- это не

. Может между ними и существует биекция, но надо еще доказать, что она вычислима.
-- 05.02.2014, 12:11 --Я вдруг обратил внимание на неоднозначность формулировки задачи. В заголовке написано "множество всех алгоритмов", а в тексте — "множество алгоритмов, вычисляющих функции одного аргумента". Это разные вещи, и второе запросто может оказаться не перечислимым, при перечислимом первом. Как определить по записи алгоритма, что он делает?
Формулировка такая. Поставим каждому НАМ (нормальному алгоритму Маркова)

в соответствие строку

:

, где

- алфавит данного НАМ не содержащий символов

,

и

;

и

- слова в данном алфавите;

- либо пустое слово, либо

. Пусть

, где

- множество всех НАМ. Надо доказать, что

- перечислимое множество. Т.е. предъявить такой НАМ, который бы печатал (в произвольном порядке и с произвольными промежутками времени) все элементы множества

и только их.