2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6 ... 8  След.
 
 
Сообщение18.02.2009, 22:28 


26/06/06
56
Одесса
Простая иллюстрация для Nxx без "завуалированных аргументов":
Пусть функции $a(x)$ и $b(x)$ примитивно рекурсивные. Пусть функция $f(x)$ есть одна из $a(x)$ и $b(x)$ (любая). Тогда функция $f(x)$ примитивно рекурсивная.

Xaositect писал(а):
А если ночью 18.02.2009 Караганду переименуют, или вогоны сотрут с Землю с лица Галактики? :)

В этом случае высказывание "19.02.2009 в Караганде будет дождь" ложно :wink:

 Профиль  
                  
 
 
Сообщение18.02.2009, 22:36 


20/07/07
834
Цитата:
Пусть функция $f(x)$ есть одна из $a(x)$ и $b(x)$ (любая).

Случайным образом? :-) Или когда ей как нравится? Я четко видел в определении функции $f(x)$ слово "если" и фигурную скобку. Или мне показалось? Или это не было частью определения функции $f(x)$?

Если это не относилоcь к определению $f(x)$, а было чемто посторонним, то да.

Пусть функция f(x) дает вообще любой ответ, ни от чего не зависящий. f(x) - примитивно рекурсивная?

 Профиль  
                  
 
 
Сообщение18.02.2009, 22:47 
Экс-модератор


17/06/06
5004
$(f=a\Rightarrow f\in X)\&(f=b\Rightarrow f\in X)\to ((f=a\vee f=b)\Rightarrow f\in X)$

 Профиль  
                  
 
 
Сообщение18.02.2009, 22:58 


20/07/07
834
Цитата:
$(f=a\Rightarrow f\in X)\&(f=b\Rightarrow f\in X)\to ((f=a\vee f=b)\Rightarrow f\in X)$

Что вы считаете $a$ и что - $b$?
Может быть, я прочитал неверно, и вместо

$$ h(x) \equiv \left\{ \begin{array}{сl} 2, & $если гипотеза Гольдбаха истинна$,\\ 1, & $если гипотеза Гольдбаха ложна$. \end{array} \right. $$

там было

$$ \begin{array}{сl}$если гипотеза Гольдбаха истинна$, & h(x) \equiv 1,\\$если гипотеза Гольдбаха ложна$, & h(x)\equiv 2. \end{array} \right? $$

Условие "если" является частью определения функции или нет? Если является, то $h(x)$ - не обязательно примитивно-рекурсивная, если не является, то $h(x)$ не имеет отношения к гипотезе Гольдбаха.

 Профиль  
                  
 
 
Сообщение18.02.2009, 23:04 
Экс-модератор


17/06/06
5004
$a$ - тождественная единица, $b$ - тождественная двойка. В условии, фактически, сказано, что $f=a \vee f=b$. Я это так понимаю. То есть не является частью определения, и тогда всё понятно.

Хотя давайте я все-таки лучше послушаю - не стоит мне лезть в то, что не знаю :)

 Профиль  
                  
 
 
Сообщение18.02.2009, 23:16 


20/07/07
834
AD писал(а):
$a$ - тождественная единица, $b$ - тождественная двойка. В условии, фактически, сказано, что $f=a \vee f=b$. Я это так понимаю. То есть не является частью определения, и тогда всё понятно.

А, ну если тут такая обманка, и нижеприведенное выражение не является определением функции,

$$
h(x) = 
\left\{ \begin{array}{сl} 
2, & $если гипотеза Гольдбаха истинна$,\\ 
1, & $если гипотеза Гольдбаха ложна$.
\end{array} \right.
$$

то да, $h(x)$ - примитивно-рекурсивная, так как никаких проверок условий и вычислений гипотез Гольдбаха не содержит. Она просто либо 1, либо 2. Только надо понимать, что в этом случае вышеприведенное выражение не является определением такой функции.

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

$$
y(x) = 
\left\{ \begin{array}{сl} 
1, & $ если x>0$,\\ 
0, & $ если x\le 0$.
\end{array} \right.
$$

$$
\text{если } z>0, \text{то } y(x) \equiv 1, \text{если }  z\le 0, \text{то } y(x) \equiv 0
$$

Чувствуете разницу? Во втором случае, y - константа, в первом - нет.

 Профиль  
                  
 
 
Сообщение18.02.2009, 23:22 
Экс-модератор


17/06/06
5004
Nxx в сообщении #187527 писал(а):
Чувствуете разницу? Во втором случае, y - константа, в первом - нет.
Чувствую, но не понимаю, каким образом можно вообще понять условие первым способом. Ведь истинность гипотезы не разделяет область определения функции на два множества.

 Профиль  
                  
 
 
Сообщение19.02.2009, 04:38 


24/03/07
321
маткиб писал(а):
Рекурсивность - это свойство именно функции, а не описания. И не нужно это путать с программистским понятием рекурсивности (где функция - это фрагмент программы, а рекурсивная - это которая содержит вызов себя). По крайней мере, у программистов такого понятия как "примитивная рекурсивность" просто нет.

Я ничего не путаю, я вам пытаюсь объяснить суть понятия рекурсивности функции. Следует понимать так, что рекурсивно описание функции. И если функция имеет как минимум одно конкретное рекурсивное описание - тогда она рекурсивна. Вы, конечно, можете настаивать на своём, но это не соответствует действительности.

 Профиль  
                  
 
 
Сообщение19.02.2009, 13:56 


26/06/06
56
Одесса
Nxx писал(а):
Цитата:
Пусть функция $f(x)$ есть одна из $a(x)$ и $b(x)$ (любая).

Случайным образом? :-) Или когда ей как нравится?

Да, именно так. Слово "любая" означает любая, какая угодно, выбранная произвольным образом. Акт выбора одного произвольного элемента из двух данных нетривиальная операция?

Nxx писал(а):
Я четко видел в определении функции $f(x)$ слово "если" и фигурную скобку. Или мне показалось? Или это не было частью определения функции $f(x)$?
Если это не относилоcь к определению $f(x)$, а было чемто посторонним, то да.

Условие приведено как есть у Мендельсона. Дополнительных указаний или уточнений там нет.

Nxx, выражайтесь, пожалуйста, точнее. В частности, неясно, что такое "функция дает ответ", "функции нравится", "функция не имеет отношения к", "функция ничего не знает про", "функция не сможет вычислить", "передать в качестве аргумента в функцию", "в функцию вводится параметр" и т.п.

PS
Завтра функция $r(x)$ MaximKat станет примитивно рекурсивной! :D

 Профиль  
                  
 
 
Сообщение19.02.2009, 15:51 


20/07/07
834
Цитата:
Да, именно так. Слово "любая" означает любая, какая угодно, выбранная произвольным образом. Акт выбора одного произвольного элемента из двух данных нетривиальная операция?


Понимаете ли, функция выбора, разрешенная для примитивно-рекурсивных функций выглядит так: $I_n^m(x_1,...,x_n)=x_m$. В данном случае $n=2, x_1=1,x_2=2$. А вот m неизвестно. Если m вычисляется внутри функции, то она вероятно, не примитивно-рекурсивная. Если m передается в функцию h(x) в качестве пераметра, то она, очевидно, примитивно-рекурсивная. Операция случайного выбора или "выбора произвольным образом" или "выбора когда ей как нравится" не является разрешенным элементом для примитивно-рекурсивных функций.

 Профиль  
                  
 
 
Сообщение19.02.2009, 16:00 
Экс-модератор


17/06/06
5004
Nxx, давайте по-человечески. Вы предлагаете формулировку задачи, не соответствующую моему пониманию - ну так сформулируйте, пожалуйста, эту формулировку!

Укажите область определения функции для начала.

 Профиль  
                  
 
 
Сообщение19.02.2009, 17:56 


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

Извините, не знал что Nxx примитивно рекурсивная функция :?

 Профиль  
                  
 
 
Сообщение19.02.2009, 18:24 


20/07/07
834
TypucT писал(а):
Nxx писал(а):
Операция случайного выбора или "выбора произвольным образом" или "выбора когда ей как нравится" не является разрешенным элементом для примитивно-рекурсивных функций.

Извините, не знал что Nxx примитивно рекурсивная функция :?


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

 Профиль  
                  
 
 
Сообщение19.02.2009, 19:11 


26/06/06
56
Одесса
Повторюсь: операция выбора может быть любой (в том числе - нерекурсивной). Свойства выбираемого элемента от этого не изменяются.

Вы смешиваете доказательство с тем, что мы доказываем.

И еще одно. Для определения примитивной рекурсивности не обязательно вычислять значение функции. Вот простой пример: Пусть функция $f(x)$ примитивно рекурсивная. Значит, $f(x)$ примитивно рекурсивная функция.

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


18/12/07
8774
Новосибирск
Существует столько интересных задач про примитивно рекурсивные функции, а тут какую-то х..ню обсуждают! Обидно :(

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

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



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

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


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

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