НГУ

Форумы НГУ
Текущее время: Сб фев 24, 2018 3:09 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 
Автор Сообщение
СообщениеДобавлено: Пн дек 06, 2004 5:33 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
s(x) = x+1 --- одноместная функция.
I^m_n(x_1, ..., x_n) = x_m для n > 0, 0 < m < = n --- n-местная функция.
o(x) = 0 одноместная функция, тождественно равная нулю.
f_0 --- нульместная функция, тождественно равная нулю.

Схема примитивной рекурсии:

f(x_1, ..., x_k, 0) = g(x_1, ..., x_k);
f(x_1, ..., x_k, t+1) = h(x_1, ..., x_k, t, f(x_1, ..., x_k, t)).

Отдельный случай k=0 (функция f одноместна) не выделяем (то есть если у нас нет нульместных функций, то мы не можем определить одноместную функцию по схеме примитивной рекурсии).

Скажем, что функция является прф типа 1, если она может быть получена из функций I^m_n(x_1, ..., x_n), s(x) и f_0 при помощи конечного числа суперпозиций и примитивных рекурсий. Говорим, что функция является прф типа 2, если она может быть получена из функций I^m_n(x_1, ..., x_n), s(x) и o(x) при помощи конечного числа суперпозиций и примитивных рекурсий.

Доказать, что функция местности > 0 является прф типа 1 тогда и только тогда, когда она является прф типа 2.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт дек 07, 2004 6:05 pm 
Не в сети
Начинающий автор

Зарегистрирован: Пн окт 18, 2004 12:09 am
Сообщения: 284
Откуда: Антон
А с минимизацией можно решить задачу???
А то, например, я функцию f_0 хочу так определить так: f_0 = (\mu x <= 1)(x = o(x))

PS: ПРФ1 => ПРФ2, вроде, несложно, т.к. o(x) можно представить как прим. рекурсию от f_0

PPS: Вопрос про минимизацию нужен как раз для док-ва ПРФ2 => ПРФ1


Последний раз редактировалось PranT Вт дек 07, 2004 6:30 pm, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт дек 07, 2004 6:24 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
PranT писал(а):
А с минимизацией можно решить щадачу???


Нет, нельзя. Минимизация запрещена условиями задачи.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт дек 07, 2004 6:26 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Сб мар 20, 2004 11:13 pm
Сообщения: 1085
Откуда: Карлсон, который живёт на крыше
Так там ограниченная минимизация используется, а её можно без оператора минимизации записать. Просто так удобнее.

_________________
Спокойствие, только спокойствие! :)

И всё же:
Янукович -- мой выбор!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт дек 07, 2004 6:38 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Исследователь писал(а):
Так там ограниченная минимизация используется, а её можно без оператора минимизации записать. Просто так удобнее.


При чем здесь ограниченная минимизация? Ведь в условии же сказано:

Цитата:
Скажем, что функция является прф типа 1, если она может быть получена из функций I^m_n(x_1, ..., x_n), s(x) и f_0 при помощи конечного числа суперпозиций и примитивных рекурсий. Говорим, что функция является прф типа 2, если она может быть получена из функций I^m_n(x_1, ..., x_n), s(x) и o(x) при помощи конечного числа суперпозиций и примитивных рекурсий.


Никакие минимизации там не упоминаются.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт дек 07, 2004 6:42 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Сб мар 20, 2004 11:13 pm
Сообщения: 1085
Откуда: Карлсон, который живёт на крыше
Ещё раз. Ограниченная минимизация -- это не более, чем договорённость, позволяющая коротко записывать некоторые формулы примитивно рекурсивных функций. Всё.

_________________
Спокойствие, только спокойствие! :)

И всё же:
Янукович -- мой выбор!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт дек 07, 2004 6:54 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Исследователь писал(а):
Ещё раз. Ограниченная минимизация -- это не более, чем договорённость, позволяющая коротко записывать некоторые формулы примитивно рекурсивных функций. Всё.


Бред какой-то.

Если мы применяем обычную минимизацию к k-местной функции, то получаем (k-1)-местную функцию. Если применяем ограниченную минимизацию, то получаем k-местную функцию.

Ну ка, Исследователь, докажите, что одноместная функция f(x) = x минус с точкой 1 является прф типа 2.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт дек 07, 2004 7:05 pm 
Не в сети
Начинающий автор

Зарегистрирован: Пн окт 18, 2004 12:09 am
Сообщения: 284
Откуда: Антон
Коба писал(а):
Если мы применяем обычную минимизацию к k-местной функции, то получаем (k-1)-местную функцию. Если применяем ограниченную минимизацию, то получаем k-местную функцию.

Что-то непонятно! Я всегда думал, что ограниченная минимизация вообще "работает" с ПР предикатами!!! Проясните, пожалуйста, ситуацию!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт дек 07, 2004 7:35 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Под применением ограниченной минимизации к функции g подразумевается применение ограниченной минимизации к предикату g=0.

И вообще, не я тут первый заговорил про ограниченную минимизацию. Я всего лишь отвечал Исследователю. Каков вопрос, таков и ответ :)

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


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

Часовой пояс: UTC + 7 часов


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

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


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

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB