примитивно рекурсивные и разрешимые множества

[T-Mac]

здраствуйте!
помогите доказать:
1)Замкнуты ли примитивно рекурсивные множества относительно операции проекции
2)доказать что разрешимые множества незамкнуты относительно операции проекции


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

По второй задаче как я понимаю нужно привести пример множества которое не замкнуто, но дальше дело не двигается(

Заранее спасибо!

[Xaositect]

По первой задаче какие соображения? Подсказка: проекция и минимизация вещи похожие.

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

[T-Mac]

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

по второй:
примером перечислимого, но не разрешимого множества является множество, соответствующее проблеме самоприменимости, т. е.

$${x:!U(x,x)}$$

кроме того есть ещзе такие примеры множество выводимых формул исчисления предикатов 1-го порядка, множество общезначимых формул логики предикатов 1-го порядка, множество выводимых формул формальной арифметики или теории множеств (в этих последних случаях истинные формулы уже не образуют перечислимых множеств), множество полиномов из

$$ Z[x1,…,xn], n>9$$

, обращающихся в ноль хотя бы на одном k-членном наборе целых чисел

[Xaositect]

T-Mac в сообщении #279535 писал(а):

множество выводимых формул исчисления предикатов 1-го порядка

Мне вот это нравится, доказательство проще получится. Обозначим это множество $T$
Что значит, что формула выводима? Это значит, что существует доказательство этой формулы.
Как это можно записать формально?
$\phi\in T \Leftrightarrow \exists \Gamma (\Gamma \text{ - корректное доказательство и последняя формула } \Gamma \text{ есть } \phi)$

Что это такое? Это проекция. Осталось еще сказать, что свойство "$\Gamma$ есть корректное доказательство" разрешимо.

С остальными примерами можно сделать что-то похожее ("Существует конечное вычисление МТ на своем коде", "Существует целый корень многочлена" и т.п.).

-- Пн янв 11, 2010 18:27:42 --

Напомню определение примитивно-рекурсивной функции: ф-я примитивно-рекурсивна, если она м.б.получена из базовых с помощью суперпозиции и примитивной рекурсии.
А определение частично рекурсивной функции добавляет еще одну операцию - операцию минимизации $\mu$:
$\mu_y f(x_1, \dots, x_n, y)$ есть по определению минимальное $y_0$ такое, что $f(x_1,\dots,x_n, y_0) = 0$, и $f(x_1,\dots,x_n,y)$ определено для всех $y\leq y_0$.

Так вот, проекция ("существует $y$ такое, что $\left< x, y\right> \in S$") и минимизация("найти $y$ такое, что $f(x, y) = 0$") похожи.
Так что попробуйте свести минимизацию к проекции.

Еще можно доказать, что те разрешимые свойства, о которых я говорил до этого (насчет второй задачи), примитивно рекурсивны.

[T-Mac]

Цитата:

Что это такое? Это проекция.

я наверное чего то не понимаю... а почему это проекция?

[Xaositect]

T-Mac в сообщении #280984 писал(а):

я наверное чего то не понимаю... а почему это проекция?

Дайте тогда ваше определение проекции.

[T-Mac]

проекция вдоль i-й координаты

$$ для S \in N^k ; pri_i(S)={(x_1,…,x_{i-1},x_{i+1},…,x_k) }$$

[Ираклий]

1) Если известно, что примитивно рекурсивное множество это то же самое, что и перечислимое множество, то из алгоритма, перечисляющего данное множество легко получить алгоритм, перечисляющий проекцию данного множества.
2) Пусть М - множество пар натуральных чисел (k;n) таких, что k-я машина Тьюринга завершает свою работу на пустом входе за не более чем n шагов. Легко убедиться, что M - разрешимое множество. То, что проекция М на первую ось (т.е. вдоль 2-й координаты) не разрешимо - известный факт.

[Xaositect]

$x = (x_1,\dots,x_n)\in N^k;\, pr_i(x) = (x_1,\dots,x_{i-1},x_{i+1},\dots,x_n)$
$S\subseteq N^k;\, y\in pr_i(S) \Leftrightarrow \exists x_i (y_1,\dots,y_{i-1},x_i,y_{i+1},\dots,x_n)$

[T-Mac]

Цитата:

1) Если известно, что примитивно рекурсивное множество это то же самое, что и перечислимое множество, то из алгоритма, перечисляющего данное множество легко получить алгоритм, перечисляющий проекцию данного множества.

А как получить алгоритм?

Цитата:

2) Пусть М - множество пар натуральных чисел (k;n) таких, что k-я машина Тьюринга завершает свою работу на пустом входе за не более чем n шагов. Легко убедиться, что M - разрешимое множество. То, что проекция М на первую ось (т.е. вдоль 2-й координаты) не разрешимо - известный факт.

Я не очень понял, что значит k-ая машина...

-- Вс янв 17, 2010 16:00:50 --

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

$x = (x_1,\dots,x_n)\in N^k;\, pr_i(x) = (x_1,\dots,x_{i-1},x_{i+1},\dots,x_n)$
$S\subseteq N^k;\, y\in pr_i(S) \Leftrightarrow \exists x_i (y_1,\dots,y_{i-1},x_i,y_{i+1},\dots,x_n)$

я все равно не понял почему выполнены эти свойства в вашем примеры

[Ираклий]

T-Mac в сообщении #281218 писал(а):

Цитата:

1) Если известно, что примитивно рекурсивное множество это то же самое, что и перечислимое множество, то из алгоритма, перечисляющего данное множество легко получить алгоритм, перечисляющий проекцию данного множества.

А как получить алгоритм?

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

T-Mac в сообщении #281218 писал(а):

Цитата:

2) Пусть М - множество пар натуральных чисел (k;n) таких, что k-я машина Тьюринга завершает свою работу на пустом входе за не более чем n шагов. Легко убедиться, что M - разрешимое множество. То, что проекция М на первую ось (т.е. вдоль 2-й координаты) не разрешимо - известный факт.

Я не очень понял, что значит k-ая машина...

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

[T-Mac]

Спасибо!
Вроде разобрался с этим

[Xaositect]

Ираклий в сообщении #281131 писал(а):

1) Если известно, что примитивно рекурсивное множество это то же самое, что и перечислимое множество, то из алгоритма, перечисляющего данное множество легко получить алгоритм, перечисляющий проекцию данного множества.

Примитивно рекурсивное множество - это не то же самое что перечислимое.

-- Пн янв 18, 2010 13:37:08 --

T-Mac в сообщении #281218 писал(а):

я все равно не понял почему выполнены эти свойства в вашем примеры

Это я к тому, что проекция делается квантором $\exists$

[Ираклий]

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

Примитивно рекурсивное множество - это не то же самое что перечислимое.

Хм.. Тогда сорри. Мне казалось, что разрешимые множества в теории рекурсивных функций называются рекурсивными, а перечислимые -- примитивно рекурсивными. Если это не так, то есть ли в теории рекурсивных функций термин, соответствующий перечислимым множествам?

[Xaositect]

Чаще всего называют рекурсивно-перечислимыми.

А примитивно-рекурсивные - это подмножество рекурсивных.