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

[venco]

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

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

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

[arseniiv]

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

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

Как уже писал Xaositect после первой редакции первого способа доказательства, ничего подобного. Строка-код $a$ с некоторыми маленькими изменениями сшивается один или несколько раз с какими-то строками, давая в результате строку-код $b$.

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

А вот здесь:
$(a, b, b)$
Алгоритму $a$ передается в качестве параметра алгоритм $b$ и следовательно $a$ создавался позднее $b$

Ничего подобного 2. Какому-то интерпретатору, заранее нами заданному, даётся на вход код $a$ и два параметра $b$ и $b$, которые интерпретатор использует там, где в коде $a$ стоит какая-нибудь инструкция, запрашивающая параметры. Заметьте: ни в какие алгоритмы никакие алгоритмы не передаются, а строки.

Есть ещё одна важная вещь: коль мы уж имеем дело с математикой, надо выкинуть время, потому что в какое время мы что определили — не важно. Мы определили. И всё тут, теперь это существует в каком-то лексическом контексте, пока кому-нибудь нужно.

(2 venco)

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

(на самом деле аналогия с языком C не полная, т.к. у него есть куча ограничений, мешающих строгости доказательства, поэтому математики используют машину Тьюринга)

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

[venco]

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

до конца понял существование константы Хайтина.

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

[Xaositect]

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

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

Ну, я сейчас наверно скажу то, что Вы уже знаете, а если не знаете, то догадываетесь :)

Есть такая область, как теория вычислимости, или теория рекурсии. Изучает она вычислимые и невычислимые функции, там есть иерархии и полурешетки, но мы не об этом.

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

А теперь можно вспомнить, что у нас всего функций континуум, как и действительных чисел. Каждое действительное число можно воспринимать как функцию $n\mapsto a_0.a_1\dots a_n$. Или как дедекиндово сечение (рассматриваются только общерекурсивные функции и разрешимые множества рациональных чисел). Соответственно, можно считать, что теория рекурсии имеет дело не с функциями, а с действительными числами - вычислимыми и невычислимыми. Тот же диагональный метод даст нам как раз константу Чейтина как невычислимое число. Она же является аналогом нерекурсивного перечислимого множества: нижняя часть ее сечения Дедекинда перечислима.

Теперь к теореме Геделя и логическим теориям. Рассмотрим ту же halting problem. Утверждение о том, что некоторая машина останавливается или не останавливается, можно рассматривать как утверждение некоторой формальной теории. Тогда теорема о halting problem становится аналогом теоремы Геделя: не существует эффективно аксиоматизируемой теории, в которой доказуемы все верные утверждения вида "машина $M$ (не) останавливается на строке $x$". Теория - это, по сути, перечислимое множество, а теорема говорит о том, что множество $\{(M,x,1)|M(x)\mathop{\downarrow}\}\cup\{(M,x,0)|M(x)\mathop{\uparrow}\}$(стрелочки - это сходится-расходится, останавливается-зацикливается). Теорема Геделя утверждает то же самое относительно множества всех истинных утверждений арифметики, и один из возможных способов доказательства - как раз кодирование алгоритмов.

Другое дело, что множество истин арифметики неразрешимо "значительно сильнее", чем halting problem: если мы добавим оракул для решения HP, мы все равно не сможем получить всю арифметику. Для этого необходимо сделать счетную цепочку оракулов, отвечающих на вопросы об останове машин с оракулами ниже рангом.

У меня тоже есть один вопрос в тему, вдруг кто-нибудь знает. Что происходит с конструктивным анализом, если разрешить использовать оракул, говорящий, равны два числа или нет, или добавить аксиому $\forall x y (x = y \vee \neg x = y)$ (и одно ли это и то же)? Понятно, что появляются разрывные функции и вроде бы теорема о промежуточном значении. Насколько все хорошо становится?

[Андрей АK]

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

Ничего подобного 2. Какому-то интерпретатору, заранее нами заданному, даётся на вход код $a$ и два параметра $b$ и $b$, которые интерпретатор использует там, где в коде $a$ стоит какая-нибудь инструкция, запрашивающая параметры. Заметьте: ни в какие алгоритмы никакие алгоритмы не передаются, а строки.

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

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

Есть ещё одна важная вещь: коль мы уж имеем дело с математикой, надо выкинуть время, потому что в какое время мы что определили — не важно. Мы определили. И всё тут, теперь это существует в каком-то лексическом контексте, пока кому-нибудь нужно.

Чтоб любая теория не была непротиворечива, необходимо, чтоб в ней не было циклических ссылок.
(Например, чтоб не было определений типа: "Лес - это там где много деревьев. Деревья - это то что растет в лесу")
Но как можно убедиться, что в теории нет никаких самоопределений?
Только используя время и четко фиксируя в какой момент было создано то или иное определение и контроль, чтоб более раннее определение (или алгоритм) не использовало никаким образом ,ни прямо ни косвенно, более поздние определения (или алгоритмы).

[Xaositect]

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

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

Существование интерпретатора доказывается.
Самое простое доказательство - приводится текст программы-интерпретатора.
Я не понимаю, вы утверждаете, что интерпретаторы вычисляют невычислимые функции?

[venco]

Андрей АK, Вы на мои сообщения не отвечаете потому что я непонятно пишу, или потому что мои аргументы настолько непоколебимы, что и возразить нечего?

[Андрей АK]

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

Андрей АK, Вы на мои сообщения не отвечаете потому что я непонятно пишу, или потому что мои аргументы настолько непоколебимы, что и возразить нечего?

Я просто не успеваю на все отвечать.
Мне показалось, что ваше сообщение перекликается с тем, на которое я ответил и я постарался в ответе на него учесть и ваши замечания.
Или я чего-то в вашем вопросе не понял.

-- Чт янв 27, 2011 23:58:23 --

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

Существование интерпретатора доказывается.
Самое простое доказательство - приводится текст программы-интерпретатора.
Я не понимаю, вы утверждаете, что интерпретаторы вычисляют невычислимые функции?

Да нет, если приводится текст интерпретатора, то все нормально.
Я имел ввиду, что если интерпретатор обеспечивает синтаксис языка, то ссылаться на него - это выходить за рамки.
Как например заменив синтаксис с $X(Y)$ на $(X,Y)$ мы как бы избавились от необходимости учитывать то, что алгоритму $X$ передается алгоритм $Y$, который может располагаться позже в иерархии.
Но ведь не должно такого быть чтоб от изменения синтаксиса изменялся какой-то смысл.

[Xaositect]

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

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

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

[Андрей АK]

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

Если бы мы, в качестве методологического принципа потребовали соблдать принцип причинности, то
во первых, исчезло бы большинство парадоксов (как то "парадокс лжеца", "парадокс брадобрея", "о множестве всех множеств" и т.д.
и ,во вторых, невозможно было бы так же доказать и саму теорему Геделя.

Т.е. любая математика, соблюдающая "принцип причинности", была бы заведомо корректной.

-- Пт янв 28, 2011 00:15:02 --

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

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

Я уже отвечал (наперед) на такой вопрос: Некорректные математики существуют.
Все эти компиляторы и интерпретаторы недостаточно корректны.
Поэтому программы и зависают.
Если бы не это, то ни одна программа не смогла бы зависнуть.

[arseniiv]

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

у алгоритмов есть иерархия, а при таком обращении она теряется

Нету никакой иерархии.

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

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

Можно убедиться в отсутствии циклических ссылок без введения времени. Для этого необходимо убедиться в отсутствии ссылок вообще. У нас есть строка $a$. Берём заранее заданную (не зависящую от $a$) функцию $B$ и строим строку $b = B(a)$. Ссылок нет никаких. В строке $b$ не используется исполнение («вызов») алгоритма $a$, поскольку в моей модели есть только одна сущность, «выполняющая» алгоритм — интерпретатор. Если его убрать, вы не сможете выполнять алгоритм (выполнять = сопоставлять коду и параметрам результат или не сопоставлять ничего, если зациклилось).
Так как обе буквы $a$ и $b$ у нас обозначают две конкретные строки, о которых мы знаем, что они являются и кодами двух алгоритмов, мы можем составлять конструкции вида $(a, \mathrm{params})$ и $(b, \mathrm{params})$ и ждать от них определённости, и потому равенства какому-то значению, или неопределённости. Что происходит со строками $a$, $b$ и $\mathrm{params}$ внутри интерпретатора, не вовлекает никаких ссылок на что-то.

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

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

Я ввёл этот синтаксис, чтобы показать, что алгоритм жёстко с аргументами не связан, потому что можно все алгоритмы перевести в строки и выполнять интерпретатором, при этом интерпретатору не важно, какие параметры подставлять в алгоритм — он всё подставит, а алгоритм сам не подставит. Алгоритм сам себя не выполняет!
Алгоритму $X$ не передаётся алгоритм $Y$. В алгоритм с кодом $X$ подставляется параметр-строка $Y$. Да, в доказательстве все параметры — коды, но это не мешает им быть просто строками. Они не выполняются как алгоритмы. $X$ анализирует $Y$, манипулируя символами этой строки.

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

Т.е. любая математика, соблюдающая "принцип причинности", была бы заведомо корректной.

Сформулируйте его формально, что ли. И посмотрим. А так — бабушка надвое сказала.

-- Пт янв 28, 2011 02:22:16 --

(Оффтоп)

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

Так как обе буквы $a$ и $b$ у нас обозначают две конкретные строки

Ох, venco же об этом в начале страницы говорил!

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

Сформулируйте его формально

Как звучит!

[Xaositect]

Цитата:

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

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

-- Чт янв 27, 2011 23:29:10 --

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

Если бы не это, то ни одна программа не смогла бы зависнуть.

while(true){printf("1");}

-- Чт янв 27, 2011 23:33:08 --

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

[Toucan]

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

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

Андрей АK, считайте эту просьбу Xaositect'а требованием модераторов дискуссионного раздела.

[Андрей АK]

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

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

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

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

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

Принцип причинности: ни одно следствие не может быть собственной причиной.
Как то:
Ни одно определение не может использовать термины, в определении которых оно участвовало (прямо или косвенно).

[Xaositect]

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

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

Поговорить о математике мы, конечно, можем.
Но дело-то ведь в том, что Вы пытаетесь своими полуфилософскими рассуждениями опровергнуть доказанные теоремы. Философские рассуждения и аналогии могут помочь при исследовании математических объектов, но если от них мы не переходим к строгим доказательствам, то это не предмет математической дискуссии.
Дело в том, что теоремы Тьюринга и Геделя идейно достаточно просты, но технически требуют местами занудного формализма. Если Вы хотите разобраться, чем они существенно отличаются от парадоксов лжеца или Рассела, придется в эту технику вникнуть.

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

Не знаю, корректна ли арифметика Пеано - с этой стороны я её не исследовал.
Но на первый взгляд там никаких циклических ссылок нет.

Для справки - теорема Геделя формализуется внутри арифметики Пеано.