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

[Nemiroff]

Duku в сообщении #822820 писал(а):

Забавно, тогда $2^n$ или $x^n$ - не функция, т.к. $\sqrt {n}$ не единственное.

Это вы сейчас что-то не то сказали. $x^n$ --- это выражение странное, а вот $2^n$ --- функция. От $n$. $n^2$ тоже.

[Duku]

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

вот $2^n$ --- функция. От $n$. $n^2$ тоже.

А если $n=2$ ? Каждый элемент области значений имеет два прообраза ?

[Nemiroff]

Duku в сообщении #822841 писал(а):

А если $n=2$ ? Каждый элемент области значений имеет два прообраза ?

М-м-м, я вас не понимаю.
$n^2$ --- это функция из $\mathbb{R}$ в $\mathbb{R}$. А потому --- это есть подмножество $\mathbb{R} \times \mathbb{R}$, причём для любого $n\in \mathbb{R}$ существует единственное $y\in\mathbb{R}$ (равное $n^2$) такое, что $\langle n,y \rangle$ принадлежит функции. Если рисовать это множество на плоскости, получится парабола.

[cscscs]

Попробую доказать в контексте нормальных алгоритмов.
Значит, любой НАМ $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$.
Пусть $A$ - множество всех НАМ. Пусть $S=\{s(a): a \in A\}$. Попробуем найти такую биективную вычислимую всюду определенную функцию $f:S\to\mathbb{N}$, чтобы однозначно занумеровать все строки из $S$.
И вот как её найти?

[patzer2097]

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

Попробую доказать

ну Вы бы сначала задачу сформулировали.. А то иначе эта тема чем-то вроде блога оказывается Главное, что (по-моему) тут непонятно, что Вы называете вообще программой.

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

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

[cscscs]

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

ну Вы бы сначала задачу сформулировали.

Я думал это логически следует из обсуждения
Доказать, что существует марковский алгоритм, который печатает (в произвольном порядке и с произвольными промежутками времени) вообще все программы и только их.
Программа (например) - это элемент множества $S$, которое я определил выше.

Очевидно, что существует марковский алгоритм, который печатает все натуральные числа. Поэтому, если бы мы могли предъявить такую функцию $f$, которую я описал выше, то теорема была бы доказана. (Если только я тут не заблуждаюсь). Таким образом вопрос свелся к тому, существует ли такая $f$.

-- 04.02.2014, 23:37 --

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

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

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

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

универсальная функция двуместна

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

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

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

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

[patzer2097]

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

Программа (например) - это элемент множества $S$, которое я определил выше.

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

строки $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\}$.

то есть Вы хотите доказывать, что множество строк указанного вида перечислимо, я правильно Вас понял? и в чем здесь может быть проблема? Упорядочиваем все вообще возможные строки длины $l$ лексикографически, читаем по одной; если такая как Вы хотите, выводим на печать, если нет, то нет; идем к следующей. Когда все строки длины $l$ просмотрели, смотрим строки длины $l+1$.

[cscscs]

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

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

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

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

-- 04.02.2014, 23:48 --

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

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

В виде схем только встречал, но я их переделал в строки.

-- 04.02.2014, 23:52 --

Duku в сообщении #822820 писал(а):

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

Квайн-программа выводит только саму себя. А та универсальная программа впридачу.
Опрационные системы работают на реальных машинах. А они являются не MT, а скорее https://en.wikipedia.org/wiki/Linear_bounded_automaton

-- 04.02.2014, 23:56 --

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

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

Да.

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

Упорядочиваем все вообще возможные строки длины $l$ лексикографически

Что такое "все вообще возможные строки"? В каком алфавите?

[patzer2097]

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

В каком алфавите?

в том, в котором Вы элементы множества $S$ задаете

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

Что "все вообще возможные строки"?

вообще все строки, не исключая $\rightarrow\rightarrow.\rightarrow$ и подобных

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

[cscscs]

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

в том, в котором Вы элементы множества $S$ задаете

Вы наверное не знаете, что такое НАМ. У каждого НАМ $a$ свой алфавит $\alpha(a)$. Да, я согласен, что $s(a)$ - это строка в алфавите $\alpha(a)$, к которому добавили символы $,$,$\to$ и $\cdot$. Но этот алфавит для каждого $s(a)$ свой. И Вы рассуждали в таком ключе, будто существует общий алфавит для всех элементов $s(a)$ при любом $a$. Для меня не очевидно, что такой алфавит существует. Можно сказать, что этим алфавитом является объединение всех $\alpha(a)$, но это множество не явлсяется конечным. Поэтому не может считаться алфавитом.

[patzer2097]

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

Можно сказать, что этим алфавитом является объединение всех $\alpha(a)$

что является алфавитом, нужно сказать. нужно явно его зафиксировать.

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

но это множество не явлсяется конечным

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

даже если Ваше множество $\alpha(a)$ бесконечно, мы должны научиться кодировать его элементы в конечном алфавите. Что, впрочем, сделать очень легко - ведь как-то же мы упоминаем эти $a_i$ в наших сообщениях

[cscscs]

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

и нужно сказать. и явно его зафиксировать.

Я могу доказать Вам, что оно бесконечно, если хотите. Алфавит - это, по определению, конечное множество. Для каждого алфавита можно построить какой-нибудь НАМ, по определению НАМ. Каждое конечное подмножество $\{1,...,n \}$ натуральных чисел является алфавитом. Значит для каждого из них существует НАМ. Но объединение всех этих множеств является множеством натуральных чисел, которое счетно, а не конечно.

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

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

Надо бы еще доказать, что это можно сделать. Я уже показал, что с объединением ничего не получится.

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

даже если Ваше множество $\alpha(a)$ бесконечно

Оно конечно по определению НАМ.

[patzer2097]

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

Оно конечно по определению НАМ.

OK, я имел в виду "объединение всех $\alpha(a)$", оставаясь в Ваших терминах.

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

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

Но объединение всех этих множеств является множеством натуральных чисел, которое счетно, а не конечно.

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

[cscscs]

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

число НАМ с 1-м правилом счетно

Кстати, спорный момент. Для каждого фиксированного алфавита $\{1,...,n\}$ существует счетное число НАМ с одним правилом. Счетное объединение счетных множеств - это счетное множество, да, но это утверждение доказывается с помощью аксиомы выбора (и без неё, если мне не изменяет память, это нельзя доказать).

[patzer2097]

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

Кстати, спорный момент. Для каждого фиксированного алфавита $\{1,...,n\}$ существует счетное число НАМ с одним правилом. Счетное объединение счетных множеств - это счетное множество, да, но это утверждение доказывается с помощью аксиомы выбора (и без неё, если мне не изменяет память, это нельзя доказать).

Вас послушать, так мы и счетность рациональных чисел без выбора не докажем

-- Ср фев 05, 2014 00:32:56 --

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