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

[DeBill]

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

[Anton_Peplov]

DeBill в сообщении #1096328 писал(а):

что, иррациональные числа можно считать с любой точностью?

В теории алгоритмов реальный компьютер с конечной памятью заменяют идеализацией - машиной Тьюринга с бесконечной лентой, машиной с неограниченными регистрами или еще чем-нибудь подобным.

[whitefox]

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

Здесь надо как-то формализовать слово "доказать"

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

[Anton_Peplov]

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

Впрочем, любое доказательство (ну почти любое ) можно представить в виде конечного текста. Следовательно множество доказательств перечислимо

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

[whitefox]

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

Конечно, если предположить, что оно еще и разрешимо во множестве всех текстов

Конечно разрешимо, ведь мы выбросим в корзину любой текст не начинающийся со слова "доказательство".
Но по существу вы правы — в своём утверждении

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

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

я имел ввиду именно формальные доказательства.

[Anton_Peplov]

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

Конечно разрешимо, ведь мы выбросим в корзину любой текст не начинающийся со слова "доказательство".

А из тех, которые им начинаются, ни один не бросим в корзину?:)
Давайте признаем, что по части формальных доказательств Вы правы, а про неформальные пошутили, и закончим на этом.

[whitefox]

Так я для того везде смайлики и ставил.

[Anton_Peplov]

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

[Someone]

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}}$ лет и всё ещё результата не выдал. Существует доказательство или нет? Неизвестно.

[gomomorfizm]

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

[Someone]

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

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

[whitefox]

Someone в сообщении #1096380 писал(а):

множества аксиом и правил вывода теории должны быть алгоритмически перечислимыми (по-моему, распознаваемости всё-таки не требуется)

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

[gomomorfizm]

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

[Someone]

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

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

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

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

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

С помощью теоремы о том, что проблема остановки алгоритма является алгоритмически неразрешимой.

[whitefox]

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