:-P

[tyomitch]

А к нам в ту среду приедет лекцию читать Юрий Гуревич
Это, наверное, не менее круто чем Вирт, так?

[gaidar]

Не, круче Вирта мало людей осталось.

[tyomitch]

Как бы, типа, Вирт - это вчерашняя звезда. За последние 20 лет он ничего интересного не придумал и, наверное, уже не придумает.

А вот Гуревич - это звезда сегодняшняя. Из вступления к его лекции: родился в Челябинске, учился в Свердловске, в 28 лет защитил докторскую. Занимался какой-то алгеброй, вроде теории групп. В 1974 г. уехал в Израиль, оттуда - в США. В университете Мичигана заинтересовался информатикой, и как и положено чистому математику, задался вопросом: что представляют собой объекты информатики как науки?

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

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

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

Что самое важное: это не обычный профессор, сочиняющий непонятно что от скуки, а сотрудник Microsoft, создающий реально полезные продукты. Понятно, что система формального описания программ необходима и на этапе постановки задачи ("что должно получиться"), и на этапе тестирования ("то ли получилось, что надо"). Созданная его группой система постепенно внедряется во все отделы Microsoft; в частности, он хвалится, что отдел Windows уже использует эту систему.



gaidar, я тебя переубедил?

[d3drm]

второй раз действительно убедительно выглядит =)

[Approximator]

Про "неполноценность" машин Тьюринга .

Как математик-математику замечу г-ну Гуревичу.

Есть такая теорема МакКаллока-Питса: ЛЮБОЙ КОНЕЧНЫЙ процесс может быть ЭФФЕКТИВНО моделирован (преобразован в алгоритм) на машинах Тьюринга.

Переходя на более понятный язык аналогий можно сказать, что из упомянутой выше теоремы вполне себе следует существование такого описания для ПОЛНОЦЕННОГО моделирования на машинах Тьюринга всего того, что делает наш мозг...

Понятно, что ПОДОБНЫЕ лекции это PR и ничего более. Так что, уровень г-на Гуревича, конечно же, не показывают.

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

[tyomitch]

Есть такая теорема МакКаллока-Питса: ЛЮБОЙ КОНЕЧНЫЙ процесс может быть ЭФФЕКТИВНО моделирован (преобразован в алгоритм) на машинах Тьюринга.

Вы с ним, наверное, по-разному понимаете слово "эффективно".
Он приводит пример: решение СЛУ методом Гаусса конечно, но нереализуемо на МТ из-за того, что на её ленту нельзя положить действительные числа. Если же класть их приближённые значения (как и делается в реальных компьютерах), то погрешность метода достигает диких величин.

Согласен, что ТОЧНОЕ решение СЛУ методом Гаусса - это КОНЕЧНЫЙ процесс? На бумажке человеческий мозг его способен осуществить за конечное время.

Понятно, что ПОДОБНЫЕ лекции это PR и ничего более. Так что, уровень г-на Гуревича, конечно же, не показывают.

Ну, насчёт "ничего более" я бы поспорил, но то, что сотрудник Microsoft будет в своих лекциях пиарить свой продукт - совершенно ожидаемо.

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

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

[Approximator]

Есть такая теорема МакКаллока-Питса: ЛЮБОЙ КОНЕЧНЫЙ процесс может быть ЭФФЕКТИВНО моделирован (преобразован в алгоритм) на машинах Тьюринга.

Вы с ним, наверное, по-разному понимаете слово "эффективно".
Он приводит пример: решение СЛУ методом Гаусса конечно, но нереализуемо на МТ из-за того, что на её ленту нельзя положить действительные числа. Если же класть их приближённые значения (как и делается в реальных компьютерах), то погрешность метода достигает диких величин.

Так можно сделать (чтобы не получилось), но либо по незнанию - применяя слишком грубо "метод Гаусса"; либо преднамеренно.
Вобр какой у Гуревича случай оставлю тебе.
Почему это не правда объясню опять в виде СТРОГО ДОКАЗАННЫХ теорем. Есть теорема о СУЩЕСТВОВАНИИ сколь угодно гладкой аппроксимации ЛЮБОГО подмножества вещественного континуума решёткой. То есть, при решении системы линейных уравнений над множеством R^n всегда можно подобрать сколь угодно гладкую решёточную аппроксимацию. На качестве решения это не отражается в принципе.
Так что, эффективность мною понимается в общепринятом смысле.

Согласен, что ТОЧНОЕ решение СЛУ методом Гаусса - это КОНЕЧНЫЙ процесс? На бумажке человеческий мозг его способен осуществить за конечное время.

Всё это можно разложить и осуществить в алгоритмах для МТ. Всё будет сделано с ЛЮБОЙ заранее заданной точностью.

В остальном - тоже не переубедил .