September 2nd, 2014

moose, transparent

чуть-чуть об алгоритмах (англ.)

(может быть интересно читателям со склонностью к математике, компьютерам итп.)

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

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

Algorithms are clever ways to pack up an infinity of data into a finite description.

Say there’s an infinite (here and below “infinite” means “countably infinite”; if you don’t know what that means, ignore this remark) binary string of zeroes and ones, some 010010101101111… Suppose I come up to you and I say: “I am the keeper of this infinite string of data. People come to me and ask: what is at the 13th place in this string, 0 or 1? How about 23523238th place? For any query they ask, I think for a while and then give them the correct answer. But I’ve been doing this for a long time and could use a vacation. Could you take over for me for a while? The job pays well.”

You might reply to me: Collapse )
moose, transparent

иногда

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

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

Вот у вас бывает такое? А с чем еще, если бывает?

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

Друг: страшно ж наверное?

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

Друг: это как, почему они раскрываются?

Путешественник: я не знаю.

Друг: А они знают?

Путешественник: и они не знают, я спрашивал у людей наугад в лифте.

Друг: но доверяют?

Путешественник: доверяют.

Друг: камикадзе какие-то.

Путешественник: как-как ты сказал? "Камикадзе" начали говорить только в 40-х, я тебе про японцев ничего не рассказывал.

Друг: блин, на такой дурости спалился. Вынимает бластер. Прости, друг.)
moose, transparent

история математики

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

Пока что по-английски я нашел следующие рекомендации:

- D. J. Struik, A concise history of mathematics. 250 страниц (действительно concise, видимо), для широкого читателя.
- Morris Kline, Mathematical Thought from Ancient to Modern Times. Три тома по 400 страниц в каждом, т.е. очень, очень подробная история.
- John Steelwell, Mathematics and its History. 600 страниц, предназначена для студентов-математиков, а не широкого читателя. С упражнениями (!).

Если у вас есть мнения об этих книгах, или если есть другие книги лучше этих (по-английски или по-русски), расскажите мне о них, пожалуйста.
moose, transparent

новые сведения о солдатах РФ на украине

Несколько важных ссылок:

  • Как оказался на войне и погиб 20-летний Антон Туманов, житель Козьмодемьянска Республики Марий Эл. Рассказ мамы.
    По словам сослуживцев, приказ перейти границу с Украиной пришел 11 августа. Тех, кто отказывался, командование оскорбляло, стыдило, угрожало уголовным преследованием. Все документы и телефоны приказали сдать, форму снять (все переоделись в простой камуфляж), на технике замазать опознавательные знаки и номера. На ноги и руки повязали узкие белые повязки: позже Туманова нашла в «ВКонтакте» фотографию сына с такими повязками и комментарием его сослуживца: «Это знаки опознавания свой-чужой. Сегодня на ноге, завтра на правой руке и т. д. Все, что движется без повязок, — уничтожается».

    Ночью 12 августа колонна из 1200 человек зашла в Украину и днем 13-го остановилась на территории завода в городе Снежное Донецкой области в 15 километрах от границы. Машины с боеприпасами и оружием поставили очень скученно. Днем 13 августа по колонне ударили из «Градов».


  • Статья о Льве Шлосберге, разговор с ним в больнице, где он лежит после нападения.

    - После статей о закрытых похоронах десантников люди ко мне потянулись, поверили, — говорит Лев. – Они начинают понимать последствия, понимать, куда их загоняют. Первую тысячу человек отправили 15-16 августа, вторую собирали на прошлой неделе, и они должны были уйти 29 августа. И я знаю, что поставлена задача собрать третью тысячу бойцов, но с этим уже начинаются проблемы – люди не хотят вот так погибать.

    Молчание семей, в которых погибли или ранены псковские военные – это один из главных вопросов, который волнует всех. Лев рассказывает об одном бойце, лежащем сейчас в Ростове с тяжелым ранением: «Его мать пишет на своей страничке, какие «журналюги сволочи», «всё это придумано», а её сын «жив-здоров». При этом он с чудовищной кровопотерей в госпитале, у него ампутирована нога.


  • «Всю роту положили».

    Новый репортаж "Псковской губернии", Льва Шлосберга и Алексея Семенова. Записи разговоров с десантниками, непосредственно участвовавшими в боевых действиях. В первом разговоре, в частности, рассказывается о бое, в котором погиб Леонид Кичаткин. Судя по некоторым особенностям разговора, это не телефон, а видео, Скайп наверное.

    Голос 2: Сколько человек погибло то, б?..
    Голос 1: Да до…
    Голос 2: Ты не знаешь вообще? Ну человек 40, 50, 100, блин?
    Голос 1: 80.
    Голос 2: Восемьдесят?
    Голос 1: Угу… Это вместе с Черёхой…
    Голос 2: Это одну роту?
    Голос 1: Это вместе с Черёхой, с Промежицами, всё вместе.
    Голос 2: Потому что слух шёл, б..., что там 140, нах...
    Голос 1: Да? Может быть.
    Голос 2: Ну это со Пскова.
    Голос 1: Ну не знаю, это вместе с Промежицами, Черёхой, со всеми.


  • Неизвестные солдаты на необъявленной войне. Еще один материал из "Псковской губернии". Рассказ о встречах с женами десантников, о нападениях на журналистов, которые ездили на кладбище.

    «Когда уехал ваш муж?» - «Две недели назад… В понедельник они поехали на учения в Кислово (полигон под Псковом, рядом с Выбутами. – Авт.). В четверг он мне позвонил и сказал, что их срочно отправляют. До этого я ему позвонила и спросила: "Вас точно никуда НЕ отправляют?". Он ответил: "Точно". А через десять минут перезвонил и сказал, что пришлёт список вещей… Я собирала ему вещи. Они вечером в четверг уехали на аэродром, и в пятницу вылетели». – «Много было народу на аэродроме?» – «Пятьсот из дивизии и пятьсот из Черёхи… Он ОТТУДА звонил три дня назад, и говорил, что если что случится, чтобы я не боялась… И квартиру, и всё до копейки, всё что можно, от армии получила… Чтобы не было напрасно». – «Он сказал, где находится?» - «Он сказал, что "нас бомбят уже неделю, а завтра мы идём в наступление"». – «Это когда он сказал?» - «Двадцать пятого числа».


Почитайте - больше всего информации в последних двух ссылках, но во всех четырех ее хватает. Сайт "Псковской губернии" лежит на данный момент, я даю ссылки на копии статей в журнале автора, Льва Шлосберга.