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

[Someone]

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

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

Там ещё есть теорема о переводе (пункт 5, теорема 1), которая позволяет алгоритм в любом алфавите перевести в алгоритм в двухбуквенном алфавите. Этого, я думаю, достаточно для вашей задачи. Даже если перечисляющий алгоритм будет использовать более широкий алфавит.

[cscscs]

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

Там ещё есть теорема о переводе (пункт 5, теорема 1), которая позволяет алгоритм в любом алфавите перевести в алгоритм в двухбуквенном алфавите.

Там фиксируется алфавит $A$ и далее с помощью него однозначно строятся алфавиты $A_1$ и $A_2$ и описывается некоторый однозначный способ кодирования каждого нормального алгоритма в алфавите $A_1$ в какой-то нормальный алгоритм в алфавите $A_2$, т.е. некоторая инъективная функция $f_A:K(A_1)\to K(A_2)$, где под $K(X)$ я подразумеваю множество всех нормальных алгоритмов в алфавите $X$. Нет сомнений, что при каждом фиксированном $A$, для $f_A$ есть соответствующий ей нормальный алгоритм.
Пусть $W$ - множество всех алфавитов.
Доказательство теоремы основано на том, что можно любому алфавиту $A$ однозначно сопоставить $f_A$, т.е. что существует инъекция $g(A)=f_A$ для всех $A\in W$. Но возникает сильное сомнение, что для $g$ можно указать соответствующий ей нормальный алгоритм. Такого нормального алгоритма не существует, потому что он должен был бы обладать бесконечным алфавитом.

[Someone]

Алфавит $\text{A}$, в частности, может быть пустым. И в рассуждениях между теоремами 13 и 14 как раз этот вариант используется (там есть слова "сохраняемый алфавит в данном случае пуст"). Алфавит $\text{A}$ в теореме 1 — это как раз "сохраняемый алфавит", который не кодируется. В теореме 14 этот "сохраняемый алфавит" взят пустым, а $\text{A}=\{\gamma_1,\gamma_2,\ldots,\gamma_n\}$ кодируется алфавитом $\{\alpha,\beta\}=\{\vert,0\}$.

[cscscs]

Я неправильно написал свое предыдущее сообщение. Я вот что хотел сказать.
В той книге Кушнера выясняется истинно ли утверждение, что можно все алфавиты свести к одному алфавиту. Обозначим это утверждение через Y. Для доказательства Y делается следующее.
Пусть $\mathbb{A}$ - множество всех алфавитов, количество букв в которых не меньше шести. Будем обозначать через $\text{A}^*$ множество слов в алфавите $\text{A}$. Пусть $f:\mathbb{A}\to \bigcup_{\text{A}\in \mathbb{A}}{\text{A}^*}$ такая, что для любого $\{\gamma_1,...,\gamma_n\}\in \mathbb{A}$: $f(A)$ есть слово $\gamma_1 ... \gamma_n$. Пусть $\text{A}=\{\gamma_1,...,\gamma_n\}\in \mathbb{A}$. Обозначим $\gamma_1$ через $\to$, $\gamma_2$ через $\cdot$, $\gamma_3$ через $\text{|}$, $\gamma_4$ через $\alpha$ и $\gamma_5$ через $\beta$. Пусть $\mathfrak{A}^{\text{И}}_{\text{A}}$ есть следующее слово в алфавите $\text{A}$:

$$ \alpha\to \cdot \alpha\beta\alpha |\beta\to \cdot \alpha\beta\beta\alpha |\gamma_6 \to \cdot \alpha\beta\beta\beta\alpha| ... | \gamma_n \to \cdot \alpha\underbrace{\beta ...\beta}_{n-3 \text{ раз}}\alpha \\ $$

Но остаётся не выясненным существует ли такой алгоритм $\mathfrak{B}$, что для любого $X\in f(\mathbb{A})=\{f(\text{A}):\text{A}\in\mathbb{A}\}$ верно $\mathfrak{B}(X)=\mathfrak{A}^{\text{И}}_{f^-1(X)}$. Потому что утверждение, что $f(\mathbb{A})$ можно представить как множество слов в некотором конечном алфавите, равносилено утверждению Y, которое мы ещё не доказали.

Т.е. я хочу сказать, что в книге Кушнера рассуждение, которое преподносится как доказательство Y, по сути основано на неявном предположении, что Y уже верно.

[cscscs]

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

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

Для нее фиксированном? Или Вы говорите про один фиксированный алфавит для всех алгоритмов?
Если первое, то я согласен. Если второе, то я не уверен. Потому что тогда получается, что есть ещё много "прог", которые "ничего не вычисляют". Что Вы тогда понимаете под "прога которая что-то вычисляет" и под "прога которая ничего не вычисляет"?

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

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

Вот с этим я согласен.

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

Тем не менее, работу любой НАМ можно смоделировать в конечном алфавите. Например, считать, что любая НАМ оперирует "алфавитом", содержащим первые несколько слов из $a_1,\ldots,a_{953},\ldots$ и ничто больше.

Что такое $a_1,\ldots,a_{953},\ldots$?

[Someone]

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

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

Я даже не могу догадаться, откуда Вы это переписали. Я имел в виду главу 1, § 1, пункт 5, теорему 1, которая называется теоремой о переводе. Она совершенно элементарна, и из неё тривиально следует, что любой нормальный алгорифм в любом алфавите можно очень просто перевести в двухбуквенный алфавит.

[cscscs]

Someone
Похоже Вы меня не поняли. Тогда я сейчас сформулирую всё очень строго. При этом то, что дальше будет написано, не имеет прямого отношения к книге Кушнера. Я просто дам определения и докажу несколько теорем.

Слова будем обозначать большими латинскими буквами.
Пустое слово будем обозначать через $\Lambda$.
Множества будем обозначать большими латинскими буквами с чертой: $A'$, $B'$, $C'$, ..., $Z'$.
Функции будем обозначать маленькими латинскими буквами, кроме $i$, $j$ и $n$.

Возьмём алфавит $\{0,1\}$. Пусть
$B$ - это слово $010$,
$C$ - это слово $0110$,
$D$ - это слово $01110$,
$E$ - это слово $011110$,
$F$ - это слово $0111110$.

Определение множества слов $S'$:
1) $\Lambda$, $B$ и $C$ принадлежат $S'$.
2) Если $X\in S'$, то $BX\in S'$ и $CX\in S'$.
3) Ничто другое $S'$ не принадлежит.

Определение множества программ $P'$.
Программа - это слово в алфавите $\{0,1\}$ вида $X_1DZ_1Y_1FX_2DZ_2Y_2F...FX_n DZ_n Y_n$, где $n\in\mathbb{N}$ и $X_i\in S'$, $Y_i\in S'$, $Z_i\in \{\Lambda, E\}$ $\forall i:1\le i\le n$.

Определение универсальной функции $u:P'\times S'\to S'$.
Пусть $A=X_1DZ_1Y_1FX_2DZ_2Y_2F...FX_n DZ_n Y_n\in P'$ и $W\in S'$.
1) Если $\forall i:1\le i\le n$ слово $W$ не содержит слова $X_i$, то $u(A,W)=W$.
2) Если $W=KX_i M$, $K\in S'$, $M\in S'$, $1\le i\le n$, $\forall T\in S'$ $\;\forall V\in S'\setminus \{\Lambda\}\forall\;$ $j:1\le j\le n$ верно $KX_i\neq TX_jV$ и, если $i\neq 1$, то $\forall j:1\le j< i$ $\; X_i\neq X_j$,
то тогда

$$u(A,W)= \left\{ \begin{array}{rcl} KY_iM & , & Z_i=E \\ u(A, KY_iM) & , & Z_i=\Lambda \\ \end{array} \right.. $$

Определение функции $g:\{\Lambda,B,C,D,E,F\}\to S'$.
$g(\Lambda)=\Lambda$,
$g(B)=BCB$,
$g(C)=BCCB$,
$g(D)=BCCCB$,
$g(E)=BCCCCB$,
$g(F)=BCCCCCB$.

Если даны две функции $q:X'\to Y'$ и $l:V' \to Z'$, где $X',Y',V',Z'$ есть какие-то множества слов, то под записью $q(K)l(R)$ будем понимать слово $MN\in Y'\cup Z'$ такое, что $q(K)=M$ и $l(R)=N$.

Определение функции $h:S'\to S'$.
$h(\Lambda)=\Lambda$,
$\forall X\in S':h(BX)=g(B)h(X)$,
$\forall X\in S':h(CX)=g(C)h(X)$.

Определение функции перевода $f:P'\to S'$.
Пусть $A=X_1DZ_1Y_1FX_2DZ_2Y_2F...FX_n DZ_n Y_n\in P'$. Тогда $f(A)=h(X_1)g(D)g(Z_1)h(Y_1)g(F)h(X_2)g(D)g(Z_2)h(Y_2)g(F)...g(F)h(X_n) g(D)g(Z_n) h(Y_n)$.

Теорема 1. Функция $f$ инъективна, т.е. $\forall A_1\in P' \; \forall A_2\in P':\; A_1\neq A_2\Rightarrow f(A_1)\neq f(A_2)$
Доказательство. Очевидно следует из определений функций $g$, $h$ и $f$ $\blacksquare$

Теорема 2. $P'\not\subset S'$.
Доказательство. По определению $P'$ слово $D\in P'$. Покажем, что $D\not\in S'$. Т.к. $01110\neq 010$ и $01110\neq 0110$, то $D\neq B$ и $D\neq C$. Длина слов $XB$ и $XC$, где $X\in S'$, не меньше длины слова $X$ плюс длина слова $B$, т.е. три. Значит длина любого слова из $S'\setminus \{\Lambda,B,C\}$ не меньше шести. Но длина слова $D$ равна пяти. Значит $D\not\in S'$. Откуда следует, что $P'\not\subset S'$ $\blacksquare$

Теорема 3. Не существует такой программы $A\in P'$, что $\forall W\in P':u(A,W)=f(W)$.
Доказательство. По определению функция $u:P'\times S'\to S'$. Из теоремы 2 следует, что $P'\not\subset S'$, т.е. существует такое $R\in P'$, что $R\not\in S'$. Поэтому $\forall A\in P'$ значение $u(A,R)$ не определено и значит не может быть равным $f(R)$ $\blacksquare$

[Sonic86]

(эээээээээээ)

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

Определение множества слов $S'$:
1) $\Lambda$, $B$ и $C$ принадлежат $S'$.
2) Если $X\in S'$, то $BX\in S'$ и $CX\in S'$.
3) Ничто другое $S'$ не принадлежит.

Короче, $S'=\{B,C\}^*$.

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

Определение множества программ $P'$.
Программа - это слово в алфавите $\{0,1\}$ вида $X_1DZ_1Y_1FX_2DZ_2Y_2F...FX_n DZ_n Y_n$, где $n\in\mathbb{N}$ и $X_i\in S'$, $Y_i\in S'$, $Z_i\in \{\Lambda, E\}$ $\forall i:1\le i\le n$.

НАМы.

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

Определение универсальной функции $u:P'\times S'\to S'$.
Пусть $A=X_1DZ_1Y_1FX_2DZ_2Y_2F...FX_n DZ_n Y_n\in P'$ и $W\in S'$.
1) Если $\forall i:1\le i\le n$ слово $W$ не содержит слова $X_i$, то $u(A,W)=W$.
2) Если $W=KX_i M$, $K\in S'$, $M\in S'$, $1\le i\le n$, $\forall T\in S'$ $\;\forall V\in S'\setminus \{\Lambda\}\forall\;$ $j:1\le j\le n$ верно $KX_i\neq TX_jV$ и, если $i\neq 1$, то $\forall j:1\le j< i$ $\; X_i\neq X_j$,
то тогда

$$u(A,W)= \left\{ \begin{array}{rcl} KY_iM & , & Z_i=E \\ u(A, KY_iM) & , & Z_i=\Lambda \\ \end{array} \right.. $$

Короче, $u$ - это эмулятор действия НАМ-а $A$ на строку $W$.

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

Определение функции $h:S'\to S'$.
$h(\Lambda)=\Lambda$,
$\forall X\in S':h(BX)=g(B)h(X)$,
$\forall X\in S':h(CX)=g(C)h(X)$.

$h$ - индуцирование отображения $g$ c $\{B,C,D,E,F\}$ на $\{B,C,D,E,F\}^*$,, ограниченное на $\{B,C\}^*$.

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

Определение функции перевода $f:P'\to S'$.
Пусть $A=X_1DZ_1Y_1FX_2DZ_2Y_2F...FX_n DZ_n Y_n\in P'$. Тогда $f(A)=h(X_1)g(D)g(Z_1)h(Y_1)g(F)h(X_2)g(D)g(Z_2)h(Y_2)g(F)...g(F)h(X_n) g(D)g(Z_n) h(Y_n)$.

$f$ - индуцирование отображения $g$ c $\{B,C,D,E,F\}$ на $\{B,C,D,E,F\}^*$, ограниченное на $P'$.

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

Теорема 3. Не существует такой программы $A\in P'$, что $\forall W\in P':u(A,W)=f(W)$.

Видимо, опечатка: $\forall W\in S'$...
А нет, в этом соль теоремы 3. Можно было проще сказать: $u$ определена только на $P'\times S'$, значит она не определена на $P'\times P'$.

И что? Зачем я это прочитал???

З.Ы.: А еще текст похож на программы на Васике. Вот почему нельзя было написать $g(D)=BC^3B, A=\prod\limits_{k=1}^nX_kDZ_kY_k$ например...
Или вот:

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

$K\in S'$, $M\in S'$,

можно же написать $K,M\in S'$...

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

Пусть $A=X_1DZ_1Y_1FX_2DZ_2Y_2F...FX_n DZ_n Y_n\in P'$. Тогда $f(A)=h(X_1)g(D)g(Z_1)h(Y_1)g(F)h(X_2)g(D)g(Z_2)h(Y_2)g(F)...g(F)h(X_n) g(D)g(Z_n) h(Y_n)$.

Пусть $A=\prod\limits_{k=1}^nX_kDZ_kY_k$, тогда $f(A)=h(A)=\prod\limits_{k=1}^nh(X_k)h(D)h(Z_k)h(Y_k)$. Ну не максимально лаконично, но лаконичнее...

[cscscs]

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

И что?

Для $f$ не существует вполне эквивалентной программы.

[Sonic86]

У Вас $u$ определена только на $P'\times S'$. Т.е. Вы это закладываете явно в определение $u$, а потом спустя 3 километра достаете в качестве теоремы.
Мне лень на содержательный язык переводить, но это всяко тавтология.

[cscscs]

Sonic86
Да это не про функцию $u$ был текст. Т.е. он, конечно же, и про неё тоже, но я имею в виду, что это всё писалось не для того, чтобы сказать, что $u$ не определена на $P'\times P'$. Ключевая вещь там - это функция перевода $f$. И то, что для неё верна теорема 3.

[Someone]

cscscs, Вы не в ту сторону копаете. Ваша задача — выяснить, перечислимо ли множество всех алгоритмов. Если не фиксировать алфавит, то задача не разрешима, потому что перечисляющий алгоритм должен уметь работать со всеми алфавитами, с которыми работают перечисляемые алгоритмы, а это невозможно, так как нормальный алгорифм Маркова имеет конечное описание и, следовательно, в этом описании встречается только конечное множество символов, а если говорить о машине Тьюринга, то она управляется конечным автоматом, который имеет конечное множество состояний и распознаёт конечное множество символов. Поэтому необходимо ограничиться одним алфавитом.
Но здесь, естественно, возникает вопрос, зависит ли объём понятия "алгоритм" от используемого алфавита. Теорема о переводе как раз показывает, что не зависит (исключая тривиальный случай однобуквенного алфавита). Мы кодируем все нужные символы в двухбуквенном алфавите словами вида $\alpha\beta\beta\ldots\beta\alpha$, "переводим" схему алгоритма и исходные данные, потом "запускаем" алгоритм. "Переведённый" алгоритм просто по шагам воспроизводит работу исходного алгоритма, получая результат, соответствующий "переводу" результата работы исходного алгоритма.

Поручать "перевод" туда и обратно каким-то алгоритмам нельзя по той же причине, о которой я писал в начале: "переводчик" должен уметь работать со всеми символами всех алфавитов. Этим должен заниматься человек, готовящий исходные данные для алгоритма и интерпретирующий результат.
Предположим, у нас есть алгоритм для сложения чисел. Мы ведь не можем записать для него исходные данные как вздумается. Мы должны закодировать их в таком виде, в каком алгоритм может с ними работать. И результат он нам выдаст в таком виде, какой предусмотрен его схемой, а не как нам захочется, поэтому интерпретация результата — это наша проблема, а не алгоритма.

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

Или Вы уже решаете другую задачу, а я этого не заметил?

[cscscs]

(Оффтоп)

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

Короче, $S'=\{B,C\}^*$.

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

$h$ - индуцирование отображения $g$ c $\{B,C,D,E,F\}$ на $\{B,C,D,E,F\}^*$,, ограниченное на $\{B,C\}^*$.

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

$f$ - индуцирование отображения $g$ c $\{B,C,D,E,F\}$ на $\{B,C,D,E,F\}^*$, ограниченное на $P'$.

Вот это всё не верно.

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

Вот почему нельзя было написать $g(D)=BC^3B, A=\prod\limits_{k=1}^nX_kDZ_kY_k$ например...

Потому что второе не верно. И нужно предварительно оговаривать, что эти обозначения значат.

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

можно же написать $K,M\in S'$...

Зато в первоначальном варианте сразу понятно где что и ничего не перепутаешь.

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

Пусть $A=\prod\limits_{k=1}^nX_kDZ_kY_k$, тогда $f(A)=h(A)=\prod\limits_{k=1}^nh(X_k)h(D)h(Z_k)h(Y_k)$.

Это не верно.

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

Ну не максимально лаконично, но лаконичнее...

Не столь важно, имхо.

-- 08.02.2014, 01:17 --

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

Ваша задача — выяснить, перечислимо ли множество всех алгоритмов.

Программ. Я ошибся, когда писал название темы. nikvic меня поправил.

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

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

Что такое перевод? Это некоторое точное общепонятное предписание, определяющее потенциально осуществимый процесс последовательного преобразования абстрактных слов из некоторого множества слов $X'$, процесс, допускающий любое слово из $X'$ в качестве исходного. Т.е. это алгоритм.
Для того, чтобы доказать, что множество всех программ перечислимо, мы пользуемся этим алгоритмом. Хорошо, вот мы доказали, что множество всех программ перечислимо. Но т.к. мы пользовались алгоритмом перевода, то мы неяво предположили, что для него существует вполне эквивалентная программа (разве я здесь ошибаюсь?). Теорема 3, как мне кажется, говорит об обратном.

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

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

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

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

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

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

[nikvic]

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

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

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

[Sonic86]

(Оффтоп)

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

Sonic86 писал(а):

Короче, $S'=\{B,C\}^*$.

Sonic86 писал(а):

$h$ - индуцирование отображения $g$ c $\{B,C,D,E,F\}$ на $\{B,C,D,E,F\}^*$,, ограниченное на $\{B,C\}^*$.

Sonic86 писал(а):

$f$ - индуцирование отображения $g$ c $\{B,C,D,E,F\}$ на $\{B,C,D,E,F\}^*$, ограниченное на $P'$.

Вот это всё не верно.

Да?!
Ухожу из этой темы.