Ни о какой безапелляционности в моих высказываниях не может быть и речи!

Из блога Скотта Ааронсона я узнал сегодня, что мы теперь точно знаем значение BB(5) - функции Busy Beaver на 5 состояниях. Это одновременно тривиальная и захватывающая новость. Это что-то, про что я не был уверен, что будет известно в течение моей жизни - хотя полагал вероятным.

Что такое Busy Beaver? Попробую вкратце объяснить.

В информатике есть понятие "машина Тьюринга". Это не настоящая физическая машина из транзисторов, а теоретическая модель. Представьте себе бесконечную ленту, состоящую из ячеек, в каждой из которых может быть записано '0' или '1' (в общем случае можно и больше разных символов, но достаточно двух). Изначально на ленте везде написано '0', и над одной из ячеек находится головка чтения-записи, которая может находиться в одном из нескольких состояний (представьте себе переключатель, который может быть в положении A,B,C или D - это пример 4 состояний). За один шаг головка машины смотрит, что написано на ячейке, над которой она сейчас находится, а потом справляется в "таблице переходов". В таблице написано, например: если ты в состоянии A и видишь 0, то перейди в состояние B, напиши 1, и сдвинься вправо. И так на любую комбинацию "состояние-что я вижу" есть рецепт: в какое состояние перейти, что написать, 0 или 1, и куда сдвинуться, влево или вправо. Потом машина делает следующий шаг по таким же правилам. И так далее, пока она не войдет в состояние, которое заранее считается "конечным", например D, и тогда она останавливается.

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

В 1962 году венгерско-американский математик Тибор Радо задал следующий вопрос. Обычно для того, чтобы сделать что-нибудь "интересное" машиной Тьюринга, нужно много состояний. Состояния играют роль внутренней логики алгоритма, позволяют машине "помнить", где она находится внутри сложного алгоритма, что она уже выяснила, итд. Но давайте для любого N посмотрим на все возможные машины (т.е. разные таблицы перехода) из N состояний, и что они делают с пустой лентой (все нули). Одни программы быстро остановятся, войдя в состояние остановки; другие войдут в бесконечный цикл, или уйдут "в бесконечность" без цикла - например, будут писать 1, двигаясь все дальше и дальше по бесконечной ленте без возврата. Но есть какая-то машина, которая в конце концов остановится, но после наибольшего числа шагов по сравнению со всеми остальными из N состояний. Такая машина-чемпион называется Busy Beaver. Сколько шагов она сделает перед тем, как остановится, для данного N?

Для очень малого числа состояний, 1-2-3, легко перебрать все возможные машины и посмотреть, что они делают, слишком примитивными они являются. Для 4 состояний максимальное число шагов перед остановкой равно 107, и это доказали в 1983 году. Однако уже 5 состояний позволяют сделать хитрые машины, про которые нелегко понять, они делают что-то бесконечное, или все-таки остановятся рано или поздно. С 1990 года есть кандидат - машина, которая останавливается после 47 миллионов шагов - но чтобы доказать, что она чемпион, нужно перебрать все возможные машины из 5 состояний, а их 16 триллионов! Проблема в том, что нет универсального метода определить, остановится данная машина или нет (это как раз "проблема остановки", которую принципиально невозможно решить с помощью алгоритма). Можно либо запускать ее на симуляторе, желательно очень оптимизированном, делающим миллионы шагов в секунду, и ждать, пока она остановится, либо искать математическое доказательство того, что никогда не остановится - а его надо искать для каждого сложного случая отдельно. К началу 2000-х осталось только около 40 сложных случаев - машин, которые скорее всего никогда не останавливаются, но доказать это пока не могли. В принципе могло бы оказаться и так, что одна из них "моделирует" сложную математическую проблему. Скажем, есть машина из 23 состояний, которая останавливается только если неверна знаменитая гипотеза Гольдбаха, которую никто не может доказать уже несколько сотен лет. Но 5 состояний все же настолько мало, что такое казалось маловероятным. И вот, после нескольких лет усердной работы фанатов этой проблемы в последние годы, им удалось избавиться от всех сложных случаев, и доказать то, что все подозревали - что кандидат 1990 года и есть чемпион. Все технические подробности - на сайте bbchallenge.org!

Проблема Busy Beaver - странная, любопытная штука. С одной стороны, не очень ясно, зачем ей заниматься. Найти общую формулу или метод для любого N невозможно в принципе. Ответ для N=5 никакой конкретной пользы ни для чего не приносит. Ответ для N=6 скорее всего останется недоступен для человечества за все время его существования. Более того, то, как именно сформулирована задача (какое из нескольких определений простой машины Тьюринга используется, например) "все меняет" в смысле ответа и его доступности нашим усилиям, так что задача в любом случае довольно "искусственно" выглядит. И все равно есть что-то притягательное в ней для горстки программистов и математиков, которые продолжали активно работать над ней все эти годы.

Я это хорошо понимаю, потому что много лет назад внес свой крохотный вклад в этот сизифов труд. Тогда был свежий и многообещающий кандидат в ряды Busy Beaver из 6 состояний, который останавливался после 8 квадриллионов шагов (квадриллион это миллион миллиардов), но этот факт еще никто не подтвердил независимо от первооткрывателя этой машины (столько шагов невозможно было запустить "напрямую" симулятором, надо было придумать и написать специальную программу, которая использует логику этой конкретной машины). Я помню, что написал такую программу, подтвердил результат и послал первооткрывателю, но не мог вспомнить сегодня, когда это сделал, думал, что где-то в начале 2000-х. Но потом нашел упоминание, которое все еще лежит на сайте этого человека: "No 2 has been verified independently by Anatoly Vorobey <mellon@pobox.com>
at 20 Sep 1997. He was the first to detect that the original number of steps were one too large (corrected above)."

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

BB(5) = 47,176,870

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

Я прочитал дискуссию о том, почему стандартный курсор мышки наклонен влево (утверждают, что в 70-х так сделали в GUI-системе Xerox Parc, одной из первых в мире, потому что на маленьком разрешении экрана линия под углом 45 градусов отчетливее выглядела, чем прямая).

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

Гипотеза полностью провалилась. Я замечаю каждый день. Каждые несколько минут. Я так больше не могу. Возвращаю обычный курсор.

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

Я 2 или 9, по обстоятельствам. Неоднократно пробовал 3 и 4, не моё.

Прошло меньше времени от конца Второй Мировой войны до первой версии Ворда от Майкрософт, чем от первой версии Ворда до наших дней.

(сегодня исполнилось 39 лет)

Любопытное интервью с последним в Америке продавцом дискет всех видов: We Spoke With the Last Person Standing in the Floppy Disk Business

Это не последний производитель, кстати; из статьи неясно, сколько осталось производителей (похоже, что есть еще китайские компании, которые выполняют большие заказы на дискеты, но качество сильно упало в последние годы). Это владелец floppydisk.com. У него есть большой запас новых дискет, которые он закупил 10 лет назад, плюс он постоянно получает от людей ненужные им дискеты, в том числе ни разу не распакованные. Интересно, что он продает также пятидюймовые дискеты, и даже восьмидюймовые, для тех месье, которые реально знают толк в извращениях.

Там много интересного о том, кому еще нужны дискеты в наше время (в основном индустрия, старые станки, медицинские аппараты, самолеты, итд. итп., но и любители-реставраторы тоже попадаются), о том, как работает его бизнес и как менялся с годами. Я не догадывался о том, что с точки зрения производства сделать дискету намного тяжелее, чем CD или DVD-диск: как он это объясняет, после того, как технология налажена, сделать CD или DVD это залить пластмассу в один конец машины, получить диски из другого конца; а дискета состоит из 10 разных частей, разных материалов (пластмасса, металл, пружина итд.), которые должны быть точно пригнаны друг к другу, автоматическая сборка требует серьезного контроля над качеством итд. итп.

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

В комментариях в HN много интересного, особенно когда люди начинают вспоминать, как мы все в 80-е и 90-е мудох... извините, наслаждались дискетами, и у меня тоже в голове вспыхивает лампочка, да, да! Помните, как сердце екало, когда слышал характерный скрежет дисковода, который означал, что он один и тот же сектор читает, пытается преодолеть ошибку чтения? Помните, как оно было, устанавливать Линукс с 38 дискет, и 23-я не читается? Помните наклеечки и коробочки и программы-каталоги? Помните этот звук, с которым трехдюймовая входит в дисковод: кчюк! Помните?

В фейсбуке есть израильское сообщество "в 90-х на этой неделе", там всякие заметки из прессы 90-х, реклама итд. Сегодня попалась реклама компьютера 30 лет назад, октябрь 1991:



"Цветной компьютер AT". Два дисковода для дискет размером 5 1/4. Отдельно упоминаются "часы реального времени с поддержкой батарейки". Вместе с покупкой дают бесплатный абонемент на "библиотеку игр" на год (не помню такого; видимо, в магазин можно было приходить и брать дискеты с играми на время).

Здесь не написана модель процессора, но я уверен, что это 80286, и вообще компьютер очень устаревший для октября 1991 (скорость без турбо всего 12 мегагерц, нет жесткого диска). Поэтому и цена довольно низкая, 1777 шекелей; хоть, конечно, тогда это было намного больше денег, чем сейчас. В это время наша семья уже четыре месяца жила в Израиле, и я начал учиться в израильской школе, в предпоследнем классе. Где-то месяца через четыре у нас впервые появится собственный компьютер, он был на основе 80386, с жестким диском размером в 80MB. Мне кажется, мы заплатили за него примерно 3200 шекелей.

До флеш-карт, до DVD-дисков, до компакт-дисков, задолго до всего этого люди пользовались, для хранения данных, дискетами. Те из нас, кто помнят это древнее время, скорее всего пользовались маленькими дискетами на 3,5 дюйма, в которых данные записывались на магнитный диск. И почти никто уже не помнит, как работали большие гибкие пятидюймовые дискеты. В них, как видно, если присмотреться к этой фотографии, данные считывались с хранящейся внутри дискеты перфокарты.

Фотографии из твиттера Даны Сиберы https://twitter.com/NanoRaptor/, у которой есть еще много интереснейших артефактов компьютерной истории, горячо рекомендую.

Я сделал первые шаги на пути к аудиофильству (вполне возможно, что последние, потому что больше мне и не надо будет), и впервые в жизни купил вместе с телевизором AV-ресивер и набор 5.1 (5 колонок и сабвуфер). До сих пор всегда обходился звуком самого телевизора.

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

Теперь у меня есть, разумеется, наивные вопросы!

(ресивер Onkyo TX SR393, телевизор LG OLED65CX)

1. Что делает ресивер, кроме перевода звука из цифрового в аналоговый? В частности, я не вполне понял, что происходит, если ресивер получает обычный стерео звук. Он сам решает, какие части этого звука идут на три другие колонки и сабвуфер, или просто посылает его на две боковые и все? Если 'сам решает', то как это устроено, и отличаются ли ресиверы друг от друга по качеству этих алгоритмов? Чем вообще супер-крутые ресиверы отличаются от менее крутых в смысле качества звука?

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

3. Процитирую свое сообщение в чате, если кто-то хочет добавить критику/рекомендацию, милости прошу :)

"Там есть всякие интересные вопросы которые остались не до конца выясненными, возможно из-за того, что ресивер не супер продвинутый (но я вполне ок как минимум начинать с такого). Типа: * подключил нам все девайсы (приставку, стример, TV box) к телевизору, а от него по оптическому кабелю к ресиверу. И это вполне работает. Но теоретически это теряет данные аудио, если они приходят в Dolby Atmos и других супер-продвинутых форматах. Оптический кабель столько не тянет. Т.е. если я скачаю тяжелый качественный фильм со звуком, уже оптимизированным на surround, то он уйдет в телевизор, но телевизор ресиверу отдаст обычный стерео звук (или 5.1?), а тот уже сам заново решит, какой колонке что дать (и не так оптимально). Так я понимаю, возможно, неверно.

По этим причинам более стандартный режим - это когда подключаешь девайсы к ресиверу, а ресивер к телевизору HDMI-кабелем. Ресивер умеет любой звук и любое видео принимать, на то он и ресивер. Но тогда возникает интересная проблема, если пользуешься телевизором как smart девайсом, напр. для ютуба или кромкастаешь на него, то ресивер не получает звук от телевизора, приходится пользоваться его родным звуком, а не крутыми колонками.

Специально для этой цели придумали протоколы ARC и более новый eARC. В них когда ты подключаешь ресивер кабелем HDMI к телевизору, телевизор умеет по этому же кабелю обратно передавать свой звук ресиверу, а тот умеет включать его в струю. Но у этих протоколов очень геморройная поддержка, во всех телевизорах по-разному она включается, и ресиверы в разной степени ее поддерживают, и зависит еще от того, что идет по каналу звука, и вообще все сложно. Я попробовал это так подключить, но так и не смог сделать, чтобы заработало. хотя сделал несколько танцев с бубнами, которые нагуглил. То ли виноват телевизор LG, то ли ресивер Onkyo, то ли их сочетание, то ли я. Но все это было в общем для любопытства, все устраивает и так."

Какие полезные бесплатные программы установлены у вас на домашнем компьютере/ноутбуке? Пользователям Линукса можно не отвечать :)

Перечислю свои (Windows):

7-Zip
Anki
Audacity
Calibre
LibreOffice
Notepad++
qBittorrent
SMPlayer
WinDJView
youtube-dl

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

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

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

Вот уже несколько дней не могу придти в себя. Как же это так? Умом понимаю, но сердце отказывается. Нет протокола, нет хендшейка, нет версии, нет контрольной суммы, но как?! Даже битов нет, один голый ток. Есть в этом что-то неприличное, непристойное. Будто кто-то разделся, извалялся в грязи и в таком виде бегает по улицам и машет руками. На наушники теперь смотрю с подозрением. Вот они, лежат передо мной, провод извивается и уходит к разъему в компьютере. А по этому проводу такое идет, ну как же это так?