Доказать, что предикат является (или не является) (примитивно) рекурсивным

@E}|{|/||{ · Регистрация: 03.07.2012

Author24 — интернет-сервис помощи студентам

Нужна курсовая по теме. Если у кого то есть хоть какая то информация - буду очень признателен.

Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы логических аксиом (6)»
Сам предикат во вложениях.
(Мендельсон: с. 151 - )

Psilon · 03.07.2012, 19:44

Не по теме:

E}|{|/||{, судя по заданию, похоже на Волкова из МАИ... :)

Вроде знакомый такой курсач делал, надо спросить

@E}|{|/||{ · 03.07.2012, 20:21 **[ТС]**

Psilon, да, именно Волков. Будь добр, спроси. Я даже купить готов.

@НектоЯрик · 17.10.2013, 18:31

Psilon, здравствуйте, могли бы вы снова обратиться к вашему другу и спросить про данную курсовую? у меня похожий вариант. рекурсивность я доказал, а как быть с геделевой нумерцией - без понятия =(

@ZGold · 04.04.2015, 21:04

Psilon, Привет! У тебя не осталось этой курсовой, можешь, посмотреть, пожалуйста ?

@3D Homer · 05.04.2015, 21:57

Если есть конкретные вопросы, то буду рад ответить.

@VSI · 05.04.2015, 22:00

ZGold, 3D Homer, обращайте внимание на даты создания тем...

@ZGold · 05.04.2015, 23:58

3D Homer, привет! Сможешь помочь ?
VSI, Уважаемый Модератор, может быть у них остались еще материалы по этой теме, тогда они выручат конкретно

@3D Homer · 06.04.2015, 00:27

Я могу ответить на некоторые вопросы, но у меня нет полного решения.

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

Извините, я не вижу, как можно цитировать сообщение и как можно использовать LaTeX. Не подскажете?

@ZGold · 06.04.2015, 00:37

3D Homer, У меня немножко другое задание, посмотрите, пожалуйста

@VSI · 06.04.2015, 06:49

ZGold, НА БУДУЩЕЕ: размещение задания и решения в виде картинок и других файлов с их текстом - запрещено Правилами форума (5.18). Задания и решения надо перепечатывать на форум (для набора формул есть встроенный редактор).

@3D Homer · 06.04.2015, 16:10

ZGold, как у вас определяются геделевы номера функциональных букв?

Вы используете учебник Мендельсона? Какое издание?

@ZGold · 07.04.2015, 22:11

3D Homer, Издательство "Наука", Москва, 1971 год

Добавлено через 21 час 14 минут
3D Homer, именно, учебник Мендельсона

@3D Homer · 07.04.2015, 23:30

Согласно Мендельсону, $https://www.cyberforum.ru/cgi-bin/latex.cgi?g(f^n_k)=9+8(2^n3^k)$ . Предикат $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(m)=\exists n,k\ge1.\;m=9+8(2^n3^k)$ , безусловно, примитивно рекурсивный. ПРФ (функции) позволяют производить арифметические действия, определять делимость и т.п. С помощью ПРП (предиката) можно сказать, например: для всех чисел $https://www.cyberforum.ru/cgi-bin/latex.cgi?j$ не превосходящих $https://www.cyberforum.ru/cgi-bin/latex.cgi?p$ , если $https://www.cyberforum.ru/cgi-bin/latex.cgi?j$ — простое число и делит $https://www.cyberforum.ru/cgi-bin/latex.cgi?p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?j=2$ или $https://www.cyberforum.ru/cgi-bin/latex.cgi?j=3$ .

@ZGold · 07.04.2015, 23:51

3D Homer, Огромное спасибо! А как доказать вот это: FL(x): x есть геделев номер функциональной буквы ?

@3D Homer · 08.04.2015, 00:03

Это разве не определение FL(x)? По-моему, это то, что я назвал P(x) в посте №14.

@3D Homer · 03.05.2015, 15:06

Сообщение от ZGold

Хорошо, определение предиката FL(x), как я полагаю, вы дали мне в соответствующей темех

У вас неправильное отношение. Нужно взять учебник Мендельсона, найти в указателе обозначений в конце FL и лично посмотреть определение этого понятия. Если в определении есть непонятные термины, то их тоже можно посмотреть в предметном указателе. В частности, нужно понять определение примитивно рекурсивного свойства (предиката). У меня FL определяется в разделе 3.4 после упражнения3.34, но у меня четвертое издание на английском языке. А конкретный пример этого определения дан в самом начале раздела 3.4: там есть равенство $https://www.cyberforum.ru/cgi-bin/latex.cgi?g(f^n_k)=\dots$ (правда, в английском издании правая часть, кажется, другая, чем в сообщении 14).

Сообщение от ZGold

а как теперь его доказать ?

Доказать определение? Определения не доказывают.

Сообщение от ZGold

(В учебнике я так и не нашел доказательства, что именно x - геделев номер функциональной буквы)

А вы можете доказать, что именно x — это наименьшее натуральное число, представимое в виде суммы двух кубов натуральных чисел двумя различными способами? Пока вы не скажете, что x = 1729, вы не сможете сделать это. Так что именно нужно доказать?

@ZGold · 17.05.2015, 14:50

3D Homer, Привет! Спасибо за помощь, почти разобрался. Но есть вопрос, зачем в выражении нужны кванторы (и именно ограниченные), что они показывают ? Заранее благодарю!

@3D Homer · 17.05.2015, 23:13

Сообщение от ZGold

зачем в выражении нужны кванторы

Ну вы же должны сказать, что m — код, если существуют некоторые степени чисел 2 и 3, дающие в произведении m (или что-то вроде того). Если кванторы ограниченные, то предикат, их содержащий, может по-прежнему быть примитивно рекурсивным. Ограниченный квантор имеет эффект цикла for в языке программирования: он просто проверяет данное примитивно рекурсивное условие определенное количество раз. Если это количество известно заранее, то алгоритм проверки понятен. Если же квантор неограничен, то, возможно, нужно проверять условие для всех натуральных чисел. Даже если условие, которое нужно проверить для каждого числа, примитивно рекурсивно, непонятно, как можно за ограниченное время проверить его для всех чисел.

@ZGold · 22.05.2015, 00:53

3D Homer, Большое спасибо! Но препода все равно не устраивает мой ответ. Если вообще убрать кванторы, то выражение все равно останется примитивно - рекурсивным. Он требует провести аналогию: подставить в словесное определение предиката FL(x) значение и сравнивать с письменным видом.(Когда предикат истинен и когда ложен) Не понимаю в чем фишка

@E}\|{\|/\|\|{ 1 / 1 / 2 Регистрация: 03.07.2012 Сообщений: 5
		1
	Доказать, что предикат является (или не является) (примитивно) рекурсивным 03.07.2012, 18:28. Показов 5737. Ответов 20 Метки нет (Все метки) Нужна курсовая по теме. Если у кого то есть хоть какая то информация - буду очень признателен. Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным: «х есть геделев номер частного случая схемы логических аксиом (6)» Сам предикат во вложениях. (Мендельсон: с. 151 - ) Изображения 0

Psilon Master of Orion 6098 / 4954 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	03.07.2012, 19:44	2
	Не по теме: E}\|{\|/\|\|{, судя по заданию, похоже на Волкова из МАИ... :) Вроде знакомый такой курсач делал, надо спросить 1

@E}\|{\|/\|\|{ 1 / 1 / 2 Регистрация: 03.07.2012 Сообщений: 5
	03.07.2012, 20:21 [ТС]	3
	Psilon, да, именно Волков. Будь добр, спроси. Я даже купить готов. 0

@НектоЯрик 0 / 0 / 0 Регистрация: 13.12.2012 Сообщений: 5
	17.10.2013, 18:31	4
	Psilon, здравствуйте, могли бы вы снова обратиться к вашему другу и спросить про данную курсовую? у меня похожий вариант. рекурсивность я доказал, а как быть с геделевой нумерцией - без понятия =( 0

@ZGold 0 / 0 / 0 Регистрация: 04.04.2015 Сообщений: 7
	04.04.2015, 21:04	5
	Psilon, Привет! У тебя не осталось этой курсовой, можешь, посмотреть, пожалуйста ? 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1150 Регистрация: 01.09.2014 Сообщений: 9,657
	05.04.2015, 21:57	6
	Если есть конкретные вопросы, то буду рад ответить. 0

@VSI Модератор $Эксперт по математике/физике$ 5240 / 4027 / 1385 Регистрация: 30.07.2012 Сообщений: 12,288
	05.04.2015, 22:00	7
	ZGold, 3D Homer, обращайте внимание на даты создания тем... 0

@ZGold 0 / 0 / 0 Регистрация: 04.04.2015 Сообщений: 7
	05.04.2015, 23:58	8
	3D Homer, привет! Сможешь помочь ? VSI, Уважаемый Модератор, может быть у них остались еще материалы по этой теме, тогда они выручат конкретно 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1150 Регистрация: 01.09.2014 Сообщений: 9,657
	06.04.2015, 00:27	9
	Я могу ответить на некоторые вопросы, но у меня нет полного решения. Почти всякий разумный предикат является примитивно рекурсивным. В данном случае можно даже написать программу на каком-нибудь языке программирования, которая будет проверять, что строчка имеет нужный вид. Извините, я не вижу, как можно цитировать сообщение и как можно использовать LaTeX. Не подскажете? 0

@ZGold 0 / 0 / 0 Регистрация: 04.04.2015 Сообщений: 7
	06.04.2015, 00:37	10
	3D Homer, У меня немножко другое задание, посмотрите, пожалуйста Миниатюры 0

	22.05.2015, 00:53

@VSI Модератор $Эксперт по математике/физике$ 5240 / 4027 / 1385 Регистрация: 30.07.2012 Сообщений: 12,288
	06.04.2015, 06:49	11
	ZGold, НА БУДУЩЕЕ: размещение задания и решения в виде картинок и других файлов с их текстом - запрещено Правилами форума (5.18). Задания и решения надо перепечатывать на форум (для набора формул есть встроенный редактор). 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1150 Регистрация: 01.09.2014 Сообщений: 9,657
	06.04.2015, 16:10	12
	ZGold, как у вас определяются геделевы номера функциональных букв? Вы используете учебник Мендельсона? Какое издание? 0

@ZGold 0 / 0 / 0 Регистрация: 04.04.2015 Сообщений: 7
	07.04.2015, 22:11	13
	3D Homer, Издательство "Наука", Москва, 1971 год Добавлено через 21 час 14 минут 3D Homer, именно, учебник Мендельсона 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1150 Регистрация: 01.09.2014 Сообщений: 9,657
	07.04.2015, 23:30	14
	Согласно Мендельсону, $https://www.cyberforum.ru/cgi-bin/latex.cgi?g(f^n_k)=9+8(2^n3^k)$ . Предикат $https://www.cyberforum.ru/cgi-bin/latex.cgi?P(m)=\exists n,k\ge1.\;m=9+8(2^n3^k)$ , безусловно, примитивно рекурсивный. ПРФ (функции) позволяют производить арифметические действия, определять делимость и т.п. С помощью ПРП (предиката) можно сказать, например: для всех чисел $https://www.cyberforum.ru/cgi-bin/latex.cgi?j$ не превосходящих $https://www.cyberforum.ru/cgi-bin/latex.cgi?p$ , если $https://www.cyberforum.ru/cgi-bin/latex.cgi?j$ — простое число и делит $https://www.cyberforum.ru/cgi-bin/latex.cgi?p$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?j=2$ или $https://www.cyberforum.ru/cgi-bin/latex.cgi?j=3$ . 1

@ZGold 0 / 0 / 0 Регистрация: 04.04.2015 Сообщений: 7
	07.04.2015, 23:51	15
	3D Homer, Огромное спасибо! А как доказать вот это: FL(x): x есть геделев номер функциональной буквы ? 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1150 Регистрация: 01.09.2014 Сообщений: 9,657
	08.04.2015, 00:03	16
	Это разве не определение FL(x)? По-моему, это то, что я назвал P(x) в посте №14. 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1150 Регистрация: 01.09.2014 Сообщений: 9,657
	03.05.2015, 15:06	17
	Сообщение от ZGold Хорошо, определение предиката FL(x), как я полагаю, вы дали мне в соответствующей темех У вас неправильное отношение. Нужно взять учебник Мендельсона, найти в указателе обозначений в конце FL и лично посмотреть определение этого понятия. Если в определении есть непонятные термины, то их тоже можно посмотреть в предметном указателе. В частности, нужно понять определение примитивно рекурсивного свойства (предиката). У меня FL определяется в разделе 3.4 после упражнения3.34, но у меня четвертое издание на английском языке. А конкретный пример этого определения дан в самом начале раздела 3.4: там есть равенство $https://www.cyberforum.ru/cgi-bin/latex.cgi?g(f^n_k)=\dots$ (правда, в английском издании правая часть, кажется, другая, чем в сообщении 14). Сообщение от ZGold а как теперь его доказать ? Доказать определение? Определения не доказывают. Сообщение от ZGold (В учебнике я так и не нашел доказательства, что именно x - геделев номер функциональной буквы) А вы можете доказать, что именно x — это наименьшее натуральное число, представимое в виде суммы двух кубов натуральных чисел двумя различными способами? Пока вы не скажете, что x = 1729, вы не сможете сделать это. Так что именно нужно доказать? 1

@ZGold 0 / 0 / 0 Регистрация: 04.04.2015 Сообщений: 7
	17.05.2015, 14:50	18
	3D Homer, Привет! Спасибо за помощь, почти разобрался. Но есть вопрос, зачем в выражении нужны кванторы (и именно ограниченные), что они показывают ? Заранее благодарю! 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1150 Регистрация: 01.09.2014 Сообщений: 9,657
	17.05.2015, 23:13	19
	Сообщение от ZGold зачем в выражении нужны кванторы Ну вы же должны сказать, что m — код, если существуют некоторые степени чисел 2 и 3, дающие в произведении m (или что-то вроде того). Если кванторы ограниченные, то предикат, их содержащий, может по-прежнему быть примитивно рекурсивным. Ограниченный квантор имеет эффект цикла for в языке программирования: он просто проверяет данное примитивно рекурсивное условие определенное количество раз. Если это количество известно заранее, то алгоритм проверки понятен. Если же квантор неограничен, то, возможно, нужно проверять условие для всех натуральных чисел. Даже если условие, которое нужно проверить для каждого числа, примитивно рекурсивно, непонятно, как можно за ограниченное время проверить его для всех чисел. 1