Форум программистов, компьютерный форум, киберфорум
Мат. логика и множества
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/8: Рейтинг темы: голосов - 8, средняя оценка - 4.50
0 / 0 / 0
Регистрация: 13.01.2019
Сообщений: 13
1

Покажите, что если бы теорема Райса–Успенского была неверна, то и теорема Клини была бы неверна

19.01.2019, 17:20. Показов 1653. Ответов 4
Метки нет (Все метки)

Покажите, что если бы теорема Райса–Успенского была неверна, то и теорема Клини была бы неверна.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.01.2019, 17:20
Ответы с готовыми решениями:

Теорема РАЙСА
Срочно нужна теорема Райса с доказательством. Может кто подскажет где ее найти?!....(( ... ...

А что, если Великая теорема Ферма - не верна?!
Здравствуйте, товарищи форумчане! Всех вас поздравляю с Новым 2014 годом! Желаю счастья, любви,...

Теорема Ферма и теорема Безу
Уважаемые господа, предлагаю вашему вниманию доказательство Великой теоремы Ферма с помощью...

Какая-то малость неверна(
Задание:дана квадратная матрица размерностью NxN(любая). Сформировать одномерный массив из...

4
Эксперт по математике/физике
3486 / 2476 / 810
Регистрация: 01.09.2014
Сообщений: 6,754
19.01.2019, 22:07 2
Напомните теорему Клини, потому что их несколько.

Вообще формулировка задачи странная. В предположении, что теорема Райса неверна, мы получаем противоречие, так как она также верна. А из противоречия следует что угодно, в частности, как теорема Клини, так и ее отрицание. Я бы потребовал от преподавателя серьезного объяснения, потому что это ленивая постановка задачи. Наверное, имеется в виду доказать ¬РУ -> ¬K, то есть K -> РУ, в некоторой слабой теории, в которой нельзя доказать ни K, ни РУ (здесь, естественно, РУ означает теорему Райса-Успенского, а К — теорему Клини). Но что это за слабая теория, непонятно.
0
0 / 0 / 0
Регистрация: 13.01.2019
Сообщений: 13
19.01.2019, 23:08  [ТС] 3
Если функция U
главная, то для любой вычислимой функции s: N → N найдется такое
число n0 ∈ N, что fn0 ≡ fs(n0) (теорема о неподвижной точке)

Добавлено через 6 минут
////
может надо начать от противного ,пусть существует разрешимое нетривиальное свойство
вычислимых функций.
0
0 / 0 / 0
Регистрация: 13.01.2019
Сообщений: 13
21.01.2019, 20:40  [ТС] 4
Добавлено через 21 секунду
3D Homer, не так ли?
0
Эксперт по математике/физике
3486 / 2476 / 810
Регистрация: 01.09.2014
Сообщений: 6,754
22.01.2019, 02:11 5
Цитата Сообщение от eeeeeeeeei Посмотреть сообщение
для любой вычислимой функции s: N → N найдется такое
число n0 ∈ N, что fn0 ≡ fs(n0) (теорема о неподвижной точке)
Википедия говорит, что s должна быть тотальной вычислимой.

Цитата Сообщение от eeeeeeeeei Посмотреть сообщение
может надо начать от противного ,пусть существует разрешимое нетривиальное свойство
вычислимых функций.
Действительно, пусть теорема Райса неверна и пусть A — нетривиальное множество функций, индексное множество которого разрешимо. Существует f ∈ A и g ∉ A. Пусть m — один из номеров f, а n — один из номеров g. Определим s(x) следующим образом: https://www.cyberforum.ru/cgi-bin/latex.cgi?s(x)=\begin{cases}n,&f_x\in A\\m,&f_x\notin A\end{cases}. Тогда s вычислима и тотальна (здесь используется разрешимость индексного множества). Значит, https://www.cyberforum.ru/cgi-bin/latex.cgi?f_{s(x)}\in A\Longleftrightarrow f_x\,\notin A. Соответственно, https://www.cyberforum.ru/cgi-bin/latex.cgi?f_{s(x)}\simeq f_x невозможно ни для какого x.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.01.2019, 02:11

Теория вероятностей неверна
У меня есть программа, которая работает с нарушением теории вероятностей. Проблема в том, что нет...

Подскажите, пожалуйста, почему программа неверна
Проверка на сайте http://acm.timus.ru/ Нужно найти сумму всех целых чисел, лежащих между 1 и N...

Неверна звукопередача в Counter-Strike: Source
Привет ребят! Как делишки?!) В общем дело такое. Проблемы со звуком у меня какие-то. Например...

Стандартная формула нахождения угла между векторами неверна
Приглашаю всех этом убедиться. Вот вектора: a(-2,-2, 0), b (-1, 1, -2) Угол между ними какой...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.