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

[Maslov]

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

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

Вам уже приводили:

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

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

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

Так все-таки, бесконечным рядом, или бесконечным рядом, заданным конечным алгоритмом?
Если второе, то http://en.wikipedia.org/wiki/Chaitin's_constant

Вот здесь можно лекцию самого Чейтина почитать: Randomness in Arithmetic and The Decline and Fall of Reductionism in Pure Mathematics

[hurtsy]

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

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

Имхо, Ваше множество конечных алгоритмов не больше множества алгебраических чисел(тоже счетное). Вы можете конечным алгоритмом найти число $\pi$? С уважением,

[Xaositect]

hurtsy в сообщении #404615 писал(а):

Имхо, Ваше множество конечных алгоритмов не больше множества алгебраических чисел(тоже счетное). Вы можете конечным алгоритмом найти число $\pi$? С уважением,

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

[Андрей АK]

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

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

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

Так все-таки, бесконечным рядом, или бесконечным рядом, заданным конечным алгоритмом?
Если второе, то http://en.wikipedia.org/wiki/Chaitin's_constant

Константа Хайтина приводится как пример невычислимого числа по ошибке.
И вот по чему:
Её невычислимость, основывается на утверждении, что алгоритм, решающий проблему остановки невычислим, поскольку проблема остановки неразрешима.
Однако в утверждении о неразрешимости проблемы остановки заложена ошибка.
Её невычислимость "доказывается" контрпримером, когда в некий алгоритм, позволяющий определить остановиться ли произвольный алгоритм, в качестве параметра передаётся он сам.
Эти рассуждения только кажутся логичными, однако ошибочны, поскольку невозможно никаким способом передать алгоритму , в качестве параметра, самого себя.
Ошибка в том, что тут делается попытка отделить сам алгоритм от передаваемого в него параметра и рассматривать их как независимые сущности, а между тем алгоритм P(x) - это одно, а P(P(x)) - это уже совершенно другая функция.
Если записать это в префиксном виде, то мы будем только приписывать слева все новые и новые буквы P, получая каждый раз новую функцию:
PX, PPX, PPPX, PPPPX и т.д.
(Вообще было бы удивительно, если бы мы могли передать какому то алгоритму самого себя в качестве параметра - это нарушило бы принцип причинности, наиболее фундаментальный ,на мой взгляд, методологический принцип).
Таким образом, проблемы остановки не существует.
И ,следовательно, константа Хайтина не является невычислимой константой.

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

[migmit]

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

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

Да что вы говорите.
Ну, вот вам:

MigMit:~ MigMit$ cat alg.sh
wc -c alg.sh

Алгоритм в одну строчку, который подсчитывает число байт в нём самом.
Работает:

MigMit:~ MigMit$ ./alg.sh
      13 alg.sh

13 байт.

[Dandan]

Пора в пургаторий. Андрей АK, вы либо учите математику как следует - чётко разбираясь в формулировках, утверждениях и другом материале, решая все упражнения и задачки, либо оставьте её совсем.

[Xaositect]

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

Её невычислимость "доказывается" контрпримером, когда в некий алгоритм, позволяющий определить остановиться ли произвольный алгоритм, в качестве параметра передаётся он сам.
Эти рассуждения только кажутся логичными, однако ошибочны, поскольку невозможно никаким способом передать алгоритму , в качестве параметра, самого себя.
Ошибка в том, что тут делается попытка отделить сам алгоритм от передаваемого в него параметра и рассматривать их как независимые сущности, а между тем алгоритм P(x) - это одно, а P(P(x)) - это уже совершенно другая функция.
Если записать это в префиксном виде, то мы будем только приписывать слева все новые и новые буквы P, получая каждый раз новую функцию:
PX, PPX, PPPX, PPPPX и т.д.
(Вообще было бы удивительно, если бы мы могли передать какому то алгоритму самого себя в качестве параметра - это нарушило бы принцип причинности, наиболее фундаментальный ,на мой взгляд, методологический принцип).

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

[epros]

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

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

Попробуйте указать на точку $\sqrt{2}$.

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

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

-- Ср янв 26, 2011 10:33:37 --

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

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

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

Вот пример: "Практическая" задача состоит в том, чтобы найти четвёртую степень от числа $\sqrt{2}$. Если мы возьмём вместо этого числа какое-нибудь приближение, то и ответ получится приближённым: $1.4^4 = 3.8416$. Но мы знаем точный ответ: $\sqrt{2}^4 = 4$.

[Андрей АK]

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

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

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

Да что вы говорите.
Ну, вот вам:

MigMit:~ MigMit$ cat alg.sh
wc -c alg.sh

Алгоритм в одну строчку, который подсчитывает число байт в нём самом.
Работает:

MigMit:~ MigMit$ ./alg.sh
      13 alg.sh

13 байт.

Это иллюзия.
Этот алгоритм подсчитывает количество байт вовсе не у себя, а у файла.
Чтоб алгоритм ,на самом деле, что-то делал с самим собой, попробуйте написать код, который подсчитывает время выполнения алгоритма, когда он подсчитывает время выполнения алгоритма, когда он подсчитывает время выполнения алгоритма ... самого себя.
(Вместо двоеточия стоит бесконечное число скобок передачи параметра, поскольку только в этом случае можно утверждать, что от присоединения лишнего префикса (очередной подстановки) код алгоритма не меняется (бесконечность+1=бесконечность) и он действительно исследует самого себя)

[migmit]

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

Этот алгоритм подсчитывает количество байт вовсе не у себя, а у файла.

Хотите получить алгоритм на стандартный вход? Пожалуйста:

$ cat alg.sh
wc -c
$ ./alg.sh < alg.sh
6

[Андрей АK]

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

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

Вы забываете про передаваемые параметры.
Чтоб некий алгоритм смог установить - остановится ли некий алгоритм или нет, ему ,кроме кода алгоритма, необходимо проанализировать и передаваемый параметр.
Без параметра - данных для анализа недостаточно.
Т.е. алгоритму надо передавать код себя самого и входной параметр для себя самого.
Так вот коды будут совпадать, а вот параметры - различаться.
И никогда не сделать так, чтоб алгоритм смог проанализировать собственный код, с идентичным входным параметром (идентичным для себя и для того алгоритма, что он анализирует).
Если параметры отличаются - то и проблемы остановки не существует.

-- Ср янв 26, 2011 12:50:43 --

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

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

Этот алгоритм подсчитывает количество байт вовсе не у себя, а у файла.

Хотите получить алгоритм на стандартный вход? Пожалуйста:

$ cat alg.sh
wc -c
$ ./alg.sh < alg.sh
6

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

-- Ср янв 26, 2011 13:02:08 --

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

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

Вот пример: "Практическая" задача состоит в том, чтобы найти четвёртую степень от числа $\sqrt{2}$. Если мы возьмём вместо этого числа какое-нибудь приближение, то и ответ получится приближённым: $1.4^4 = 3.8416$. Но мы знаем точный ответ: $\sqrt{2}^4 = 4$.

Да, можно используя другую систему счисления (алгебраическую) получить более точный результат (что вы продемонстрировали).
Я никогда не говорил, что множество рациональных чисел (рациональная система счисления) самая лучшая - я говорил, что она самодостаточная.
Т.е. используя ряды рациональных чисел, вы точно так же получите точный результат (ну разве что может быть 3.(9) , а не 4 - но ведь это одно и то же?).

[migmit]

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

Не вижу никакой модификации - вы считываете с диска все тот же файл.

Могу набрать его руками, мне не трудно.

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

Но такой каталог вы не сможете сделать корректным способом (т.е. в один прием).

Почему я должен что-то делать "в один приём", как вы выражаетесь? И как это ваше странное ограничение вообще чётко формулируется?

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

но вот тут и возникает проблема: файла то еще не существует (вы еще не успели его записать на диск)

Почему не существует? Он уже был, только имел другое содержимое.

[Xaositect]

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

Если параметры отличаются - то и проблемы остановки не существует.

Давайте мы сформулируем точно, о чем говорим.
Формулировка теоремы о halting problem, которая нравится мне, звучит так:
Не существует машины Тьюринга (МТ), которая, получив на вход две строки, $x$ и $y$, выдает на выход 1 тогда и только тогда, когда строка $x$ представляет собой программу некоторой МТ, и эта МТ останавливается, если ей на вход подать строку $y$.
Вы считаете это утверждение неверным?

[Андрей АK]

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

Почему не существует? Он уже был, только имел другое содержимое.

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

-- Ср янв 26, 2011 13:06:39 --

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

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

Если параметры отличаются - то и проблемы остановки не существует.

Давайте мы сформулируем точно, о чем говорим.
Формулировка теоремы о halting problem, которая нравится мне, звучит так:
Не существует машины Тьюринга (МТ), которая, получив на вход две строки, $x$ и $y$, выдает на выход 1 тогда и только тогда, когда строка $x$ представляет собой программу некоторой МТ, и эта МТ останавливается, если ей на вход подать строку $y$.
Вы считаете это утверждение неверным?

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

[Xaositect]

Андрей А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)$ останавливается.
Противоречие.