2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Показать примитивную рекурсивность словарной функции
Сообщение21.04.2017, 21:59 
Аватара пользователя


07/01/14
119
В алфавите $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

 Профиль  
                  
 
 Re: Показать примитивную рекурсивность словарной функции
Сообщение22.04.2017, 08:26 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Kosat в сообщении #1211431 писал(а):
Я не много смог найти
А какие учебники Вам рекомендовали? Просто примитивную рекурсивность на словах можно определять двумя способами - либо напрямую, либо через кодирование числами. В результате получается одно и то же, но вот доказательства примитивной рекурсивности будут разные. Надо знать, что именно было у Вас в курсе.

 Профиль  
                  
 
 Re: Показать примитивную рекурсивность словарной функции
Сообщение22.04.2017, 10:29 
Аватара пользователя


07/01/14
119
Xaositect в сообщении #1211518 писал(а):
Kosat в сообщении #1211431 писал(а):
Я не много смог найти
А какие учебники Вам рекомендовали? Просто примитивную рекурсивность на словах можно определять двумя способами - либо напрямую, либо через кодирование числами. В результате получается одно и то же, но вот доказательства примитивной рекурсивности будут разные. Надо знать, что именно было у Вас в курсе.


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

 Профиль  
                  
 
 Re: Показать примитивную рекурсивность словарной функции
Сообщение22.04.2017, 12:14 
Аватара пользователя


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

"В алфавите $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}$."

 Профиль  
                  
 
 Re: Показать примитивную рекурсивность словарной функции
Сообщение22.04.2017, 13:31 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Показать примитивную рекурсивность словарной функции
Сообщение22.04.2017, 13:34 
Заслуженный участник
Аватара пользователя


06/10/08
6422
mihaild в сообщении #1211589 писал(а):
либо придумать, как определить примитивно рекурсивные функции на строках (и тут не совсем очевидно, какие базовые функции брать, и совсем неочевидно, как определять оператор примитивной рекурсии).
По-моему, там все стандартно: основные функции это $Z(x) = \Lambda$ и $S_a(x) = ax$, рекурсия $f(\Lambda, y) = g(y); f(ax, y) = h_a(y)$.

 Профиль  
                  
 
 Re: Показать примитивную рекурсивность словарной функции
Сообщение22.04.2017, 17:40 
Заслуженный участник


27/04/09
28128

(Оффтоп)

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

 Профиль  
                  
 
 Re: Показать примитивную рекурсивность словарной функции
Сообщение23.04.2017, 13:49 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Показать примитивную рекурсивность словарной функции
Сообщение23.04.2017, 16:57 
Заслуженный участник


27/04/09
28128
Kosat в сообщении #1211853 писал(а):
то есть получится метрика
Чего это, какая метрика? Да и не нужна она тут. :roll:

 Профиль  
                  
 
 Re: Показать примитивную рекурсивность словарной функции
Сообщение24.04.2017, 16:26 
Аватара пользователя


07/01/14
119
arseniiv в сообщении #1211963 писал(а):
Kosat в сообщении #1211853 писал(а):
то есть получится метрика
Чего это, какая метрика? Да и не нужна она тут. :roll:


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

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

 Профиль  
                  
 
 Re: Показать примитивную рекурсивность словарной функции
Сообщение25.04.2017, 13:12 
Заслуженный участник


27/04/09
28128

(Оффтоп)

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

 Профиль  
                  
 
 Re: Показать примитивную рекурсивность словарной функции
Сообщение25.04.2017, 15:09 
Аватара пользователя


07/01/14
119
arseniiv в сообщении #1212446 писал(а):

(Оффтоп)

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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Показать примитивную рекурсивность словарной функции
Сообщение25.04.2017, 21:25 
Заслуженный участник


27/04/09
28128

(Оффтоп)

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

Kosat в сообщении #1212465 писал(а):
Нечто вроде этого.
Толку от такой метрики немного. Её значения будут, конечно, говорить что-то о разнице в длинах строк, но не очень хорошо.

 Профиль  
                  
 
 Re: Показать примитивную рекурсивность словарной функции
Сообщение26.04.2017, 20:36 
Аватара пользователя


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

$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)$

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Gevin Magnus


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group