2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 02:19 
Заслуженный участник


10/01/16
2315
Всем привет!
А я вот что-то тут не понимаю: что, иррациональные числа можно считать с любой точностью? :D
А как быть с рассуждением, которому меня научили в детстве:
Компутер - это такая большая железяка, с офигительно большой (но конечной) памятью, в которой содержится вся программа, входные данные, и промежуточные вычисления. Потому он может находиться лишь в конечном числе состояний. Значит, в некоторый момент случится повтор состояний. С этого момента он будет выдавать периодическую последовательность знаков числа. Периодичность влечет рациональность - не сдюжит комп с иррациональностью (даже такой хорошей, как $e$)...

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


20/08/14
8062
DeBill в сообщении #1096328 писал(а):
что, иррациональные числа можно считать с любой точностью?
В теории алгоритмов реальный компьютер с конечной памятью заменяют идеализацией - машиной Тьюринга с бесконечной лентой, машиной с неограниченными регистрами или еще чем-нибудь подобным.

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


19/12/10
1546
Anton_Peplov в сообщении #1096327 писал(а):
Здесь надо как-то формализовать слово "доказать"

Именно формальные доказательства и имелись ввиду. Впрочем, любое доказательство (ну почти любое :-) ) можно представить в виде конечного текста. Следовательно множество доказательств перечислимо, следовательно перечислимо и множество доказуемых утверждений. Остаётся только отфильтровать утверждения о том, что какой-то алгоритм вычисляет наше число. Если бы это было справедливо для любого такого алгоритма, то и всё их множество было бы перечислимо, что, однако, неверно.

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


20/08/14
8062
whitefox в сообщении #1096332 писал(а):
Впрочем, любое доказательство (ну почти любое :-) ) можно представить в виде конечного текста. Следовательно множество доказательств перечислимо
Не понял "следовательно". По-моему, из того, что доказательство - конечный текст, следует только, что множество всех доказательств счетно.
Конечно, если предположить, что оно еще и разрешимо во множестве всех текстов, т.е. существует алгоритм, который для каждого текста выясняет, является ли он доказательством, то все получается по-Вашему (и, кстати, мы тут же цепляем на свою голову обе теоремы Геделя). Но если такого алгоритма нет (а в неформальной теории его скорее нет), то я не понимаю, откуда берется "следовательно".

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


19/12/10
1546
Anton_Peplov в сообщении #1096334 писал(а):
Конечно, если предположить, что оно еще и разрешимо во множестве всех текстов

Конечно разрешимо, ведь мы выбросим в корзину любой текст не начинающийся со слова "доказательство". :-)
Но по существу вы правы — в своём утверждении
whitefox в сообщении #1096318 писал(а):
Следовательно существуют алгоритмы, вычисляющие это число, для которых не возможно доказать, что они это делают. :-)
я имел ввиду именно формальные доказательства.

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


20/08/14
8062
whitefox в сообщении #1096337 писал(а):
Конечно разрешимо, ведь мы выбросим в корзину любой текст не начинающийся со слова "доказательство". :-)
А из тех, которые им начинаются, ни один не бросим в корзину?:)
Давайте признаем, что по части формальных доказательств Вы правы, а про неформальные пошутили, и закончим на этом.

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


19/12/10
1546
Так я для того везде смайлики и ставил. :-)

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


20/08/14
8062
Множество всех шуток, увы, неразрешимо во множестве всех текстов, хотя смайлики - хорошая попытка формализации :)

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


23/07/05
17973
Москва
gomomorfizm в сообщении #1096288 писал(а):
Вычислимое число это такое, которое может быть вычислено на компьютере с любой степенью точности.
Это требует уточнения. "Вычислимое число", или конструктивное действительное число (КДЧ) — это пара алгоритмов, один из которых вычисляет последовательность рациональных чисел (то есть, по заданному натуральному числу $n$ находит некоторое рациональное число $r_n$), а другой называется регулятором сходимости в себе и по заданному натуральному числу $n$ вычисляет такое натуральное число $\beta_n$, что для любых $k>\beta_n$, $m>\beta_n$ выполняется неравенство $\lvert r_m-r_k\rvert<2^{-n}$.
Комбинируя эти алгоритмы, мы можем вычислять число КДЧ с любой заданной точностью.

Понятие КДЧ является достаточно жёстким. Существуют различные ослабления этого понятия.

На популярном уровне алгоритм — это пошаговая инструкция, каждый шаг которой выполняется однозначно (при наличии соответствующего исполнителя, естественно). Результат применения алгоритма к исходным данным определяется в момент завершения выполнения инструкции.
Не предполагается, что этот результат должен быть в каком-нибудь смысле полезным, и даже не предполагается, что выполнение инструкции хоть когда-нибудь должно завершиться.
Существует целый ряд формализаций этого понятия: машина Тьюринга, нормальный алгорифм Маркова, частично рекурсивная функция, … Все известные формализации понятия алгоритма являются эквивалентными.

Интересно, что такое направление конструктивизма, как интуиционизм, считает ограничение понятия вычислимости алгоритмами слишком жёстким.

-- Ср фев 03, 2016 12:21:28 --

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

whitefox в сообщении #1096337 писал(а):
Конечно разрешимо, ведь мы выбросим в корзину любой текст не начинающийся со слова "доказательство". :-)
Разумеется, надо ограничиться формальными теориями, удовлетворяющими определённым требованиям.
Во-первых, алфавит теории должен быть конечным.
Во-вторых, синтаксис теории должен быть алгоритмически распознаваемым.
В-третьих, множества аксиом и правил вывода теории должны быть алгоритмически перечислимыми (по-моему, распознаваемости всё-таки не требуется).

Такие формальные теории первого порядка, как арифметика Пеано или теория множеств ZFC этим условиям удовлетворяют.

Понятия "теорема" (обычно употребляются термины "высказывание" или "формула") и "доказательство" являются синтаксическими, поэтому можно построить алгоритм, перечисляющий тексты в заданном алфавите и проверяющий, являются ли эти тексты доказательствами заданной теоремы.
Проблема в следующем: если доказательство теоремы существует, то наш алгоритм "когда-нибудь" его найдёт. Но предположим, что мы его запустили, он проработал уже $10^{10^{10}}$ лет и всё ещё результата не выдал. Существует доказательство или нет? Неизвестно.

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


17/10/15
110
Someone
Скажите, а с помощью какого алгоритма была доказана невычислимость константы Хайтина?

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


23/07/05
17973
Москва
gomomorfizm в сообщении #1096389 писал(а):
Скажите, а с помощью какого алгоритма была доказана невычислимость константы Хайтина?
:shock:

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


19/12/10
1546
Someone в сообщении #1096380 писал(а):
множества аксиом и правил вывода теории должны быть алгоритмически перечислимыми (по-моему, распознаваемости всё-таки не требуется)

Имхо, распознаваемость всё-таки требуется. Ну вот столкнулись мы с очередным предложением о котором автор доказательства утверждает, что оно является аксиомой. Запустили наш алгоритм перечисляющий все аксиомы. Хорошо если автор прав, тогда наш алгоритм когда-нибудь это подтвердит (хотя бы и через $10^{10^{10}}$ лет :-) ). А если автор ошибся?

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


17/10/15
110
Someone
С помощью чего можно доказать, что не существует алгоритма вычисляющего константу Хайтина?

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


23/07/05
17973
Москва
Это можно обойти.
Алгоритм порождает первый синтаксически правильный текст и начинает проверку, что какое-то высказывание в этом тексте является аксиомой. Он запускает алгоритм перечисления аксиом, получает первую аксиому, сравнивает, получает вторую, сравнивает, и так далее. Время от времени он от этого процесса отвлекается, генерирует второй синтаксически правильный текст, и далее уже проверяет два текста. Время от времени он от них отвлекается, генерирует третий текст, и так далее. Время от времени проверка некоторых текстов будет завершаться. Если среди них окажется доказательство требуемого утверждения, то алгоритм остановится, выдав в качестве результата найденное доказательство. Если такое доказательство существует, алгоритм рано или поздно до него доберётся. Если не существует — будет работать до бесконечности.

Но да, наличие алгоритма распознавания существенно упрощает процедуру.

-- Ср фев 03, 2016 13:19:26 --

gomomorfizm в сообщении #1096397 писал(а):
Someone
С помощью чего можно доказать, что не существует алгоритма вычисляющего константу Хайтина?
С помощью теоремы о том, что проблема остановки алгоритма является алгоритмически неразрешимой.

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


19/12/10
1546
Someone
Пардон. Сам же выше говорил о перечислимости множества доказательств, а тут вдруг стал требовать его разрешимости. :?

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

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



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

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


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

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