Существуют ли иррациональные и действительные числа?

[migmit]

Андрей АK в сообщении #404737 писал(а):

В этом вся проблема.

Не вижу проблемы.

[epros]

Андрей АK в сообщении #404724 писал(а):

Я никогда не говорил, что множество рациональных чисел (рациональная система счисления) самая лучшая - я говорил, что она самодостаточная.

Что это значит? Факт заключается в том, что нельзя указать рациональное число, в точности равное $\sqrt{2}$. Это и означает, что $\sqrt{2}$ - иррациональное число.

Андрей АK в сообщении #404724 писал(а):

Т.е. используя ряды рациональных чисел...

Ряд рациональных чисел - это совершенно новый объект. Совершенно не обязательно он будет равен какому-либо рациональному числу. Существует совершенно отдельная проблема как записать на бумаге такой объект, как "ряд рациональных чисел". Как правило, если это вообще возможно, он определяется формулой или алгоритмом.

[hurtsy]

Xaositect в сообщении #404618 писал(а):

Это просто, периметр вписанного в единичную окружность $2^n$-угольника вполне считается конечным алгоритмом и является при увеличении $n$ сколь угодно хорошим приближением числа $2\pi$

Андрей АK в сообщении #404640 писал(а):

Теперь я считаю рациональные/алгебраические числа примером бесконечных алгоритмов, а насчет остального еще надо разобраться - могут ли существовать числа (и алгоритмы) содержащие бесконечно большой объем информации?

А $\pi$ все таки трансцендентное число. Где то (кажется в школе) уже рассматривался процес для вычисления $\pi$, только рассматривались все вписанные и все описанные многоугольники. Наша дискусия имеет такой же шанс на решение, какова вероятность равенства периметров вписанного и описанного многоугольников. С уважением,

[Андрей АK]

Xaositect в сообщении #404743 писал(а):

Андрей АK в сообщении #404737 писал(а):

Да , совершенно верно - это утверждение неверно.

Отлично.
Я сейчас напишу доказательство, а Вы скажете, где ошибка.

Будем обозначать машину, задаваемую программой $x$ символом $M_x$.
1. Допустим, требуемая машина существует. Обозначим эту машину $A$.
Напомню, что мы хотим, чтобы выполнялось следующее:
а) $x$ - не программа => $A(x, y) = 0$
б) $M_x(y)$ останавливается => $A(x, y) = 1$
в) $M_x(y)$ не останавливается => $A(x, y) = 0$

2. Построим на основе программы машины $A$ программу для другой машины $B$, которая принимает один параметр-строку, и работает следующим образом:
Если $A(x, x) = 0$, то $B$ завершает работу.
Если $A(x, x) = 1$, то $B$ продолжает работу бесконечно.
При желании я могу явно выписать преобразование программы машины $A$ в программу машины $B$. Надеюсь, Вы можете и сами это сделать.

3. Обозначим программу машины $B$ буквой $b$, т.е. $B = M_b$. Рассмотрим значение $B(b)$.
Значение $B(b)$ зависит от значения $A(b,b)$. Рассмотрим каждый из трех случаев:
а) случай (а) реализоваться не может, т.к. $b$ является программой некоторой машины.
б) пусть $M_b(b)$ останавливается. Тогда $A(b,b) = 1$ и $B(b)$ зацикливается. Т.к. $B = M_b$, получаем $B(b)$ останавливается => $B(b)$ не останавливается.
в) пусть $M_b(b)$ не останавливается. Тогда $A(b,b) = 0$ и $B(b)$ останавливается. Т.к. $B = M_b$, получаем $B(b)$ не останавливается => $B(b)$ останавливается.

В итоге получаем:
$B(b)$ не останавливается <=> $B(b)$ останавливается.
Противоречие.

Здесь, ошибка в выражении $A(x, x)$
Если в качестве первого параметра вы можете подставить "голый алгоритм", то в качестве второго - это уже будет неверно, поскольку входной параметр для этого есть алгоритм вместе с другим входным параметром.
Т.е.
$A(x, A(x,x))$
Для следующей подстановки (если вы переопределяя переменные пытаетесь вновь подставить весь этот алгоритм в A) вы получите $A(x,A(x, A(x,x)))$ а вовсе не превоначальный вариант $ A(x,x)$ который ,вообще говоря, тоже некорректен, поскольку не было указано, какой самый первый параметр используется в x.
Т.е. пока полностью не сформирован алгоритм A (не указано, какие в него будут передаваться параметры, иначе, этих параметров в природе не существует) нельзя создать и алгоритм B.

Если же вы, создадите "незавершенные" алгоритмы A и B и только только потом так перенаправите ссылки, чтоб они друг друга циклически вызывали, то это у вас будет всего лишь зацикленный код.
Программу с зацикленным кодом можно считать некорректной, которая никогда не завершится.
Поэтому достаточно вставить в одном из участков блок, отлавливающий ситуацию возникновения бесконечных циклов и выводящий после этого конкретный результат (0), как все неопределенности сразу пропадут.

Кроме того есть еще одно место ,где можно указать на ошибку, это:
"Построим на основе программы машины $A$ программу для другой машины $B$, которая принимает один параметр-строку"
Здесь указано , что в качестве параметра передается строка.
Но в этой строке должно быть упакован не только сам код, но и те параметры ,которые в этот код будут переданы.

А код+параметры никогда не будут равны только коду.
Т.е. опять же ситуация $ A(x,x)$ никогда не может быть реализована.
Тут же по умолчанию считается, что как только некоторые параметры будут переданы в алгоритм B, так они сразу "волшебным образом" модифицируют код алгоритма A так, что эти же параметры будут переданы в него, в качестве исходных, когда , на само деле должна произойти цепочка передач параметров, В конце которой никак не может оказаться ситуация $ A(x,x)$.

Еще одно ,последнее возражение:
Ошибка типов: Ведь сказано же что в $ A(x,y)$ $x$ - это код, а $ y$-это его параметры.
Здесь же производится передача ,в качестве первого параметра, код+параметры либо код без параметров, что есть нарушение условия.

PS
Это то , что я сходу смог найти.
Потом выберу один окончательный вариант.

-- Ср янв 26, 2011 16:42:26 --

epros в сообщении #404754 писал(а):

Андрей АK в сообщении #404724 писал(а):

Я никогда не говорил, что множество рациональных чисел (рациональная система счисления) самая лучшая - я говорил, что она самодостаточная.

Что это значит? Факт заключается в том, что нельзя указать рациональное число, в точности равное $\sqrt{2}$. Это и означает, что $\sqrt{2}$ - иррациональное число.

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

[Xaositect]

Андрей АK в сообщении #404827 писал(а):

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

Входные параметры - произвольные строки.
Вы утверждаете, что если есть машина, принимающая две строки, то нельзя сделать машину, принимающую одну строку, копирующую ее и запускающую исходную машину?

[epros]

Андрей АK в сообщении #404827 писал(а):

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

"Иррациональное" = "не рациональное".

Андрей АK в сообщении #404827 писал(а):

Т.е. надо еще доказать несчетность иррациональных чисел.

Несчётность - это второй вопрос. Например, множество конструктивных действительных чисел счётно (с точки зрения классического анализа). Но существование-то иррациональных чисел, надеюсь, Вы не станете отрицать?

[Андрей АK]

Xaositect в сообщении #404836 писал(а):

Андрей АK в сообщении #404827 писал(а):

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

Входные параметры - произвольные строки.
Вы утверждаете, что если есть машина, принимающая две строки, то нельзя сделать машину, принимающую одну строку, копирующую ее и запускающую исходную машину?

Ну вот смотрите: Машина B принимает строку - это должна быть строка: "код алгоритма+параметры к нему".
Либо только "код алгоритма" (без параметров).
Теперь она хочет передать это в машину A ... но у A первый параметр - это исключительно код алгоритма.
А вот второй параметр - это "код алгоритма+параметры к нему".
Передавая в качестве обеих параметров одно и то же вы нарушите требования к типу передаваемого значения.
Вообще это разделение на два пареметра у функции A сделано исключительно для запутывания тех кто будет разбираться.
К тому же сама машина Тьюринга - это еще тот монстр маразма.

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

-- Ср янв 26, 2011 17:37:05 --

epros в сообщении #404855 писал(а):

"Иррациональное" = "не рациональное".

Это - определение через отрицание.
Такое определение некорректно и приводит к парадоксам (как например "множество всех множеств").

[Xaositect]

Андрей АK в сообщении #404863 писал(а):

Теперь она хочет передать это в машину A ... но у A первый параметр - это исключительно код алгоритма.

Нет. Я специально по этому поводу и в формулировке написал уточнение, и в доказательстве явно выписал пункт (а). Вы все-таки не согласны с формулировкой?

(Оффтоп)

Кроме того, это вообще несущественно. Я могу взять модель, где любая строка является программой, но мне не хочется сопутствующие технические детали разгребать

Андрей АK в сообщении #404863 писал(а):

К тому же сама машина Тьюринга - это еще тот монстр маразма.

Какое математическое определение алгоритма Вас устроит?
Собственно, я могу не привязываться даже к конкретному определению, а просто сформулировать, какие свойства модели вычислений используются в доказательстве. В конце концов, теорема верна не только для класса вычислимых функций.

[migmit]

Ну, давайте вместо воображаемой машины Тьюринга возьмём обычный компьютер.

Предположим - только предположим - что есть программа stops, такая, что вызов stops program arg выводит 1, если вызов program arg останавливается, и 0 - если этот вызов уходит в бесконечный цикл; что она будет делать, если программы под названием program не существует - несущественно.

То есть, скажем вызов

stops echo whatever

выведет 1, а

stops yes whatever

выведет 0 (yes - программа, которая свой единственный аргумент бесконечно выводит на экран, никогда не останавливаясь).

Если такая программа есть, то я напишу следующую программу:

$ cat diag.sh
if (($(stops $1 $1) == 1)); then yes > /dev/null; fi

Вызов ./diag.sh program завершится, если вызов stops program program вернёт 0 - то есть, по определению stops, тогда и только тогда, когда вызов program program НЕ завершится.

Теперь попробуйте понять, что вызов

$ ./diag.sh ./diag.sh

не может ни завершиться, ни не завершиться. Противоречие.

Вопрос: какой из этих шагов, по-вашему, не получится сделать? Написать программу diag.sh? Я вам её уже написал. Сделать вызов ./diag.sh ./diag.sh? Вот ровно так и делается.

Так как противоречий в реальном мире быть не может, значит, программа stops с указанным свойством существовать не может.

[Андрей АK]

Xaositect в сообщении #404868 писал(а):

Какое математическое определение алгоритма Вас устроит?
Собственно, я могу не привязываться даже к конкретному определению, а просто сформулировать, какие свойства модели вычислений используются в доказательстве. В конце концов, теорема верна не только для класса вычислимых функций.

Не надо сложных моделей вычисления.
Возьмем префиксные функции:
Пусть строка с параметрами передаются в алгоритм приписыванием этой строки справа к коду алгоритма.
Т.е. $P(X)$ - это просто строка $PX$
($P(X,Y)$ -> $PXY$)
В такой модели нет безусловных переходов и ссылок по номерам.
Так, что сначала попробуйте доказать существование невычислимых функций в такой модели.

Если это не получится, то придется признать, что все дело в неких ссылках - номерах в базе данных или безусловных переходах - только с их использованием можно доказать существование невычислимых функций или проблемы остановки.

Тогда можно будет отдельно их обсудить на предмет - корректно или не корректно их использование в контрпримерах?
Вполне может оказаться что в некоторых случаях - некорректно (и это как раз те самые случаи в которых доказывается невозможность существования анализатора).

[Xaositect]

Андрей АK в сообщении #404885 писал(а):

Xaositect в сообщении #404868 писал(а):

Какое математическое определение алгоритма Вас устроит?
Собственно, я могу не привязываться даже к конкретному определению, а просто сформулировать, какие свойства модели вычислений используются в доказательстве. В конце концов, теорема верна не только для класса вычислимых функций.

Не надо сложных моделей вычисления.
Возьмем префиксные функции:
Пусть строка с параметрами передаются в алгоритм приписыванием этой строки справа к коду алгоритма.
Т.е. $P(X)$ - это просто строка $PX$ ($P(X,Y)$ -> $PXY$)
В такой модели нет безусловных переходов и ссылок по номерам.
Так, что сначала попробуйте доказать существование невычислимых функций в такой модели.

Либо я Вас не понял, либо в такой модели даже возведение в квадрат нельзя написать.
Нельзя ли подробнее?

-- Ср янв 26, 2011 17:15:04 --

Или Вы комбинаторы имеете в виду?

-- Ср янв 26, 2011 17:15:30 --

И как определяется останов у ваших программ?

[Андрей АK]

migmit в сообщении #404875 писал(а):

Теперь попробуйте понять, что вызов

$ ./diag.sh ./diag.sh

не может ни завершиться, ни не завершиться. Противоречие.

Вот пример , с использованием ссылки на программу в некой базе данных (имя файла './diag.sh'- это ссылка).
В код программы занесена эта конкретная ссылка, причем, если программу переименовать (не меняя кода) то ссылка окажется некорректной и все перестанет работать.
Следовательно, для работоспособности программы необходимо, чтоб база данных не меняла больше своей структуры , не переносила файлы на новое место (т.е. их не переименовывала).
Но ведь эта ссылка на алгоритм - это внутренний номер (индекс) базы данных - он должен создаваться базой данных в момент записи в неё кода программы!
Тогда вопрос: Как кто-то мог знать, в какое место будет занесен алгоритм (как пронумерованы алгоритмы в базе), в то время, когда код программы еще не был занесен в базу?
Вы заранее знали, как будет называться ваш алгоритм и в какое место он будет занесен ... но тогда , механизм занесения кода в базу, является частью алгоритма (поскольку в алгоритме это было учтено при его написании), следовательно, ваша программа анализатор анализирует не весь код программы - под анализ не попал алгоритм занесения кодов в базу данных.
Для выполнения всех условий, ваша программа должна также проанализировать и механизм занесения кода в базу (а вдруг операция сохранения на диск окончится ошибкой, имя файла неиспользуемое или ещё что-то)- т.е. в качестве параметра следует передавать весь код "операционной системы" с указанием какой алгоритм будет использоваться для занесения и куда он потребует себя занести, а этого сделано не было, следовательно ваш пример - некорректен.

-- Ср янв 26, 2011 18:36:37 --

Xaositect в сообщении #404888 писал(а):

Либо я Вас не понял, либо в такой модели даже возведение в квадрат нельзя написать.
Нельзя ли подробнее?

-- Ср янв 26, 2011 17:15:04 --

Или Вы комбинаторы имеете в виду?

-- Ср янв 26, 2011 17:15:30 --

И как определяется останов у ваших программ?

Возведение в квадрат входит в часть встроенных алгоритмов, например SQRT2 ('SQRT' - алгоритм возведения в квадрат, '2'-параметр)
Останов - когда окончится строка.
Если надо, можно ввести разделительные знаки, но ,можно подразумевать, что они там есть.

Программу анализатор можно обозначить одной буквой A или P и предположить, что она корректно работает (возможно внутри нее и есть циклы, но нам это не интересно, в данном случае - это черный ящик).
Тогда, чтоб передать в наш анализатор самого себя, придется что-то приписать (самого себя справа от буквы A), получим:
'AAX'
Но мы же передавали 'AX', а получили совсем другое: 'AAX'
Снова передадим в анализатор? Получим:
'AAAX'
И так далее.
Сразу ,наглядно, всплываю все ньюансы передачи функции самой себя.
Это уже получается другая функция!
Как сказали классики:"В одну реку невозможно войти дважды".

[epros]

Андрей АK в сообщении #404863 писал(а):

Это - определение через отрицание.
Такое определение некорректно и приводит к парадоксам (как например "множество всех множеств").

Чем Вам не нравятся определения через отрицание? Отнюдь не обязательно они должны приводить к парадоксам. Конкретно, против чего Вы возражаете? Против того, что $\sqrt{2}$ - "число"? Или против того, что $\sqrt{2}$ не является "рациональным числом"? если Вы принимаете и то, и другое, значит Вы должны признать, что $\sqrt{2}$ является "не рациональным числом".

Андрей АK в сообщении #404863 писал(а):

но у A первый параметр - это исключительно код алгоритма.
А вот второй параметр - это "код алгоритма+параметры к нему".
Передавая в качестве обеих параметров одно и то же вы нарушите требования к типу передаваемого значения.

Вообще-то, как я понял, второй параметр к программе $A$ - это параметр к алгоритму $M_x$ (без его кода).

В чём вообще проблема? Ещё можно как-то сомневаться в том, что алгоритму $M_x$ можно подавать на вход параметр $x$ (код самого алгоритма $M_x$), потому что алфавит, в котором кодируется алгоритм $M_x$, может содержать символы, которых нет в алфавите, со словами которого работает алгоритм $M_x$. Но ведь у программы $A$ нет такого ограничения! Она может работать со словами в объединённом алфавите.

[Андрей АK]

epros в сообщении #404907 писал(а):

В чём вообще проблема? Ещё можно как-то сомневаться в том, что алгоритму $M_x$ можно подавать на вход параметр $x$ (код самого алгоритма $M_x$), потому что алфавит, в котором кодируется алгоритм $M_x$, может содержать символы, которых нет в алфавите, со словами которого работает алгоритм $M_x$. Но ведь у программы $A$ нет такого ограничения! Она может работать со словами в объединённом алфавите.

Еще раз повторяю:
Анализатору $A(x,y)$, для успешной работы надо код программы и параметры к коду программы.
Когда мы в анализатор $A(x,y)$ хотим передать самого себя, то вместо х можно передать просто $A$ - код программы, а вот в качестве у надо передавать 'код+параметры', т.е.:
$A(A,A(x,y))$ - причем мы сверху спускаем условие, что x- это A, а y - ,по прежнему, анализатор в виде кода + параметры, т.е. снова надо подставить вместо x -A, а вместо y:$A(A,A(x,y))$
Получим:
$A(A,A(A,A(x,y)))$
И так далее.
Т.е. мы сформулировали условие, которое невозможно реализовать практически.
(А всякие трюки с переименовыванием - это только уловка чтоб замаскировать софизм)

[Xaositect]

Андрей АK в сообщении #404895 писал(а):

Возведение в квадрат входит в часть встроенных алгоритмов, например SQRT2 ('SQRT' - алгоритм возведения в квадрат, '2'-параметр)
Останов - когда окончится строка.
Если надо, можно ввести разделительные знаки, но ,можно подразумевать, что они там есть.

Программу анализатор можно обозначить одной буквой A или P и предположить, что она корректно работает (возможно внутри нее и есть циклы, но нам это не интересно, в данном случае - это черный ящик).
Тогда, чтоб передать в наш анализатор самого себя, придется что-то приписать (самого себя справа от буквы A), получим:
'AAX'
Но мы же передавали 'AX', а получили совсем другое: 'AAX'
Снова передадим в анализатор? Получим:
'AAAX'
И так далее.
Сразу ,наглядно, всплываю все ньюансы передачи функции самой себя.
Это уже получается другая функция!
Как сказали классики:"В одну реку невозможно войти дважды".

Так, а если я хочу в программу $P$ передать строку $AX$ два раза, надо написать $PAXAX$? а как отличить это от программы, которой передается строки $A$, $X$ и потом в результат еще две строки $A$ $X$?
Я предлагаю скобки ставить, согласны: $P(AX)(AX)$?

Я сейчас формально опишу модель, а Вы скажете, Вы это имели в виду или нет:
Программа представляет собой последовательность символов из некоторого алфавита, содержащего скобки. Некоторым нескобочным символам приписаны функции, переводящие наборы строк в строки, напр. мы можем приписать символу $S$ функцию от одной строки, которая работает так: если аргумент является числом, то она выдает квадрат числа, если нет - то некоторый выделенный символ $*$. Арностью функции назовем количество ее аргументов.
Работа программы происходит следующим образом: Рассматривается первый символ строки. Если ему не приписана никакая функция, то происходит останов машины, и строка считается результатом. Иначе приписанная первому символу функция, имеющая некоторую арность $k$ применяется к записанным после этого $k$ строкам и символ с последующими $k$ строками заменяется на результат. Например, $S2$ преобразуется в $4$, и после этого машина останавливается и результатом будет $4$. Для того, чтобы передать многобуквенную строку, нужно использовать скобки: $S(11)$ -> $121$.

Согласны?