2014 dxdy logo

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

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


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


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Диагональный метод Кантора и вычислимые числа
Сообщение14.01.2020, 05:12 


12/01/20
2
В диагональном методе Кантора обычно для простоты рассматриваются числа на полуинтервале [0; 1), а сами числа представляются в виде последовательностей нулей и единиц - знаков после запятой в двоичной записи числа.

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

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

Отсюда напрашивается один из возможных выводов: либо множество вычислимых чисел континуально (но мы-то знаем, что это не так), либо - oh my gosh! - диагональный метод на самом-то деле ничего не доказывает и ничего не опровергает.

Как это все понимать?

 Профиль  
                  
 
 Re: Диагональный метод Кантора и вычислимые числа
Сообщение14.01.2020, 05:52 
Заслуженный участник
Аватара пользователя


08/11/11
5871
Nyan-Cat в сообщении #1435083 писал(а):
Как это все понимать?


Посмотреть в ту же статью википедии, но на английском. Там есть ответ.

 Профиль  
                  
 
 Re: Диагональный метод Кантора и вычислимые числа
Сообщение14.01.2020, 14:00 
Заслуженный участник
Аватара пользователя


27/04/09
27145
Кстати можно не писать «конечного алгоритма». Когда завозят обобщения вычислимости, тогда и добавляют уточнения.

UPD. Я бы вообще предложил рассматривать просто вычислимые (и тотальные) последовательности (двоичные, десятичные, натуральных чисел, не важно): явление там всё то же, а деталей мешающих минимум.

 Профиль  
                  
 
 Re: Диагональный метод Кантора и вычислимые числа
Сообщение14.01.2020, 14:42 
Заслуженный участник
Аватара пользователя


16/07/14
4021
Москва
Nyan-Cat в сообщении #1435083 писал(а):
Любое число в нашем списке можно вычислить до любой заданной точности с помощью конечного алгоритма, зная лишь его (числа) порядковый номер и желаемую точность
Уточните, как вы это предлагаете сделать (подсказка: на самом деле это сделать нельзя).

 Профиль  
                  
 
 Re: Диагональный метод Кантора и вычислимые числа
Сообщение14.01.2020, 16:53 


12/01/20
2
g______d в сообщении #1435085 писал(а):
Посмотреть в ту же статью википедии, но на английском. Там есть ответ.

Ок, попробую вникнуть, язык сложноват (для меня).

mihaild в сообщении #1435132 писал(а):
Уточните, как вы это предлагаете сделать (подсказка: на самом деле это сделать нельзя).

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

 Профиль  
                  
 
 Re: Диагональный метод Кантора и вычислимые числа
Сообщение14.01.2020, 17:10 
Заслуженный участник


31/12/15
836
Нумеруются не все вычислимые последовательности, а все частичные (не обязательно везде определённые) вычислимые последовательности. Диагональ тоже вычислима, но в проблемных местах не определена. Распознать по номеру, является ли последовательность всюду определённой, нельзя.

 Профиль  
                  
 
 Re: Диагональный метод Кантора и вычислимые числа
Сообщение14.01.2020, 23:40 
Заслуженный участник
Аватара пользователя


27/04/09
27145
Nyan-Cat в сообщении #1435151 писал(а):
Хм, подумал-подумал, и вот что надумал: то есть, не смотря на то, что каждое число можно вычислить алгоритмом, множество всех требуемых алгоритмов бесконечно, и поэтому общий алгоритм (с входными данными "Порядковый номер числа, желаемая точность") перестает быть "конечным"? И следовательно, число, образованное главной диагональю - невычислимое?
Нет, мог бы существовать алгоритм, выдающий по каждому натуральному числу код алгоритма, вычисляющего число с таким номером в списке. Но в данном случае не существует, что и показывается диагональным аргументом. Не из-за того что что-то там бесконечно, просто потому что его существование влечёт противоречие.

-- Ср янв 15, 2020 01:40:35 --

(Это для случая именно тотальных последовательностей.)

 Профиль  
                  
 
 Re: Диагональный метод Кантора и вычислимые числа
Сообщение14.01.2020, 23:42 
Заслуженный участник
Аватара пользователя


08/11/11
5871
Nyan-Cat в сообщении #1435151 писал(а):
Ок, попробую вникнуть, язык сложноват (для меня).


Уже было несколько ответов. Могу попробовать сформулировать так: чтобы получить противоречие, нужно перечислить все вычислимые числа. Казалось бы, в чём проблема? Каждое вычислимое число задаётся алгоритмом, и все алгоритмы можно перечислить. Проблема в том, что не каждый алгоритм задаёт какое-то число, и нужно научиться пропускать те, которые не задают. Последняя задача заведомо не проще, чем проблема останова, про которую известно, что она алгоритмически неразрешима.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

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



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

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


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

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