Существует ли биекция между вычислимыми числами и нат.?

[bot]

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

Nxx в сообщении #181488 писал(а):
Думаю, тему пора закрывать.
Решили сбежать?

Nxx в сообщении #181604 писал(а):

Нет, просто получил ответы на свои вопросы.

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

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

[Someone]

Nxx в сообщении #181604 писал(а):

Ну контруктивные(вычислимые) объекты, как я понимаю, примерно соответствуют тому, что мог бы доказать/построить кропотливый математик с бумагой и карандашом.

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

Nxx в сообщении #181604 писал(а):

Это следует из тезиса Чёрча-Тьюринга.

Тезис Чёрча (Тьюринга, Поста, Маркова и т.д.) - это внематематический принцип. В который можно верить, а можно не верить. Интуиционисты не верят. Наши отечественные конструктивисты верят.

Nxx в сообщении #181604 писал(а):

Это же соответствует тому, что мог бы рассчитать компьютер, работающий по принципу машины Тьюринга.

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

Nxx в сообщении #181604 писал(а):

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

Причём тут законы физики?

[epros]

Ух ты! Это за два дня такую тему раскатали?

Профессор Снэйп писал(а):

Nxx писал(а):

Мне также не понятно, с чего вы взяли, что диффуров в конструктином анализе нет.

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

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

Вообще-то я тоже не вполне понял вопрос, на который хочет получить ответ автор темы.

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

[PAV]

Nxx в сообщении #181604 писал(а):

Ну контруктивные(вычислимые) объекты, как я понимаю, примерно соответствуют тому, что мог бы доказать/построить кропотливый математик с бумагой и карандашом.

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

[Nxx]

Цитата:

А что - очень даже эффективный способ написания реферата.

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

[PAV]

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

[Brukvalub]

PAV в сообщении #181658 писал(а):

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

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

[PAV]

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

[nikov]

Nxx писал(а):

- Нерекурсивные - для их получения необходим генератор случайных чисел.

А при чем здесь генератор случайных чисел? Возьмем, например, последовательность Busy Beaver. Она алгоритмически не вычислима. Но любой ее конечный отрезок алгоритмически вычислим. И по мере развития математики люди будут находить алгоритмы, позволяющие вычислить все больше и больше элементов этой последовательности. И найденные значения будут отнюдь не случайными.

Добавлено спустя 1 минуту 40 секунд:

Nxx писал(а):

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

Вы можете привести пример хотя бы одного алгоритма, для которого невозможно определить, остановится он или нет?

Добавлено спустя 2 минуты 24 секунды:

Nxx писал(а):

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

Опять-таки, попрошу пример такого алгоритма.

Добавлено спустя 7 минут 17 секунд:

Nxx писал(а):

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

Теорема о неполноте утверждает существование недоказуемых утверждений в рамках одной фиксированной теории. Любую теорию, в которой выразимо понятие доказуемости (например, аксиоматику Пеано), можно усилить, добавив к ней схему аксиом: $(T \vdash \Phi) \rightarrow \Phi$, что расширит множество алгоритмов, об остановке которых она может судить.

Добавлено спустя 2 минуты 11 секунд:

Nxx писал(а):

Кстати, по-моему, логика "да", "нет" и "недоказуемо" вполне естественна, особенно учитывая наличие теоремы Гёделя. Разве не так? Как можно париписывать истинность или ложность утверждениям, про которые доказано, что их истинность никогда не будет ни доказана, ни опровергнута?

Можете привести пример такого утверждения?

Добавлено спустя 5 минут 33 секунды:

Nxx писал(а):

Значит, что-то не так с аксиоматикой, если она позволяет существование вообще любых множеств, даже тех, которых в природе не бывает.

То есть, я не хочу сказать, что такая аксиоматика неправомерна, просто она имеет нулевую практическую ценность

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

[Nxx]

Цитата:

Но любой ее конечный отрезок алгоритмически вычислим.

Нет.

Цитата:

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

Развитие математики тут никак не поможет.

Цитата:

Вы можете привести пример хотя бы одного алгоритма, для которого невозможно определить, остановится он или нет?

Алгоритм, завязанный на какую-нибудь неразрешимую проблему в математике. Например, подбор решений диофантового уравнения.

Цитата:

Теорема о неполноте утверждает существование недоказуемых утверждений в рамках одной фиксированной теории. Любую теорию, в которой выразимо понятие доказуемости (например, аксиоматику Пеано), можно усилить, добавив к ней схему аксиом: $(T \vdash \Phi) \rightarrow \Phi$, что расширит множество алгоритмов, об остановке которых она может судить.

В таком случае, мы не узнаем, является ли новая система аксиом непротиворечивой.

Цитата:

Можете привести пример такого утверждения?

Вот тут целый список:
http://en.wikipedia.org/wiki/List_of_un ... e_problems

[маткиб]

Ох уж эти конструктивисты...

[epros]

маткиб писал(а):

Ох уж эти конструктивисты...

Nxx пока не признался, что он констуктивист

[nikov]

Nxx писал(а):

Цитата:

Но любой ее конечный отрезок алгоритмически вычислим.

Нет.

Объясните, почему нет. Для любой конечной последовательности чисел существует алгоритм, печатающий ее и останавливащийся.

Nxx писал(а):

Цитата:

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

Развитие математики тут никак не поможет.

Почему?

Nxx писал(а):

Цитата:

Вы можете привести пример хотя бы одного алгоритма, для которого невозможно определить, остановится он или нет?

Алгоритм, завязанный на какую-нибудь неразрешимую проблему в математике. Например, подбор решений диофантового уравнения.

Что значит "завязанный на"? Приведите конкретный пример алгоритма, для которого невозможно определить, остановится он или нет.

Nxx писал(а):

Цитата:

Теорема о неполноте утверждает существование недоказуемых утверждений в рамках одной фиксированной теории. Любую теорию, в которой выразимо понятие доказуемости (например, аксиоматику Пеано), можно усилить, добавив к ней схему аксиом: $(T \vdash \Phi) \rightarrow \Phi$, что расширит множество алгоритмов, об остановке которых она может судить.

В таком случае, мы не узнаем, является ли новая система аксиом непротиворечивой.

Если мы считаем аксиоматику Пеано содержательно истинной, то очевидно, что добавление схемы аксиом "каждое утверждение, доказуемое в аксиоматике Пеано - истинно" даст по прежнему содержательно истинную, а значит, непротиворечивую теорию.
Или Вам нужно еще какое-то свидетельство непротиворечивости?

Nxx писал(а):

Цитата:

Можете привести пример такого утверждения?

Вот тут целый список:
http://en.wikipedia.org/wiki/List_of_un ... e_problems

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

[Nxx]

Цитата:

Объясните, почему нет. Для любой конечной последовательности чисел существует алгоритм, печатающий ее и останавливащийся.

Нет.

Цитата:

Почему?

Потому что невычислимо вычислить нельзя.

Цитата:

Приведите конкретный пример алгоритма, для которого невозможно определить, остановится он или нет.

Уже привел. Берется диофантово уравнение и перебираются коэффициенты-натуральные числа. Если они являются решением уравнения, алгоритм останавливается.

[nikov]

Nxx писал(а):

Цитата:

Объясните, почему нет. Для любой конечной последовательности чисел существует алгоритм, печатающий ее и останавливащийся.

Нет.

Цитата:

Почему?

Потому что невычислимо вычислить нельзя.

Давайте по-другому. Существует ли алгоритм, печатающий 3 первых члена этой последовательности и останавливающийся? А 4 первых члена?

Nxx писал(а):

Цитата:

Приведите конкретный пример алгоритма, для которого невозможно определить, остановится он или нет.

Уже привел. Берется диофантово уравнение и перебираются коэффициенты-натуральные числа. Если они являются решением уравнения, алгоритм останавливается.

Какое именно диофантово уравнение?

Неудобный аргумент с добавлением аксиом предпочитаете игнорировать?