2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 02:19 
Всем привет!
А я вот что-то тут не понимаю: что, иррациональные числа можно считать с любой точностью? :D
А как быть с рассуждением, которому меня научили в детстве:
Компутер - это такая большая железяка, с офигительно большой (но конечной) памятью, в которой содержится вся программа, входные данные, и промежуточные вычисления. Потому он может находиться лишь в конечном числе состояний. Значит, в некоторый момент случится повтор состояний. С этого момента он будет выдавать периодическую последовательность знаков числа. Периодичность влечет рациональность - не сдюжит комп с иррациональностью (даже такой хорошей, как $e$)...

 
 
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 02:24 
Аватара пользователя
DeBill в сообщении #1096328 писал(а):
что, иррациональные числа можно считать с любой точностью?
В теории алгоритмов реальный компьютер с конечной памятью заменяют идеализацией - машиной Тьюринга с бесконечной лентой, машиной с неограниченными регистрами или еще чем-нибудь подобным.

 
 
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 02:27 
Аватара пользователя
Anton_Peplov в сообщении #1096327 писал(а):
Здесь надо как-то формализовать слово "доказать"

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

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

 
 
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 02:48 
Аватара пользователя
Anton_Peplov в сообщении #1096334 писал(а):
Конечно, если предположить, что оно еще и разрешимо во множестве всех текстов

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

 
 
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 02:58 
Аватара пользователя
whitefox в сообщении #1096337 писал(а):
Конечно разрешимо, ведь мы выбросим в корзину любой текст не начинающийся со слова "доказательство". :-)
А из тех, которые им начинаются, ни один не бросим в корзину?:)
Давайте признаем, что по части формальных доказательств Вы правы, а про неформальные пошутили, и закончим на этом.

 
 
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 03:08 
Аватара пользователя
Так я для того везде смайлики и ставил. :-)

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

 
 
 
 Re: Неисчислимые числа.
Сообщение03.02.2016, 11:54 
Аватара пользователя
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 
Аватара пользователя
Someone
Скажите, а с помощью какого алгоритма была доказана невычислимость константы Хайтина?

 
 
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 12:36 
Аватара пользователя
gomomorfizm в сообщении #1096389 писал(а):
Скажите, а с помощью какого алгоритма была доказана невычислимость константы Хайтина?
:shock:

 
 
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 12:45 
Аватара пользователя
Someone в сообщении #1096380 писал(а):
множества аксиом и правил вывода теории должны быть алгоритмически перечислимыми (по-моему, распознаваемости всё-таки не требуется)

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

 
 
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 13:00 
Аватара пользователя
Someone
С помощью чего можно доказать, что не существует алгоритма вычисляющего константу Хайтина?

 
 
 
 Re: Невычислимые числа.
Сообщение03.02.2016, 13:13 
Аватара пользователя
Это можно обойти.
Алгоритм порождает первый синтаксически правильный текст и начинает проверку, что какое-то высказывание в этом тексте является аксиомой. Он запускает алгоритм перечисления аксиом, получает первую аксиому, сравнивает, получает вторую, сравнивает, и так далее. Время от времени он от этого процесса отвлекается, генерирует второй синтаксически правильный текст, и далее уже проверяет два текста. Время от времени он от них отвлекается, генерирует третий текст, и так далее. Время от времени проверка некоторых текстов будет завершаться. Если среди них окажется доказательство требуемого утверждения, то алгоритм остановится, выдав в качестве результата найденное доказательство. Если такое доказательство существует, алгоритм рано или поздно до него доберётся. Если не существует — будет работать до бесконечности.

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

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

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

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

 
 
 [ Сообщений: 30 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group