множество всех алгоритмов перечислимо

[cscscs]

Нет, я согласен, что $S$ счетно. Про аксиому выбора это я просто так ляпнул не подумав

(Оффтоп)

Все, я спать. Завтра отвечу полностью.

[Nemiroff]

cscscs в сообщении #822912 писал(а):

Счетное объединение счетных множеств - это счетное множество, да, но это утверждение доказывается с помощью аксиомы выбора (и без неё, если мне не изменяет память, это нельзя доказать).

Оно, конечно, правда, только мало связано с темой.

[Sonic86]

cscscs в сообщении #822912 писал(а):

Счетное объединение счетных множеств - это счетное множество, да, но это утверждение доказывается с помощью аксиомы выбора (и без неё, если мне не изменяет память, это нельзя доказать).

Неее, что Вы.
Например, как перебрать $\mathbb{N}\times\mathbb{N}$? Последнее - счетное объединение счетных множеств вида $\mathbb{N}\times\{k\}$
$(1;1)$
$(1;2), (2,1)$
$(1;3), (2,2), (3,1)$
и т.п.
(графически тоже представьте себе процесс перебора и сами множества $\mathbb{N}\times\{k\}$)
С НАМ такая же фигня.

cscscs в сообщении #822869 писал(а):

Подождите, Вы путаете ту универсальную двухместную функцию с тем о чем я говорил. А я говорил про алгоритм, который ничего на вход не берет (или можно сказать пустое слово ему передается) и печатает все программы и только их.

А, да, действительно. Все равно не вижу ничего страшного.

cscscs в сообщении #822869 писал(а):

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

Ну тут, думаю, это уже такое свойство лекций - это вопрос к авторам. Считайте, что интуитивно понятно.

[Someone]

cscscs в сообщении #822654 писал(а):

Подскажите как доказывается, что множество всех программ, вычисляющих функции одного аргумента, перечислимо? Или дайте ссылку, где это доказывается, пожалуйста.

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

cscscs в сообщении #822709 писал(а):

Someone в сообщении #822678 писал(а):

Поскольку запись алгоритма — это слово определённой синтаксической структуры

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

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

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

Возвращаясь к условию задачи, нужно, опять же для конкретной реализации понятия "алгоритм", определить, что такое "функция одного аргумента". Тогда задача приобретёт определённость и её можно будет решать.

P.S. Прошу прощения, если написал то, что раньше уже было написано.
P.P.S. Что такое НАМ?

[cscscs]

Пусть $s(a)$ и $s(a')$ - две программы. Пусть $\gamma:\alpha(a)\to \alpha(a')$. Определим функцию $\Gamma_\gamma:S\to S$, которая применяет $\gamma$ ко всем символам $s(a)$, за исключением "$,$", "$\to$" и "$\cdot$". Если существует биективная $\gamma$ такая, что $\Gamma_\gamma(s(a))=s(a')$, то будем называть такие алгоритмы эквивалентными. Очевидно, что в каждом элементе фактор-множества существует единственная программа с алфавитом вида $\{1,...,n\}$. Обозначим множество всех таких программ через $S'$. Попробуем доказать, что $S'$ - перечислимое множество. И вот как это сделать? Каждый элемент $S'$ - это слово в бесконечном алфавите $\mathbb{N}\cup T$, где $T$ - множество символов "$,$", "$\to$" и "$\cdot$".

patzer2097 в сообщении #822909 писал(а):

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

Я хочу выяснить перечислимо оно или нет.

patzer2097 в сообщении #822909 писал(а):

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

Подскажите как это сделать?

patzer2097 в сообщении #822909 писал(а):

неужели у Вас вызывает сложности запись натурального числа в конечном алфавите?

Не вызывает. И что из этого следует? Что если я запишу каждое натуральное число в алфавите $B$, то отсюда сразу следует, что каждое слово из $S'$ можно будет закодировать в этом алфавите? Что-то мне так не кажется.

-- 05.02.2014, 12:03 --

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

Например, как перебрать $\mathbb{N}\times\mathbb{N}$? Последнее - счетное объединение счетных множеств вида $\mathbb{N}\times\{k\}$
$(1;1)$
$(1;2), (2,1)$
$(1;3), (2,2), (3,1)$
и т.п.
(графически тоже представьте себе процесс перебора и сами множества $\mathbb{N}\times\{k\}$)
С НАМ такая же фигня.

С рациональными числами понятно. И даже с $\mathbb{N}^n$ понятно. А вот с НАМ - нет. $S$ - это не $\mathbb{N}^n$. Может между ними и существует биекция, но надо еще доказать, что она вычислима.

-- 05.02.2014, 12:11 --

Someone в сообщении #822999 писал(а):

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

Формулировка такая. Поставим каждому НАМ (нормальному алгоритму Маркова) $a$ в соответствие строку $s(a)$: $a_1 ... a_k,X_1\to Z_1 Y_1,...,X_n\to Z_n Y_n$, где $\{a_1, ... ,a_k\}$ - алфавит данного НАМ не содержащий символов $,$, $\cdot$ и $\to$; $X_i$ и $Y_i$ - слова в данном алфавите; $Z_i$ - либо пустое слово, либо $\cdot$. Пусть $S=\{s(a): a \in A\}$, где $A$ - множество всех НАМ. Надо доказать, что $S$ - перечислимое множество. Т.е. предъявить такой НАМ, который бы печатал (в произвольном порядке и с произвольными промежутками времени) все элементы множества $S$ и только их.

[cscscs]

Мне кажется я немного приблизился к доказательству. В каждом элементе фактор-множества существует единственная программа с алфавитом вида $\{4,...,n\}$. Обозначим множество всех таких программ через $S''$. Обозначим "$,$" через 1, "$\to$" через 2 и "$\cdot$" через 3. Тогда каждый элемент $S''$ есть упорядоченная конечная последовательность натуральных чисел. Пусть $E(x_1,x_2,x_3,\dots,x_n) = 2^{x_1}\cdot 3^{x_2}\cdot 5^{x_3}\cdots p_n^{x_n}$.
Очевидно, что $E$ инъективно.
Итак, мы можем применить $E$ к любому $s''$ из $S''$.

[Someone]

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

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

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

Б.А.Кушнер. Лекции по конструктивному математическому анализу. "Наука", Москва, 1973.

Попробуйте почитать первую главу. Там много технической возни с нормальными алгорифмами Маркова.

[cscscs]

Someone в сообщении #823037 писал(а):

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

Хорошо, ну вот есть функция $E$, которую я определил выше. Таким образом мы можем все элементы $S''$ закодировать в виде каких-то натуральных чисел. И, очевидно, что существует НАМ, которая печатает все натуральные числа. Но нам нужно не все печатать, а только те натуральные числа $n$, что $E^{-1}(n)\in S''$. Вот в чем проблема.

Someone в сообщении #823037 писал(а):

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

Это можно сделать с помощью функции $E$, которую я определил выше. И, как мне кажется, $E$ можно реализовать в виде НАМ. Но проблема не исчезает: даже если мы реализуем НАМ, который последовательно печатает все значения $E(x_1,...,x_n)$, то это не будет удовлетворять условию того, что этот НАМ должен печатать ТОЛЬКО те $E(x_1,...,x_n)$, что $(x_1,...,x_n)\in S''$.

Someone в сообщении #823037 писал(а):

Б.А.Кушнер. Лекции по конструктивному математическому анализу. "Наука", Москва, 1973.

Попробуйте почитать первую главу. Там много технической возни с нормальными алгорифмами Маркова.

Спасибо, гляну.

[nikvic]

Между тем, задача о "правильной печати" невычислима.

Т.е. не существует алгоритма, который по нормальному алгорифму сообщает, перерабатывает ли он кучу палок (целое неотрицательное число) в кучу палок всегда, когда останавливается.

[cscscs]

Кстати, подытожу, что проблема на данный момент уже свелась к следующей: доказать, что множество натуральных чисел $E(S'')=\{E(s''):s''\in S''\}$ является перичислимым.

-- 05.02.2014, 14:55 --

nikvic в сообщении #823053 писал(а):

Между тем, задача о "правильной печати" невычислима.

Т.е. не существует алгоритма, который по нормальному алгорифму сообщает, перерабатывает ли он кучу палок (целое неотрицательное число) в кучу палок всегда, когда останавливается.

Не знаю, я брал определение отсюда ftp://ftp.mccme.ru/users/shen/logic/comput/part3.pdf

Цитата:

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

Вот именно в так смысле печать имелась в виду.

-- 05.02.2014, 15:12 --

Вообще, я создал тему эту потому, что читал эту книгу и дочитал до "доказательства" теоремы 6 о существовании универсальной функции:
ftp://ftp.mccme.ru/users/shen/logic/comput/part3.pdf
И у меня возник вопрос: почему без всяких обоснований подразумевается, что множество $\{p_0,p_1,...\}$ перечислимо?
А вообще меня интересовала эта теорема о существовании универсальной функции потому, что на ней основана Колмогоровская сложность. А она меня интересует потому что есть доказательства того, что сильный искусственный интеллект можно свести к умению сжимать данные, т.е. к вычислению КС. Но она не вычислима. Все это мне показалось подозрительным и я начал усиленно копать в надежде найти где-нибудь нестыковки, которые другие не заметили.

-- 05.02.2014, 15:38 --

Someone в сообщении #823037 писал(а):

Я думаю, что задачу нужно решать для алгоритмов, работающих в фиксированном алфавите.

Но тогда мы только эти нормальные алгоритмы закодируем, а не все. Разве нет? А нужно-то все. Т.е. мы сведём задачу к вопросу: существует ли вычислимая биекция между множеством нормальных алгоритмов в фиксированном алфавите и множество всех нормальных алгоритмов. Т.о. мы не сдвинулись с места, а просто переформулировали задачу.

[Sonic86]

cscscs в сообщении #823057 писал(а):

почему без всяких обоснований подразумевается, что множество $\{p_0,p_1,...\}$ перечислимо?

потому что это достаточно тривиально.

cscscs в сообщении #823057 писал(а):

Но тогда мы только эти нормальные алгоритмы закодируем, а не все. Разве нет? А нужно-то все.

Если угодно: множество всех алфавитов счетно: один счетный и счетное число конечных. Алгоритмы на алфавитах одинаковой мощности изоморфны. Потому можно считать, что множество всех алфавитом вполне упорядочено по включению, максимальный алфавит - счетный. Алгоритм на субалфавите является алгоритмом на алфавите, значит достаточно рассмотреть только счетный алгоритм, а patzer2097 Вам про него уже говорил.

(Оффтоп)

Вообще, я думаю, Вам уже все объяснили. Вам остается только фиксировать нормально определение и провести все выкладки (варианты выкладок уже приведены).

[cscscs]

Someone в сообщении #823037 писал(а):

Б.А.Кушнер. Лекции по конструктивному математическому анализу. "Наука", Москва, 1973.

Посмотрел. Там оказывается теорема 14 о существовании универсального алгоритма указывается до определения того, что такое перечислимое множество. И формулировка этой теоремы там совсем другая. Там говорится о том, что существует универсальный алгоритм над алфавитом $A\cup \{0|\delta \}$, но не для всех алгоритмов, а только для алгоритмов в алфавите $A$. А из той формулировки из той книги, на которую я выше ссылался, следует, что существует универсальный алгоритм для всех алгоритмов.

(Оффтоп)

Ещё раз убедился, что надо тщательнее выбирать литературу, а не лишь бы что.

Но доказательства теоремы 14 не приводится: сcылаются на монографию Маркова. Придется её почитать.
Но сомнений у меня уже в значительной степени поубавились, потому что то, что для всех алгоритмов в фиксированном алфавите существует универсальны алгоритм в бОльшем алфавите, даже интуитивно мне кажется верным. Потому как никакого печатания самого себя и прочий бред не требуется.

-- 05.02.2014, 19:52 --

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

потому что это достаточно тривиально.

Нет. Это вообще совсем не то утверждение, которое надо было приводить. Нам не нужно говорить о перечислимости множества всех программ. Нужно рассматривать только программы алгоритмов в каком-то фиксированном алфавите, а не всех вообще.

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

Алгоритмы на алфавитах одинаковой мощности изоморфны.

Что такое изоморфные алгоритмы?

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

Потому можно считать, что множество всех алфавитом вполне упорядочено по включению, максимальный алфавит - счетный.

А алфавит - это конечное множетсво. По определению.

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

Алгоритм на субалфавите является алгоритмом на алфавите, значит достаточно рассмотреть только счетный алгоритм

Что такое субалфавит и счетный алгоритм?

[patzer2097]

cscscs в сообщении #823057 писал(а):

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

Вам уже $100$ раз сказали, что алгоритмические вычисления можно производить только в фиксированных конечных алфавитах
если Вас никакой конечный раз и на всегда фиксированный алфавит не устраивает, то задача Ваша никакого решения (и даже адекватной формулировки) не допускает

[cscscs]

patzer2097 в сообщении #823158 писал(а):

Вам уже $100$ раз сказали, что алгоритмические вычисления можно производить только в фиксированных конечных алфавитах

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

patzer2097 в сообщении #823158 писал(а):

если Вас никакой конечный раз и на всегда фиксированный алфавит не устраивает, то задача Ваша никакого решения (и даже адекватной формулировки) не допускает

С формулировками я уже разобрался здесь post823131.html#p823131

[patzer2097]

cscscs в сообщении #823161 писал(а):

Что мешает определить НАМ, который будет иметь алфавит, выходящий за рамки зафиксированного? Ничто не мешает, по определению НАМ.

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

Тем не менее, работу любой НАМ можно смоделировать в конечном алфавите. Например, считать, что любая НАМ оперирует "алфавитом", содержащим первые несколько слов из $a_1,\ldots,a_{953},\ldots$ и ничто больше. Обратите внимание, что все эти $a_1,\ldots,a_{953},\ldots$ мы можем записать (и постоянно это делаем) в конечном алфавите $\{a,0,1,2,3,4,5,6,7,8,9\}$.