2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Невычислимые числа.
Сообщение03.02.2016, 00:09 
Аватара пользователя


17/10/15
110
Недавно прочитал статью про невычислимые числа. Автор писал, что существование невычислимых чисел доказывает несчетность множества действительных чисел, но Кантором было показано, что даже множество иррациональных чисел несчетно.(Хотя меня есть подозрения что первый, но я все же спрошу), кто ошибся автор или Кантор? И как вообще пришли к выводу о существовании невысчислимых чисел?

 Профиль  
                  
 
 Re: Неисчислимые числа.
Сообщение03.02.2016, 00:20 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
gomomorfizm в сообщении #1096282 писал(а):
существование неисчислимых чисел доказывает несчетность множества действительных чисел, но Кантором было показано, что даже множество иррациональных чисел несчетно.(Хотя меня есть подозрения что первый, но я все же спрошу), кто ошибся автор или Кантор?

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

 Профиль  
                  
 
 Re: Неисчислимые числа.
Сообщение03.02.2016, 00:27 
Аватара пользователя


17/10/15
110
Brukvalub
Вычислимое число это такое, которое может быть вычислено на компьютере с любой степенью точности.

 Профиль  
                  
 
 Re: Неисчислимые числа.
Сообщение03.02.2016, 00:31 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
gomomorfizm в сообщении #1096288 писал(а):
Brukvalub
Вычислимое число это такое, которое может быть вычислено на компьютере с любой степенью точности.

Спасибо, но выше шла речь о "неисчислимых числах", а не о ВЫчислимом числе.

 Профиль  
                  
 
 Re: Неисчислимые числа.
Сообщение03.02.2016, 00:34 
Аватара пользователя


17/10/15
110
Brukvalub
Прошу прощения, это я напутал.

 Профиль  
                  
 
 Re: Неисчислимые числа.
Сообщение03.02.2016, 00:40 
Заслуженный участник
Аватара пользователя


19/12/10
1546
gomomorfizm в сообщении #1096282 писал(а):
Автор писал, что существование неисчислимых чисел доказывает несчетность множества действительных чисел

Может быть автор писал, что существование не вычислимых чисел доказывается несчётностью множества действительных чисел? Так как множество вычислимых чисел счётно, ибо счётно число алгоритмов их вычисляющих.

 Профиль  
                  
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 00:45 
Аватара пользователя


17/10/15
110
whitefox
Тогда множество иррациональных чисел счетно?

 Профиль  
                  
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 00:48 
Заслуженный участник
Аватара пользователя


19/12/10
1546
С чего бы это? Вы полагаете, что все иррациональные вычислимы?

 Профиль  
                  
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 00:54 
Аватара пользователя


17/10/15
110
whitefox
Смотрите, пусть у нас есть число $\psi$. Какими свойствами оно должно обладать, чтобы мы могли точно сказать, что оно невычислимо? Как доказать, что $\psi$ – иррационально?

 Профиль  
                  
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 01:03 
Заслуженный участник
Аватара пользователя


20/08/14
8062
gomomorfizm в сообщении #1096302 писал(а):
Какими свойствами оно должно обладать, чтобы мы могли точно сказать, что оно невычислимо?
От противного, дамы и господа, от противного. Если есть алгоритм, вычисляющий это число, то из него можно слепить какой-нибудь алгоритм, о котором заведомо известно, что его не существует. Например (и это стандартный путь в таких доказательствах) решающий проблему остановки универсального алгоритма. Как доказывается иррациональность, я не знаю, но подозреваю, что тоже от противного.
Вы, однако, кажется, смешиваете две задачи. Чтобы доказать, что "подавляющее большинство" (континуум против счетного множества) действительных чисел невычислимо, совсем не обязательно предъявлять хоть одно такое число. Достаточно, как уже было сказано выше, заметить, что множество всех алгоритмов (и, значит, всех вычислимых чисел) счетно, а множество всех действительных чисел - нет.

 Профиль  
                  
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 01:04 
Заслуженный участник
Аватара пользователя


19/12/10
1546
gomomorfizm в сообщении #1096302 писал(а):
пусть у нас есть число $\psi$

А что вы под этим понимаете? Какой-то алгоритм вычисляющий это число?

 Профиль  
                  
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 01:08 
Заслуженный участник
Аватара пользователя


20/08/14
8062
Подозреваю, что под этим понимается все-таки определение. Например, "отношение длины окружности к диаметру" или "корень уравнения $x^2 = 2$". Из этих определений вовсе не очевидно, рациональны ли эти числа и если нет, то вычислимы ли. Однако это можно доказать.
Точно так же можно доказать, что заданная своим определением константа Хайтина невычислима.

 Профиль  
                  
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 01:36 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Anton_Peplov в сообщении #1096311 писал(а):
"отношение длины окружности к диаметру" или "положительный корень уравнения $x^2 = 2$"
(подчёркнутое моё)

Ну, для этих-то чисел мы можем указать алгоритмы их вычисляющие, доказав тем самым их вычислимость. Забавно, что множество алгоритмов, вычисляющих какое-то число, не перечислимо. Следовательно существуют алгоритмы, вычисляющие это число, для которых не возможно доказать, что они это делают. :-)

 Профиль  
                  
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 01:45 
Заслуженный участник
Аватара пользователя


20/08/14
8062
whitefox в сообщении #1096318 писал(а):
Ну, для этих-то чисел мы можем указать алгоритмы их вычисляющие, доказав тем самым их вычислимость.
Можем, конечно. Я говорю о том, что число задается своим определением, а уж потом ищется алгоритм, доказывается иррациональность и происходят прочие интересные события. Так что
gomomorfizm в сообщении #1096302 писал(а):
пусть у нас есть число $\psi$.
я бы понимал как "пусть у нас есть определение некоторого числа". Которое может оказаться, например, определением константы Хайтина. А может и не оказаться.

 Профиль  
                  
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 02:08 
Заслуженный участник
Аватара пользователя


20/08/14
8062
whitefox в сообщении #1096318 писал(а):
Забавно, что множество алгоритмов, вычисляющих какое-то число, не перечислимо. Следовательно существуют алгоритмы, вычисляющие это число, для которых не возможно доказать, что они это делают. :-)
Из неперечислимости, конечно, следует неразрешимость, т.е. у нас нет алгоритма, который для любого алгоритма $A$ решал бы вопрос, вычисляет ли он число $x$. Но как из этого получить Ваше утверждение, я не знаю. Здесь надо как-то формализовать слово "доказать", чтобы разбираться, что можно, а что нельзя доказать - т.е. построить формальную теорию.

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

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



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

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


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

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