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

[Андрей АK]

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

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

$<A(b,b)>$ - фактически запускает B на выполнение (анализирует, т.е. выполняет самостоятельно своим собственным отладчиком).

Это кто такое сказал?
$A$ может действовать любым способом, каким захочется.

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

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

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

Круг замкнулся - имеем рекурсивный зацикленный алгоритм.

Алгоритма не вижу.

Алгоритм был предъявлен post404743.html#p404743
Я только показал, что он зацикленный.

[migmit]

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

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

Давайте тогда и будем называть так, чтобы не вводить друг друга в заблуждение, ладно?
Далее, вы пишете:

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

$<B(b)> = <A(b,b)>$

Это неверно. Программа $A$ была определена так:

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

а) $x$ - не программа => $A(x, y) = 0$
б) $M_x(y)$ останавливается => $A(x, y) = 1$
в) $M_x(y)$ не останавливается => $A(x, y) = 0$

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

Алгоритм был предъявлен post404743.html#p404743

Простите, алгоритм ЧЕГО? В том постинге Xaositect ПРЕДПОЛОЖИЛ, что программа $A$ реализована - как именно, он не уточнял.

[epros]

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

Обозначим операцию запуска программы на выполнение косыми скобками...
...
...где квадратными скобками обозначен все тот же запуск на выполнение но уже другой средой

Ничё не понял. Программа $A(x,y)$ анализирует код $x$ совместно с параметром $y$. Какие проблемы? Кто кого должен "запускать на выполнение"?

[arseniiv]

Я думаю, лучше для понятности Андрею АК переобозначить кое-что, а именно:
$(a, b_1, \ldots, b_n)$ — результат запуска алгоритма, задаваемого строкой-кодом $a$, с параметрами $b_1, \ldots, b_n$, если он останавливается; иначе $(a, b_1, \ldots, b_n)$ не определено.

Тогда первое доказательство Xaositectа перепишется в виде:

Изменённая цитата писал(а):

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

2. Построим на основе $a$ $b$ — код алгоритма, который принимает один параметр-строку, и работает следующим образом:
Если $(a, x, x) = 0$, то $(b, x)$ определено.
Если $(a, x, x) = 1$, то $(b, x)$ не определено.

3. Рассмотрим значение $(b, b)$.
Определённость $(b, b)$ зависит от значения $(a, b, b)$. Рассмотрим каждый из трех случаев:
а) случай (а) реализоваться не может, т.к. $b$ является кодом алгоритма.
б) пусть $(b, b)$ определено. Тогда $(a, b, b) = 0$ и $(b, b)$ не определено. Получаем $(b, b)$ определено $\Rightarrow$ $(b, b)$ не определено.
в) пусть $(b, b)$ не определено. Тогда $(a, b, b) = 0$ и $(b, b)$ определено. Получаем $(b, b)$ не определено $\Rightarrow$ $(b, b)$ определено.

В итоге получаем:
$(b, b)$ не определено $\Leftrightarrow$ $(b, b)$ определено.
Противоречие.

[Андрей АK]

Ладно, чувствую, что увязаю в деталях.
Лучше я объединю все возникшие вопросы в один
Вот более "глобальный" подход к вопросу.
Почему доказательство существования невычислимых функций в post404743.html#p404743 ,и заодно все остальные, некорректны?

То что нельзя доказать корректность произвольной математики её собственными методами, было доказано в теореме Геделя.

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

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

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

Для начала следующий тезис (или Лемма?):
В корректной математике алгоритм не может иметь ссылку на самого себя.
Можно разобрать это подробней:
Действительно, если разбить создание алгоритма на два этапа:
1) Написание ,собственно, кода алгоритма
2) Занесение этого кода в некую базу данных алгоритмов.

Естественно, что пункт 2) не может предшествовать пункту 1) (Поскольку нельзя занести то чего нет).
Отсюда еще одно подтверждения тезиса о невозможности алгоритма ссылаться на самого себя.
(Иначе будет нарушен принцип причинности)

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

И следствие:
Запись $X(X)$ - некорректна, поскольку здесь записан алгоритм, имеющий ссылку на предшествующий алгоритм, что невозможно.


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

Не вопрос же: "А как же многочисленные примеры из жизни и практики программирования, когда две программы ссылаются одна на другую или рекурсивные функции, которые могут вызвать сами себя?".
Отвечу: Некорректные математики существуют.

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

[arseniiv]

Нет, лучше вместо писания вилами по воде ответьте, что в моей редакции доказательства не так.

-- Чт янв 27, 2011 22:49:07 --

(Оффтоп)

Запись ясно показывает, что никакой самоссылки в $(x, x)$ (или $(x, y, y)$) нет, потому что можно рассматривать это как вызов интерпретатора для интерпретации текста $x$ с использованием внутри в качестве аргументов $x$ (или $y, y$).

В редакции Xaositectа под таким «интерпретатором» можно понимать отображение $x \mapsto M_x$, переводящее правильные (по отношению к какому-то заранее заданному языку) описанния машин Тьюринга в собственно машины Тьюринга, так что явно ли неявно он присутствует.

Вы не согласны?

[Xaositect]

Надо сказать, что некоторые мысли Андрей АK формализовать можно. И получаются при этом системы хоть и достаточно слабые, но достаточно сильные, тот же simply typed lambda calculus.
К сожалению, пока он не остановится и не начнет, во-первых, выражать мысли на точном математическом языке (при желании мы найдем некоторый минимум, на котором можно говорить), а во-вторых, перенести свои попытки опровергнуть применимость используемых теорий на основе своих не до конца оформившихся мыслей в русло более конструктивное - по вопросу о halting problem это выяснение того, что все-таки можно делать в алгоритмах.
В таком виде, в каком тема сейчас находится, она все ближе и ближе к Пургаторию, на мой взгляд.

[arseniiv]

(Оффтоп)

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

[venco]

(Оффтоп)

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

Обозначим операцию запуска программы на выполнение косыми скобками:
Т.е. выполнить $X(Y)$ будет обозначено как: $<X(Y)>$

Кстати в C/C++ оператор вызова функции - сами скобки. То, что слева от скобок - указатель на функцию, а в скобках - аргументы, которых может и не быть.

-- Чт янв 27, 2011 12:10:11 --

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

Запись $X(X)$ - некорректна, поскольку здесь записан алгоритм, имеющий ссылку на предшествующий алгоритм, что невозможно.

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

[arseniiv]

(Оффтоп)

venco в сообщении #405457 писал(а):

По-моему, вот он, корень преткновения.

Я тоже так подумал, и потому переобозначил ту штуку.

[Андрей АK]

arseniiv в сообщении #405442 писал(а):

Нет, лучше вместо писания вилами по воде ответьте, что в моей редакции доказательства не так.

-- Чт янв 27, 2011 22:49:07 --

(Оффтоп)

Запись ясно показывает, что никакой самоссылки в $(x, x)$ (или $(x, y, y)$) нет, потому что можно рассматривать это как вызов интерпретатора для интерпретации текста $x$ с использованием внутри в качестве аргументов $x$ (или $y, y$).

В редакции Xaositectа под таким «интерпретатором» можно понимать отображение $x \mapsto M_x$, переводящее правильные (по отношению к какому-то заранее заданному языку) описанния машин Тьюринга в собственно машины Тьюринга, так что явно ли неявно он присутствует.

Вы не согласны?

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

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

[arseniiv]

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

Я сначала приведу пример с обычной базой данных.

Давайте или вы говорите по доказательству, не прибегая к ненужным аналогиям, или я запоминаю, что вы не понимаете, что такое алгоритм.
Выполняется строка-код алгоритма со строками-параметрами, которых может быть произвольное количество. Где вы тут увидели ссылки?!

[venco]

Похоже, ТС не читатель.
Тем не менее я ему благодарен, т.к. до конца понял существование константы Хайтина.
Будет ещё лучше, если кто-нибудь приведёт связь с теоремой Гёделя, если не сложно.

[Андрей АK]

arseniiv в сообщении #405529 писал(а):

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

Я сначала приведу пример с обычной базой данных.

Давайте или вы говорите по доказательству, не прибегая к ненужным аналогиям, или я запоминаю, что вы не понимаете, что такое алгоритм.
Выполняется строка-код алгоритма со строками-параметрами, которых может быть произвольное количество. Где вы тут увидели ссылки?!

1) В алгоритме $b$ есть ссылки (используется) на алгоритм $a$

Цитата:

2. Построим на основе $a$ $b$ — код алгоритма, который принимает один параметр-строку, и работает следующим образом:
Если $(a, x, x) = 0$, то $(b, x)$ определено.
Если $(a, x, x) = 1$, то $(b, x)$ не определено.

Значит, алгоритм $b$ создавался позднее $a$ (мы помним что ссылаться можно только на уже созданные алгоритмы)
2) А вот здесь:
$(a, b, b)$
Алгоритму $a$ передается в качестве параметра алгоритм $b$ и следовательно $a$ создавался позднее $b$
Что противоречит предыдущему выводу.
Найденное противоречие доказывает противоречивость вашей математики.

[Xaositect]

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

arseniiv в сообщении #405529 писал(а):

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

Я сначала приведу пример с обычной базой данных.

Давайте или вы говорите по доказательству, не прибегая к ненужным аналогиям, или я запоминаю, что вы не понимаете, что такое алгоритм.
Выполняется строка-код алгоритма со строками-параметрами, которых может быть произвольное количество. Где вы тут увидели ссылки?!

1) В алгоритме $b$ есть ссылки (используется) на алгоритм $a$

Цитата:

2. Построим на основе $a$ $b$ — код алгоритма, который принимает один параметр-строку, и работает следующим образом:
Если $(a, x, x) = 0$, то $(b, x)$ определено.
Если $(a, x, x) = 1$, то $(b, x)$ не определено.

Значит, алгоритм $b$ создавался позднее $a$ (мы помним что ссылаться можно только на уже созданные алгоритмы)
2) А вот здесь:
$(a, b, b)$
Алгоритму $a$ передается в качестве параметра алгоритм $b$ и следовательно $a$ создавался позднее $b$
Что противоречит предыдущему выводу.
Найденное противоречие доказывает противоречивость вашей математики.

Это уж какой-то совсем странный вывод. Вот есть у нас алгоритм $a$, пусть он раньше. На его основе создали $b$, то есть $b$ позднее, и теперь у нас уже есть и $a$, и $b$. И после этого мы подаем текст программы $b$, который у нас есть, на вход программе $a$, которая у нас тоже есть.

(Оффтоп)

Это все если опустить тот факт, что это вообще никакого значения не имеет.