100-летие Тьюринга
2012-06-23 05:44На главной странице «Гугола» сегодня действующая машина Тьюринга. А вот несколько действующих машин на «Ютубе» — из чего только их не строят!
http://www.youtube.com/playlist?list=PLF87F259C658F6872
…популярность и быстрый рост Джавы во многом обусловлена ее социальностью — легко научиться что-то программировать. В сравнении с внешне похожим, но куда более сложным С++, в умелых руках способным творить чудесные программы и системы.Три раза дададада!!! Учеба, кстати, в отличие от работы (и научной, и инженерной), есть процесс индивидуальный, или, в этих терминах, асоциальный. Если вам предстоит обучаться вычислительной математике, учитесь программированию на функциональном, асоциальном языке. Второй язык уже может быть любым.
Социальность не всегда значит хорошо. Если меня спрашивают, а такое порой случается, то в качестве языков для обучения студентов я всегда рекомендую именно асоциальные языки. Их сложность и строгость гарантируют, что человеку придется напрягать мозги и разбираться, а это безвозвратно, к счастью, не проходит. Впоследствии другие языки покажутся простыми.
RP Feynman. Simulating Physics with Computers. International Journal of Theoretical Physics, v. 21, Nos. 6/7, 1982. pp 467—488. Стенограмма лекции на 1-й конференции по вычислителной физике, MIT, 1981 г.
Замечательная статья с объяснениями того, почему для квантово-механических вычислений требуются квантовые компьютеры. Отличное объяснение парадокса Эйнштейна-Подольского-Розена и теоремы Белла. Фейнман великолепно объясняет сложные вещи; лекция очень понятна.
Говорили, будто, мол, Фейнман доказал, что физика невычислима на обычных логических компьютерах — это неверно; он показывает только, что эти вычисления требуют экспоненциального времени и квадратичной памяти:
Хочу ввести такое ограничение, чтобы число элементов вычислительной машины, необходимых для моделирования физической системы, было прямо пропорционально объему пространства-времени системы. Мне не нужно экспоненциальное расширение [объема вычислений]… Если удвоение [объема] пространства-времени означает, что мне требуется экспоненциально больший вычислитель, то это против правил (я устанавливаю правила, так что мне — можно).
Выдеру цитату об истолковании квантовой механики:
Должен здесь сразу заметить, что там, куда мы направляемся [в объяснение парадокса ЭПР], у нас всегда были проблемы — секрет, секрет, закройте дверь! — у нас всегда были проблемы с пониманием картины мира, описываемой квантовой механикой. У меня, во всяком случае, потому что я уже слишком стар [Фейнману 63 года], чтобы говорить, что это все для меня очевидно. Да, меня это состояние дел беспокоит. Поэтому, некоторые из молодых студентов… знаете, как это всегда бывает: каждая новая идея, ей требуется поколение-другое, чтобы всем стало очевидно, что там нет настоящей проблемы. А мне еще не ясно, что там нет настоящей проблемы. Я не могу определенно сказать, что это за проблема, я подозреваю, что там нет никакой проблемы, но до конца я не уверен.
К вычислимости нашей сознания особого отношения не имеет, но введение в тему очень хорошее.
Великолепная серия из 8 заметок Брайана Макнамары (Brian McNamara) из исследовательского отдела «Микрософта» о функциональных катаморфизмах. Ориентированы на практическое применение, с хорошими примерами, очень понятно написаны.
В помощь Гуголу с Яндексом: катаморфизм катаморфизмы катаморфный. А то что-то они катаморфизмы склонять не умеют.Меня спросили в одном обсуждении о том, совместима ли спонтанность сознания с алгоритмической организацией. Покажу, что спонтанность, непредсказуемость с алгоритмами еще как совместима. Математикам это, конечно, хорошо известно. Например, компьютеры не производят истинно случайных чисел: алгоритмы генерируют так называемые псевдослучайные последовательности, которые некоторыми математическими проверками неотличимы от случайных. Непредсказуемы это ряды чисел и для нашего разума. Человек, как и другие млекопитающие и даже насекомые, прекрасно обучаем. Мы находим образцы очень легко, помимо воли, даже помимо сознания. Ежесекундно мозг перерабатывает многие тысячи возможных совпадений, отбирая будущие «штампы» поведения, будущие слова в языке, а у кого-то и будущие великие открытия. Однако, в рядах псевдослучайных чисел мы не видим никаких закономерностей. Те, кто играл, например, в «сапера» или раскладывал на компьютере пасьянсы, хорошо знают, что предсказать, где будут спрятаны мины или какая карта откроется из колоды следующей, не получается, даже если днями напролет целыми месяцами играть!
Каков же критерий «спонтанности», непредсказуемости? Математика пользуется более строгими определениями, чем «неясно, что будет дальше», Вместо того мы говорим о «неупрощаемых вычислениях». Последовательность вычисленных алгоритмом чисел считается неупрощаемой, или нередуцируемой, если нет более простого способа узнать, каким будет следующее число в ней, чем просто взять и вычислить все предыдущие. Другими словами, сказать, что будет делать алгоритм через тысячу, или миллион, или N шагов нельзя предугадать иначе, чем запустив этот алгоритм и подождав, пока он эти шаги не сделает, потому что нет более простого алгоритма, чтобы получить тот же результат за меньшее время вычисления.
( Кажется понятным, что какие-то сложные, громоздкие вычисления приведут к сложному результату, а простые формулы дадут простые, редуцируемые последовательности… )Видим, что эти все вычисления легко упрощаемы и предсказуемы. Пока что все идет, как и предполагает здравый смысл: простой алгоритм — просто предсказуемый результат. Так ведь всегда бывает?
Нет. Достаточно только положить коэффициент при x2 равным двум (рис. 7), и поведение простого алгоритма тут же делается сложным, таким, что в нем нет никаких циклических повторений. Этот алгоритм математически неупрощаем: самый простой способ узнать xn тот же, что и самый сложный: вычислить x2 из x1, x3 из x2 и так далее, и, в конце концов, xn из xn-1.
Рис. 7.
Ну и что, скажете вы, ведь математика — просто выдумка, система правил, происходящих из положенных истинными аксиом. Аксиомы те, конечно, не случайны, а выбраны для описания нашего мира; математика — не только и не столько игра для ума, сколько мощнейший инструмент для описания физического мира вокруг нас. Она бы не была таковой, если бы начала математики не были положены из наблюдений природы, от счета камушков до общей теории относительности. Однако, возразите вы, математика прекрасно описывает физические явления, но мало ли чего она еще описывает? Не все, что следует из математики, встречается в реальности! Где же видано в природе сложное поведение, чтобы оно следовало из простого итеративного алгоритма?
( Ответ: на Земле и на Сатурне… )Итак, задача нашего объяснения исполнена: существуют простые алгоритмы, дающие нередуцируемый, то есть не предсказываемый проще, чем исполнением алгоритма, результат, и такие алгоритмы имеют непосредственное отношение к наблюдаемым в природе явлениям. Не только погода, но и экономика, например, тоже является сложной системой; биосфера континентов и Земли в целом тоже оказывается сложной, хотя численности популяций в коротком приближении очень хорошо описываются такими же простыми итеративным алгоритмами. Сознание тоже, по-видимому, является сложным, непредсказуемым продуктом простого алгоритма, или, скорее, многих взаимодействующих простых алгоритмов. Во всяком случае, модель одного нейрона проста, а модели нейронных сетей, построенные из математических нейронов, проявляют свойства вполне напоминающие сознательные: узнавание изображений, например, или распознавание текста, и, главное, поиск закономерностей и их запоминание, то есть обучение.
«Спонтанность» же, в отличие от нередуцируемости, возможна лишь в глазах наблюдателя. Непредсказуемость мы не делаем равной свободе воли или спонтанности: поведение похожего на огромную дырчатую картофелину куска камня в космосе не называют спонтанным, а ураганам, дождям и клубам дыма приписывают свободу воли, наверное, только синтоисты. Поведению же животных, а тем более человека, в обычной речи запросто придается и спонтанность, и свобода действий. На самом же деле, корень всех этих проявлений один, и лежит в одном и том же феномене, таком вездесущем и таком поздно замеченном и мало пока исследованном: хаосе.
И что же можно получить из простых итеративных формул? Вот такие картинки.
( Маленькие картинки ссылаются на полноразмерные изображения, нажимайте на них, чтобы рассмотреть. А захотите посмотреть на подобные изображения еще… )Русское название: Роджер Пенроуз. «Новый ум короля. О вычислительных машинах, разуме и законах физики». Номера страниц следуют в квадратных скобках за цитатами, и даются по изданию [Penrose 89]. Все переводы сделаны автором, изо всех сил старавшимся сохранить не только семантику, но и стилистику оригинала; последнюю, разумеется, не в ущерб первой. Ссылки на литературу в квадратных скобках и начинаются с фамилии автора. Ссылки на комментарии в конце статьи обозначаются «ножичко솻.
Эта книга захватывает читателя, захватывает новым, по крайней мере для вашего скромного собеседника, методом: в течение всего изложения автор обещает объяснить множество вещей, от необходимости квантово-механического объяснения работы его, читателя, мозга, до эволюционных преимуществ сознания, но не торопится с этими объяснениями. Подобного suspense ожидаешь от детективной истории, но никак уж ни от научно-популярной книги, ни от монографии.
В книге чуть более 450 страниц, но далеко не все они посвящены изложению теории ее автора. В задачу книги входит, как следует думать, предварительное образование читателя до уровня, необходимого для понимания обосновываемых Пенроузом идей. Книга состоит из десяти глав, из которых семь содержат в сжатом и, по видимому пониманию писавшего, популярном изложении определенные физические и математические теории. В главах со второй по девятую кратко и сжато излагаются основы следующих наук и дисциплин:
Список, как видите, нешуточный, и задача изложить эти науки в тех трехстах пятидесяти страницах, наверное, неразрешима. Поэтому не следует ставить Пенроузу в вину то, что он ее не исполнил: ( … )
I'd like to welcome you to this course on computer science. Actually, it's a terrible way to start off. Computer science is a terrible name for this business. First of all, it's not a science. It might be engineering, or might be art, or— you'll see that computer so called “science” has a lot of common with magic. You'll see that in this course.And it is not computer either!