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

[Sonic86]

(patzer2097)

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

только если $A$ пусто но у ТС - свои определения

А, прошу прощенья, я тупанул Я думал, что $f\in A^B \Leftrightarrow \operatorname{Dom}(f)\subseteq B, \operatorname{Im}(f)\subseteq A$

[Maslov]

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

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

а ответьте, пожалуйста, что значит "вычислять функции одного аргумента"? Значит ли это, что наши программы должны как минимум останавливаться на любом входе?

Нет. Если значение функции от данного аргумента не определено, то либо алгоритм не останавливается, либо останавливается, но ничего не печатает.

Но хотя бы на одном входе алгоритм, "вычисляющий функцию одного аргумента", должен останавливаться?

[nikvic]

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

Итак. Значит вопрос сводится к следующему. Доказать, что существует марковский алгоритм, который печатает (в произвольном порядке и с произвольными промежутками времени) вообще все марковские алгоритмы и только их. Как это доказывать - не понятно.

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

[patzer2097]

(Sonic86)

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

А, прошу прощенья, я тупанул Я думал, что $f\in A^B \Leftrightarrow \operatorname{Dom}(f)\subseteq B, \operatorname{Im}(f)\subseteq A$

да.. кстати, никогда не понимал аргумента из недавней темы в пользу $0^0=1$ гласящего, что "количество отображений из $n$-элементного множества в $m$-элементное равно $m^n$". Ведь при $m=5$ и $n=0$ таких отображений нет, то есть, их не $5^0=1$, а $0$

[cscscs]

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

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

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

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

Ааа, так там явно задан способ записи функций - запись вида $f(x_1,...,x_n)$

Что-то я там (ftp://ftp.mccme.ru/users/shen/logic/comput/part3.pdf) такого не заметил. Может не внимательно читал. До 16 страницы там все функции от одного аргумента.

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

Ну вот, ТС удалил свой пост

Потому что перепутал кому svv отвечал.

-- 04.02.2014, 20:27 --

Maslov в сообщении #822775 писал(а):

Но хотя бы на одном входе алгоритм, "вычисляющий функцию одного аргумента", должен останавливаться?

Нет, нигде не определённая функция тоже вычислима.

[Nemiroff]

(Оффтоп)

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

Ведь при $m=5$ и $n=0$ таких отображений нет, то есть, их не $5^0=1$, а $0$

Есть, и оно ровно одно --- пустое множество.

[patzer2097]

(Nemiroff)

Nemiroff в сообщении #822787 писал(а):

(Оффтоп)

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

Ведь при $m=5$ и $n=0$ таких отображений нет, то есть, их не $5^0=1$, а $0$

Есть, и оно ровно одно --- пустое множество.

тут я не уверен, но ладно. Дело еще вот в чем: тогда и из пустого множества в $\{1,2,3\}$ у нас есть пустая функция, в то время как $0^3\neq1$.

[cscscs]

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

Никакой алгоритм напечатать нельзя. Можно напечатать программу для выбранного языка алгоритмов.

Да, точно.

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

Для Марковских проще всего - записи в алфавите из двух букв, которые устроены проще, чем ... не помню термина... изображения.

Не понял, Вы предлагаете создать алгоритм, который бы печатал все последовательности из нулей и единиц? Так вопрос не в этом. В существовании такого алгоритма у меня сомнении нет. Вопрос в другом. Нужен алгоритм, который бы печатал ТОЛЬКО программы. И причем все.

[Nemiroff]

(Оффтоп)

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

Дело еще вот в чем: тогда и из пустого множества в $\{1,2,3\}$ у нас есть пустая функция, в то время как $0^3\neq1$.

Из пустого как раз есть --- но это $3^0$. Вы, наверное, имеете в виду, что в пустое множество функция есть, а $0^3$ при этом равно нулю. Так вот нет --- в пустое множество не из пустого функций нет.
Смотрите, функция из $A$ в $B$ --- это некоторое подмножество декартова произведения $A\times B$. Если хотя бы одно из множеств пусто, единственным кандидатом на функцию будет пустое множество. Но есть дополнительное условие (я из головы корректно не сформулирую, посмотрите в одной из тем, на которые ссылается предпоследнее сообщение из нашего предыдущего обсуждения). Так вот, если $A$ пусто, то любая функция удовлетворяет условию --- поэтому один кандидат дает одну функцию. А если $A$ не пусто, а $B$ при этом пусто, то никакая функция не удовлетворяет условию. В том числе пустое множество.

[Sonic86]

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

Что-то я там (ftp://ftp.mccme.ru/users/shen/logic/comput/part3.pdf ) такого не заметил. Может не внимательно читал. До 16 страницы там все функции от одного аргумента.

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

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

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

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

(злостный оффтоп)

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

то есть, их не $5^0=1$, а $0$

$\{\}$ - это отображение

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

Нужен алгоритм, который бы печатал ТОЛЬКО программы. И причем все.

Да просто перечисляем все НАМ явно: алфавит для НАМ конечен, число правил в каждом НАМ конечно, значит число НАМ с 1-м правилом счетно, с 2-я правилами счетно, ... - берем и перечисляем их по очереди как пары натуральных чисел.

[Nemiroff]

(Оффтоп)

А впрочем, нашёл, цитирую:

Цитата:

Определение. Функцией из множества $A$ в множество $B$ называется подмножество $f \subseteq A \times B$, такое что для любого $a \in A$ существует единственное $b \in B$, для которого $\langle a,b \rangle \in f$.

[patzer2097]

(Nemiroff)

ах, да. мы хотим говорить, что существует $|B|^{|A|}$ функций из $A$ в $B$, а не $|A|^{|B|}$, как я подумал. прошу прощения.

[Maslov]

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

Нужен алгоритм, который бы печатал ТОЛЬКО программы. И причем все.

Тогда объясните, что Вы понимаете под программой.

Любая ли машина Тьюринга является программой? Если нет, то какая не является?

[nikvic]

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

Не понял, Вы предлагаете создать алгоритм, который бы печатал все последовательности из нулей и единиц?

Нет, более осмысленный. Прочтите где-нибудь, что такое запись нормального алгорифма.

[Duku]

Nemiroff в сообщении #822802 писал(а):

А впрочем, нашёл, цитирую:

Цитата:

Определение. Функцией из множества $A$ в множество $B$ называется подмножество $f \subseteq A \times B$, такое что для любого $a \in A$ существует единственное $b \in B$, для которого $\langle a,b \rangle \in f$.

Забавно, тогда $n^2$ или $2^n$ - не функция, т.к. $\sqrt {n}$ не единственное.
Любопытно, какие теоремы опираются на то, что $2^n$ - функция ?

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

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

Из существования универсальной МТ (и квайн-программ), попросту операционных систем, следует, что таких УП бесконечное множество.
Кстати, из тех же соображений, следует, что нельзя определить, чем является произвольный текст : кодом (на некотором, неопределенном языке) или данными (на другом неопределенном языке).