Стандартная модель арифметики и все, все, все

[Xaositect]

В связи со всем этим хочется рассказать байку, которую нам рассказывал на семинаре мой научный руководитель В.Б.Алексеев.
В его диссертации у него была в ней "четырехэтажная" оценка для количества базисов особого вида. Такое бывает в некоторых дискретных задачах, там только $k$-значных функций от $n$ переменных $k^{k^n}$. И при $n=3$ у него выходила нижняя оценка порядка $2^{4000}$ или около того. И вот А.А.Марков тогда сказал такую фразу: "Таких чисел не бывает", что очень перепугало доклачика

У нас в кибернетике есть теоремы, которые говорят, что почти все булевы функции от $n$ элементов сложные (требуют $\frac{2^n}{n}(1-o(1))$ логических элементов для реализации). На практике таких функций "не бывает", вы никогда не увидите схемы такой сложности в процессорах и т.п.

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

[vek88]

Ales в сообщении #279946 писал(а):

vek88 в сообщении #279939 писал(а):

Ваше решение не является устным! За эту задачу Вам двойка. Вы же не Вольф Мессинг, чтобы проделать эти вычисления устно.

Извините, Вы должны были проинформировать чему равен предел $(1+ \frac 1 n)^n$ и сообщить первые цифры основания натурального логарифма.

В конституции батьки Махно было всего два пункта:

1. Никто никому ничего не обязан.

2. Выполнение пункта 1 не обязательно.

Я следовал пункту 1 - поэтому не должен был информировать Вас о 2-м (кажется) замечательном пределе. Да и к тому же это ведь основы - зачем они Вам?

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

А оставаясь на уровне первых членов ряда Тейлора Вы мало чего из реальных вычислительных задач сможете решить.

И вообще, если кто-то говорит, что знает все ответы, значит он просто не знает всех вопросов.

Чтобы разрядить обстановку, поясню откуда взялась задача про сопротивление заземления. Осенью у меня в доме стало вышибать автомат, на котором сидят кухонные розетки. Посмотрел на счетчик - вертится как угорелый - 4 киловатта. Все выключил - все равно 4 квт. Отсоединяю электрическую духовку от сети. Все то же. Щупаю стены на предмет нагревания - ничего нет. Слушаю не искрит ли где - тишина. Пришлось вытаскивать розетки из стены и отключать их. Пришлось отрубить все розетки. Все равно 4 квт.

Стал тестером мерять напряжение на щитке - оказалось на земле (не на нейтрали, а на земле) 220 вольт.

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

Стало понятно куда уходили 4 квт - обогревали земной шар.

Пришлось пустить под плинтусом новый кабель на кухню.

[Ales]

vek88 в сообщении #279945 писал(а):

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

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

-- Ср янв 13, 2010 00:07:43 --

vek88 в сообщении #279950 писал(а):

принцип сжатых отображений - слышали про такой

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

[vek88]

Ales в сообщении #279957 писал(а):

vek88 в сообщении #279945 писал(а):

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

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

Ну, если Вы математик, то у Вас будут урматы?

А если серьезно, согласен, что в Задаче 2 полезнее некие навыки из физики, нежели из урматов. Хотя, строго говоря, вполне достаточно (в данном случае) школьной физики.

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

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

[Ales]

vek88 в сообщении #279961 писал(а):

Ну, если Вы математик, то у Вас будут урматы

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

[vek88]

Ales в сообщении #279967 писал(а):

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

Есть два вида наглости: наглость мехмата и наглость физтеха.
Мехмат. Я все знаю, а что не знаю - это чушь собачья.
Физтех. Я ни хрена не знаю, но все нужное быстро узнаю.

Но вернемся в тему. Итак, арифметика (обычная, интуитивная) непротворечива и полна.
И таможня дает добро, т.е. Гёдель против этого не возражает.

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

[Ales]

vek88 в сообщении #279950 писал(а):

Стал тестером мерять напряжение на щитке - оказалось на земле (не на нейтрали, а на земле) 220 вольт.

Я специально прочитал в Википедии: от этого помогает УЗО - устройство защитного отключения. Оно выключает электричество, если есть даже небольшая утечка тока из сети, то есть когда ток по фазе не совпадает с током по нейтрали.
Вообще рекомендуют делать УЗО. Вы бы тогда сразу бы узнали про утечку.
Главное: УЗО спасает от удара током.

Может Вам так специально местные энергетики проводку сделали, чтобы Вы больше денег им платили?

У меня дома и на даче нет ни заземления, ни УЗО, и вообще для меня непривычно провода делить: электричество от счетчика или из розетки, а где там фаза ....

-- Ср янв 13, 2010 14:15:17 --

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

[vek88]

Ales в сообщении #280095 писал(а):

Я специально прочитал в Википедии: от этого помогает УЗО - устройство защитного отключения. Оно выключает электричество, если есть даже небольшая утечка тока из сети, то есть когда ток по фазе не совпадает с током по нейтрали.
Вообще рекомендуют делать УЗО. Вы бы тогда сразу бы узнали про утечку.
Главное: УЗО спасает от удара током.

Может Вам так специально местные энергетики проводку сделали, чтобы Вы больше денег им платили?

У меня дома и на даче нет ни заземления, ни УЗО, и вообще для меня непривычно провода делить: электричество от счетчика или из розетки, а где там фаза ....

-- Ср янв 13, 2010 14:15:17 --

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

Про УЗО все так. Его достоинство - реагирует даже на незначительный ток утечки, порядка 30 миллиампер (в моем случае утечка была 18 ампер!). У меня гидромассажная ванна сидит на своем УЗО. А когда строил дом, было не до УЗО по простой причине - жутко экономил. Кстати УЗО спасает не от всех раскладов, например, если у Вас на кухне пролилась вода и где-то она в контаке с нейтралью, а на корпусе газовой плиты оказалась фаза, то не приведи господи - УЗО даже и не тявкнет. Поэтому надо соблюдать главное правило - стоя на сыром не хватайся за провода или корпуса электроприборов. А работая с электроприборами в саду тщательно проверять целостность изоляции и работать в сухой обуви.

А в старой даче все как у Вас - два провода (нейтраль и фаза, но никто никогда не думал кто из них кто).

Покончив с электричеством вернусь к арифметике. Согласен с Вами по стандартной модели. А нестандартными даже не интересовался - поэтому в них не копенгаген.

Уже хотел уйти, но кошка залезла мне на колени и не дает уйти от компьютера. Поэтом повторю (где-то уже говорил это выше или в другой теме) еще одну мысль. Если кто-то предпочитает рассматривать формальную арифметику, то я посоветую рассматривать нефинитную формализацию арифметики - тогда с Гёделем тоже все будет в порядке - нефинитная (уровня $\Pi_1^1$) формальная арифметика полна и непротиворечива.

[Ales]

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

И вот А.А.Марков тогда сказал такую фразу: "Таких чисел не бывает", что очень перепугало доклачика

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

[Sashamandra]

vek88 в сообщении #280028 писал(а):

Стандартная интерпретация арифметики дается, грубо говоря, ей же самой

А если не грубо, а поподробнее. Что это за стандартная интерпретация? На каком множестве (или что там у вас) она осуществляется?

vek88 в сообщении #280028 писал(а):

Она и является стандартной моделью арифметики.

Отлично! Значит мы имеем еще одно понимание стандартной модели арифметики. Так разъясните подробнее эту стандартную модель. Выше вы утверждали, что знаете, что арифметика полна. Отлично! Никто не спорит. Изъясните, пожалуйста, свое понимание. Ради этого топик и был открыт.
ЗЫ
Вы там писали, что арифметика (обычная, интуитивная) непротворечива и полна.
Что это за обычная, интуитивная арифметика? Может мы говорим совершенно о разных предметах?

[vek88]

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

1. Есть множество натуральных числе $N$.
2. На нем определены обычные операции сложения и умножения.
3. Арифметические формулы строятся обычным образом с использованием операций пункта 2, констант и переменных (на $N$), логических связок и кванторов.

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

Пока хватит - хочу получить от Вас ответ - в этих 3-х пунктах все ясно, или мы с Вами уже разошлись?

[Sashamandra]

vek88 в сообщении #280157 писал(а):

Давайте поставим скромную задачу - найти то место, где наши с Вами пути расходятся.

Мне это нравится.

vek88 в сообщении #280157 писал(а):

1. Есть множество натуральных числе $N$.

Это и есть основная и единственная проблема топика. Это и есть стандартная модель. Можно остальное далеко отложить и сконцентрироваться на этом. Как, с вашей точки зрения, это множество определяется, задается, строится? Каким образом оно в математике становится определенным предметом?

[vek88]

Sashamandra в сообщении #280160 писал(а):

vek88 в сообщении #280157 писал(а):

Давайте поставим скромную задачу - найти то место, где наши с Вами пути расходятся.

Мне это нравится.

vek88 в сообщении #280157 писал(а):

1. Есть множество натуральных числе $N$.

Это и есть основная и единственная проблема топика. Это и есть стандартная модель. Можно остальное далеко отложить и сконцентрироваться на этом. Как, с вашей точки зрения, это множество определяется, задается, строится? Каким образом оно в математике становится определенным предметом?

Вот и славно - пам-па-рам. Хотя было бы еще лучше, если бы Вы так сразу и сказали.

Простейшее определение - (финитное) формальное. Например,

Переменная: $x$
Знак: /
Вспомогательный знак: $N$
Комментарий: для удобства дальнейших ссылок знак $N$ маркирует натуральные числа
Аксиома: $N$
Комментарий: пустое слово - это натуральное число.
Правило вывода: если $Nx$, то $Nx/$
Комментарий: приписывание палочки дает следующее натуральное число.

Мы определили все натуральные числа. Эффективно проверяется является ли любая строка знаков натуральным числом.

Что Вас здесь не устраивает?

[Sashamandra]

vek88 в сообщении #280168 писал(а):

Хотя было бы еще лучше, если бы Вы так сразу и сказали.

Вообще то я так сразу и говорил. Ведь это же и есть, по вашему, стандартная модель арифметики. Ведь так?

vek88 в сообщении #280168 писал(а):

Что Вас здесь не устраивает?

Вы даже не представляется, как много меня не устраивает. Есть принципиальные возражения, есть, так сказать, стилистические. Буду перечислять по порядку.
Во-первых. Я не приемлю использование переменный независимо от области ее определения. Другими словами, переменной можно пользоваться только в том случае, если область ее определения (или изменения, как хотите) задана.
Во-вторых. Вспомогательный знак $N$ я бы предпочел исключить как несущественный. Хотя не настаиваю.
В-третьих. Ваше выражение "Аксиома $N$" я просто не понял. Что это значит?
В-четвертых. Я знаю, что пустые слова широко используют в теории алгоритмов. Но я бы предпочел начинать с некого знака, например, 0 или 1 как исходного.
Пожалуй лишь к правилу вывода у меня нет замечаний.
В результате мы не определили ни одного числа. Разве что 0 или 1, которых у вас не было.
Согласен, что если есть число, мы можем эффективно в этом убедиться.
Вот такие мы разные. Что прикажете делать?

[Xaositect]

Sashamandra в сообщении #280177 писал(а):

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

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

-- Ср янв 13, 2010 18:20:31 --

Sashamandra в сообщении #280177 писал(а):

В результате мы не определили ни одного числа. Разве что 0 или 1, которых у вас не было.

Можно определить сложение, умножение и возведение в степень как примитивно рекурсивные функции.
А далее определить перевод строк в алфавите $\{0,1,\dots,9\}$ в алфавит $\{|\}$, и назвать это десятичной системой записи чисел.