2014 dxdy logo

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

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


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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1 ... 4, 5, 6, 7, 8  След.
 
 
Сообщение23.02.2009, 11:12 


26/06/06
56
Одесса
Nxx писал(а):
TypucT писал(а):
(2) $\Gamma\to h(x)\equiv 2$ --- значение первой альтернативы,
(3) $\overline\Gamma\to h(x)\equiv 1$ --- значение второй альтернативы,

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

Вы упомянули некую "формальную систему примитивно-рекурсивных функций". Где можно найти ее определение: (a) множество символов; (b) что в ней является формулой; (c) множество аксиом; (d) множество правил вывода?
Зная (a) и (b) мы сможем однозначно и без всяких споров определить, являются ли строки (2) и (3) формулами этой теории. Если ответ будет отрицательным, тогда вы правы и, действительно, в "формальной системе примитивно-рекурсивных функций" невозможно сформулировать (2) и (3).
Цитата:
если считать оба высказывания частью определения функции h(x)

Да, так и есть, выражения (1)-(5) есть определение функции $h(x)$, записанное более формально, чем в условии.

Кроме прочего, вас не смущает, что $\Gamma$ и утверждения содержащие $\Gamma$ вообще-то cформулировать несложно?

 Профиль  
                  
 
 
Сообщение23.02.2009, 11:57 


24/03/07
321
TypucT писал(а):
Вы упомянули некую "формальную систему примитивно-рекурсивных функций". Где можно найти ее определение: (a) множество символов; (b) что в ней является формулой; (c) множество аксиом; (d) множество правил вывода?

В вашем же Мендельсоне перед определением примитивно рекурсивной функции целые 2 параграфа посвящены формализации арифметики (теория S). Как вы думаете зачем?
Если не понятно зачем, обратите внимание на Предложение 3.23 - всякая рекурсивная функция представима в S.

 Профиль  
                  
 
 
Сообщение23.02.2009, 12:59 


26/06/06
56
Одесса
Dandan писал(а):
[тут что-то было]всякая рекурсивная функция представима в S.

Да. И что же?

 Профиль  
                  
 
 
Сообщение23.02.2009, 13:15 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Dandan в сообщении #188816 писал(а):
всякая рекурсивная функция представима в S.

Ваша многострадальная функция представима в $S$. Только неизвестно, какой формулой, $y=S0$ или $y=SS0$.

 Профиль  
                  
 
 
Сообщение23.02.2009, 13:31 


26/06/06
56
Одесса
Xaositect писал(а):
Dandan в сообщении #188816 писал(а):
всякая рекурсивная функция представима в S.

Ваша многострадальная функция представима в $S$. Только неизвестно, какой формулой, $y=S0$ или $y=SS0$.

Хуже. Даже формула известна.
$R(x_1,x_2)$: $(\Gamma\to x_2=0'')\mathop{\&}(\overline\Gamma\to x_2=0')$.

 Профиль  
                  
 
 
Сообщение23.02.2009, 13:54 


20/07/07
834
Xaositect писал(а):
Dandan в сообщении #188816 писал(а):
всякая рекурсивная функция представима в S.

Ваша многострадальная функция представима в $S$. Только неизвестно, какой формулой, $y=S0$ или $y=SS0$.


Это только если утверждения (2) и (3) не являются частью определения функции. Я это специально уточнил. Но

TypucT писал(а):
Цитата:
если считать оба высказывания частью определения функции h(x)

Да, так и есть, выражения (1)-(5) есть определение функции $h(x)$, записанное более формально, чем в условии.


Если определением функции является $y=S0$ или $y=SS0$, то проблем, разумеется, нет.

Добавлено спустя 10 минут 7 секунд:

Цитата:
Где можно найти ее определение: (a) множество символов; (b) что в ней является формулой; (c) множество аксиом; (d) множество правил вывода?


Могу точно сказать, что символ $\Gamma$ не является символом, определенным в этой формальной системе. Элементы, из которых должна состоять примитивно-рекурсивная функция уже перечислялись.

 Профиль  
                  
 
 
Сообщение23.02.2009, 14:13 


26/06/06
56
Одесса
Nxx писал(а):
Цитата:
Где можно найти ее определение: (a) множество символов; (b) что в ней является формулой; (c) множество аксиом; (d) множество правил вывода?


Могу точно сказать, что символ $\Gamma$ не является символом, определенным в этой формальной системе.

Наконец-то, хоть какое-то определенное утверждение. $\Gamma$ - это формула (не символ), которую можно записать в формальной арифметике. Следовательно, ваша формальная система отлична от формальной арифметики. Можете ли вы рассказать о ней поподробнее, т.е. дать (a)-(d)?

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

 Профиль  
                  
 
 
Сообщение23.02.2009, 14:38 


20/07/07
834
К рекурсивным функциям относятся только те, которые можно записать в виде формулы, состоящей из нескольких вышеперечисленных элементов (нулевая функция, функция инкремента, функция выбора, функция рекурсии), а также аргументов самой функции.

Функция выбора из неопределенного множества или по неопределенному индексу или по индексу, который не является ни аргументом функции или примитивно-рекурсиной функцией, в системе примитивно-рекурсивных функций невозможна.

Добавлено спустя 11 минут 41 секунду:

Более формально:


1) Простейшие функции
$$            s(x)=x+1,    O^{n}(x_1,x_2,...,x_n)=0, I^{nm} (x_1,x_2,...,x_n)=x_m $$
примитивно рекурсивны.
2) Если функция f получена из примитивно рекурсивных функций с
помощью оператора суперпозиции
$f(x_1,x_2,...,x_n)=h(g_1(x_1,x_2,...,x_n) ,g_2(x_1,x_2,...,x_n),...,g_m(x_1,x_2,...,x_n))$
или с помощью оператора
примитивной рекурсии
$f(x_1,x_2,...,x_n,0)= g(x_1,x_2,...,x_n),$
$ f(x_1,x_2,...,x_n, y+1)= h(x_1,x_2,...,x_n,y, f(x_1,x_2,...,x_n,y)),$
то функция f примитивно рекурсивна.
3) То, что функция f примитивно рекурсивна, устанавливается несколькими
применениями правил 1) и 2).

 Профиль  
                  
 
 
Сообщение23.02.2009, 15:01 


26/06/06
56
Одесса
Nxx писал(а):
1) Простейшие функции
$$            s(x)=x+1,    O^{n}(x_1,x_2,...,x_n)=0, I^{nm} (x_1,x_2,...,x_n)=x_m $$
примитивно рекурсивны.
2) Если функция f получена из примитивно рекурсивных функций с
помощью оператора суперпозиции
$f(x_1,x_2,...,x_n)=h(g_1(x_1,x_2,...,x_n) ,g_2(x_1,x_2,...,x_n),...,g_m(x_1,x_2,...,x_n))$
или с помощью оператора
примитивной рекурсии
$f(x_1,x_2,...,x_n,0)= g(x_1,x_2,...,x_n),$
$ f(x_1,x_2,...,x_n, y+1)= h(x_1,x_2,...,x_n,y, f(x_1,x_2,...,x_n,y)),$
то функция f примитивно рекурсивна.
3) То, что функция f примитивно рекурсивна, устанавливается несколькими
применениями правил 1) и 2).

Отлично! Уже почти виден набор символов вашей формальной теории. Дело за малым: скажите, что у вас является формулой?

 Профиль  
                  
 
 
Сообщение24.02.2009, 10:22 


26/06/06
56
Одесса
TypucT писал(а):
Xaositect писал(а):
Dandan в сообщении #188816 писал(а):
всякая рекурсивная функция представима в S.

Ваша многострадальная функция представима в $S$. Только неизвестно, какой формулой, $y=S0$ или $y=SS0$.

Хуже. Даже формула известна.
$R(x_1,x_2)$: $(\Gamma\to x_2=0'')\mathop{\&}(\overline\Gamma\to x_2=0')$.

Поторопился. Не получается доказать.

Добавлено спустя 44 минуты 46 секунд:

Nxx писал(а):
...
Это только если утверждения (2) и (3) не являются частью определения функции. Я это специально уточнил.
...
Если определением функции является $y=S0$ или $y=SS0$, то проблем, разумеется, нет.

и т. п.

$$
\exists_1 x_2 ((P\to x_2 = G_1(x_1)) \& (\neg P\to x_2 = G_2(x_1)))
\equiv 
(P \to \exists_1 x_2 (x_2=G_1(x_1))) \& (\neg P \to \exists_1 x_2 (x_2=G_2(x_1))),
$$
следовательно
$$
f(x) = 
\left\{ \begin{array}{сl} 
g_1(x), & $если $ R $ истинно$,\\ 
g_2(x), & $если $ R $ ложно$.
\end{array} \right.
$$
то же самое, что и
$$
$Если $R$ истинно, то $f(x)\equiv g_1(x)$. Если $R$ ложно, то $f(x)\equiv g_2(x)$.$
$$

 Профиль  
                  
 
 
Сообщение24.02.2009, 10:37 


20/07/07
834
Дело в том, что $g_1(x)$ и $g_2(x)$ вы можете задать в системе примитивно-рекурсивных функций, а всю фразу $$
$Если $R$ истинно, то $f(x)\equiv g_1(x)$. Если $R$ ложно, то $f(x)\equiv g_2(x)$.$
$$ - нет. Точнее, эта фраза может быть задана в системе примитивно-рекурсивных функций только если R - аргумент функции f. Завязать примитивно-рекурсивную функцию на какую-то внешнюю, неизвестную константу, не передавая ее в качестве аргумента в функцию, в формальном языке примитивно-рикурсивных функций невозможно.

 Профиль  
                  
 
 
Сообщение24.02.2009, 10:57 


26/06/06
56
Одесса
Nxx писал(а):
в формальном языке примитивно-рикурсивных функций невозможно.

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

Например, реально вы могли дать такое возражение: по определению выразимого отношения все еще нельзя доказать, что в принятой аксиоматике формальной арифметики есть формула, с помощью которой выражалось бы отношение $\Gamma$. Тут мне нечем было бы крыть, а пришлось бы наложить заплатку, мол, для доказательства я использовал такое расширение формальной арифметики, в которой формула, выражающая $\Gamma$, разрешима. Вообще, утверждая, что формула $P$ некоторой формальной теории $K$ выражает отношение $R$, мы тем самым предполагаем ее разрешимость в $K$. А что если она неразрешима в $K$? Нет проблем - добавим к аксиомам теории $K$ новую аксиому $P$ или $\neg P$ и все станет на свои места в новой теории $K'$.

 Профиль  
                  
 
 
Сообщение26.02.2009, 20:21 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
TypucT писал(а):
Вообще, утверждая, что формула $P$ некоторой формальной теории $K$ выражает отношение $R$, мы тем самым предполагаем ее разрешимость в $K$.


Что Вы понимаете под "разрешимостью формулы в теории"?

 Профиль  
                  
 
 
Сообщение28.02.2009, 18:34 


26/06/06
56
Одесса
Профессор Снэйп писал(а):
TypucT писал(а):
Вообще, утверждая, что формула $P$ некоторой формальной теории $K$ выражает отношение $R$, мы тем самым предполагаем ее разрешимость в $K$.


Что Вы понимаете под "разрешимостью формулы в теории"?

Формула $P$ разрешима в теории $K$, если $\vdash_K P$ либо $\vdash_K \neg P$. Т.е. $P$ можно доказать либо опровергнуть в $K$.

Утверждение касалось замкнутых формул. Для незамкнутой формулы $A(x_1, ..., x_n)$, выражающей отношение $R(x_1, ..., x_n)$, необходима разрешимость формулы $A(k_1, ..., k_n)$ для всякого набора цифр $k_1, ..., k_n$. Здесь цифра - это терм $0$ с применением операции "прибавление единицы" нужное количество раз.

 Профиль  
                  
 
 
Сообщение01.03.2009, 01:40 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
TypucT писал(а):
Формула $P$ разрешима в теории $K$, если $\vdash_K P$ либо $\vdash_K \neg P$. Т.е. $P$ можно доказать либо опровергнуть в $K$.


Первый раз встречаю термин "разрешимость" в таком смысле. Обычно сами теории на предмет разрешимости изучают...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 107 ]  На страницу Пред.  1 ... 4, 5, 6, 7, 8  След.

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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