Показать примитивную рекурсивность словарной функции

[Kosat]

В алфавите $A=\left\{a_1,a_2,a_3,...,a_1\right\}$ показать примитивную рекурсивность словарной функции.
$F\left(\bar{x},\bar{y}\right)=\bar{x}\bar{y}$ - функция, приписывающая к слову $\bar{x}$ справа слово $\bar{y}$.

-------------------------------

Я не много смог найти про алфавиты:
http://life-prog.ru/1_18226_vichislimie-funktsii-i-mashina-tyuringa.html
http://studopedia.org/8-29704.html

Про примитивную рекурсивность я нашёл больше:
http://www.studfiles.ru/preview/2918984/page:16/

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

-------------------------------

Для справки даю предыдущее заданее, которое я, кажется, решил:
http://dxdy.ru/topic117543.html

[Xaositect]

Kosat в сообщении #1211431 писал(а):

Я не много смог найти

А какие учебники Вам рекомендовали? Просто примитивную рекурсивность на словах можно определять двумя способами - либо напрямую, либо через кодирование числами. В результате получается одно и то же, но вот доказательства примитивной рекурсивности будут разные. Надо знать, что именно было у Вас в курсе.

[Kosat]

Xaositect в сообщении #1211518 писал(а):

Kosat в сообщении #1211431 писал(а):

Я не много смог найти

А какие учебники Вам рекомендовали? Просто примитивную рекурсивность на словах можно определять двумя способами - либо напрямую, либо через кодирование числами. В результате получается одно и то же, но вот доказательства примитивной рекурсивности будут разные. Надо знать, что именно было у Вас в курсе.

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

[Kosat]

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

"В алфавите $A=\left\{a_1,a_2,a_3,...,a_p\right\}$ показать примитивную рекурсивность словарной функции.
$F\left(\bar{x},\bar{y}\right)=\bar{x}\bar{y}$ - функция, приписывающая к слову $\bar{x}$ справа слово $\bar{y}$."

[mihaild]

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

[Xaositect]

mihaild в сообщении #1211589 писал(а):

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

По-моему, там все стандартно: основные функции это $Z(x) = \Lambda$ и $S_a(x) = ax$, рекурсия $f(\Lambda, y) = g(y); f(ax, y) = h_a(y)$.

[arseniiv]

(Оффтоп)

mihaild в сообщении #1211589 писал(а):

и совсем неочевидно, как определять оператор примитивной рекурсии

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

[Kosat]

В общем, промежуточным итогом будет такой: "Порядок лексикографический, вложение строк в числа (и обратно, и ещё плюс прибавление одного числа (особенно единицы) к другому - то есть получится метрика)) основывается на словарном номере числа"?

[arseniiv]

Kosat в сообщении #1211853 писал(а):

то есть получится метрика

Чего это, какая метрика? Да и не нужна она тут.

[Kosat]

arseniiv в сообщении #1211963 писал(а):

Kosat в сообщении #1211853 писал(а):

то есть получится метрика

Чего это, какая метрика? Да и не нужна она тут.

Метрика не нужна, но она есть.

Метрическое пространство

[arseniiv]

(Оффтоп)

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

[Kosat]

arseniiv в сообщении #1212446 писал(а):

(Оффтоп)

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

(Оффтоп)

Нечто вроде этого. И плюс норму, до кучи:
https://en.wikipedia.org/wiki/Relation_of_norms_and_metrics

[arseniiv]

(Оффтоп)

Норма не получится. Строки не образуют векторное пространство.

Kosat в сообщении #1212465 писал(а):

Нечто вроде этого.

Толку от такой метрики немного. Её значения будут, конечно, говорить что-то о разнице в длинах строк, но не очень хорошо.

[Kosat]

Подытоживая сказанное, я записал такое решение:

$F\left(\overline{x},0\right)=\overline{x}=U_1^1=g\left(\overline{x}\right)$
$F\left(\overline{x},\overline{y}+1\right)=\overline{x}\left(\overline{y}+1\right)=\overline{x}\overline{y}+1=S\left(F\left(\overline{x},\overline{y}\right)\right)=h\left(\overline{x},\overline{y},F\left(\overline{x},\overline{y}\right)\right)$

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

$F\left(a_1,a_p+1\right)=a_1\left(a_p+1\right)=a_1a_1a_1\neq a_2a_1=a_1a_p+1=S\left(F\left(a_1,a_p\right)\right)=h\left(a_1,a_p,F\left(a_1,a_p\right)\right)$

Как же можно сделать лучше (правильнее...)?..