Невычислимые числа.

[gomomorfizm]

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

[Brukvalub]

gomomorfizm в сообщении #1096282 писал(а):

существование неисчислимых чисел доказывает несчетность множества действительных чисел, но Кантором было показано, что даже множество иррациональных чисел несчетно.(Хотя меня есть подозрения что первый, но я все же спрошу), кто ошибся автор или Кантор?

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

[gomomorfizm]

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

[Brukvalub]

gomomorfizm в сообщении #1096288 писал(а):

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

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

[gomomorfizm]

Brukvalub
Прошу прощения, это я напутал.

[whitefox]

gomomorfizm в сообщении #1096282 писал(а):

Автор писал, что существование неисчислимых чисел доказывает несчетность множества действительных чисел

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

[gomomorfizm]

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

[whitefox]

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

[gomomorfizm]

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

[Anton_Peplov]

gomomorfizm в сообщении #1096302 писал(а):

Какими свойствами оно должно обладать, чтобы мы могли точно сказать, что оно невычислимо?

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

[whitefox]

gomomorfizm в сообщении #1096302 писал(а):

пусть у нас есть число $\psi$

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

[Anton_Peplov]

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

[whitefox]

Anton_Peplov в сообщении #1096311 писал(а):

"отношение длины окружности к диаметру" или "положительный корень уравнения $x^2 = 2$"

(подчёркнутое моё)

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

[Anton_Peplov]

whitefox в сообщении #1096318 писал(а):

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

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

gomomorfizm в сообщении #1096302 писал(а):

пусть у нас есть число $\psi$.

я бы понимал как "пусть у нас есть определение некоторого числа". Которое может оказаться, например, определением константы Хайтина. А может и не оказаться.

[Anton_Peplov]

whitefox в сообщении #1096318 писал(а):

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

Из неперечислимости, конечно, следует неразрешимость, т.е. у нас нет алгоритма, который для любого алгоритма $A$ решал бы вопрос, вычисляет ли он число $x$. Но как из этого получить Ваше утверждение, я не знаю. Здесь надо как-то формализовать слово "доказать", чтобы разбираться, что можно, а что нельзя доказать - т.е. построить формальную теорию.