Рассказы о математиках
Шрифт:
«Однажды, когда мне было лет десять, друг нашей семьи академик Лузин рассказал мне забавную историю о том, как Сократ открыл Платона, своего лучшего ученика. Николай Николаевич Лузин был настолько хорошим рассказчиком, что отличить, где у него правда, а где вымысел, было невозможно. Слушая его, я живо представлял себе, как Сократ, прогуливаясь, шел по родному городу. Вот он подошел к стройке и вдруг остановился. Ему бросилось в глаза что-то необычное. Все каменщики возводили стены, проделывая одни и те же движения. И только один из них клал камни по-особому. Сократ присмотрелся. Молодой рабочий берег силы. У него все было рассчитано. Там, где другие делали два движения, он обходился одним. И стена у него росла быстрее, и работал он с меньшим напряжением.
Сократ подозвал рабочего, взял его к себе жить. А через несколько лет из рабочего-каменщика получился
Николай Николаевич давно умер. Но я часто вспоминаю эту историю, которую впервые услышал от него.
Легенды легендами, а дело делом. Сейчас ученым и педагогам пришлось всерьез столкнуться с проблемой: как определить, есть ли у человека внутренняя тяга к разгадыванию новых для него явлений, к раскрытию больших и малых тайн природы? Когда педагоги станут делать это повсеместно, гораздо легче пойдет обновление школы, повысится и качество обучения» [101] .
101
М. А. Лаврентьев. Приглашение в науку. «Комсомольская правда», 1963, 17 августа.
«Чем раньше молодежь будет приобщаться к науке, тем быстрее и полнее будет отдача. Уже в средней школе надо развивать рвение к науке, к технике, изобретательству, отбирать тех, кто проявляет особый интерес к этому делу. Исключительно благородна роль скромных тружеников средней школы — учителей, которые умеют прививать своим питомцам любовь к тому или иному предмету. Между тем известно, что многие учителя ориентируются на средний уровень знаний.
Часто люди, особенно одаренные в одной области знаний, оказываются малоспособными в других областях. Если обнаруживается ученик с направленным, определенным интересом, учитель призван развить этот интерес. Его усилия должны, конечно, тактично учитывать и преподаватели по другим предметам.
„Нужно, чтобы учителя умело выявляли способности школьника, его тяготение к тому или иному предмету. К сожалению, умение школьника заучить и быстро ответить напамять выдается иногда за высокие способности. И как часто наши педагоги потом убеждаются в своей ошибке!“» [102]
102
М. А. Лаврентьев. Молодым — дорогу в науку! «Правда», 1960, 8 октября.
Петр Сергеевич Новиков (Род. в 1901 г.)
22 апреля 1957 г. Комитет по Ленинским премиям в области науки и техники при Совете Министров СССР опубликовал первое послевоенное постановление о присуждении Ленинских премий за выдающиеся работы в области науки и техники.
Из математиков Ленинской премии удостоен замечательный ученый нашего времени, действительный член Академии наук СССР Петр Сергеевич Новиков за свой научный труд «Об алгоритмической неразрешимости проблемы тождества слов в теории групп».
Алгоритмом называют единое правило (предписание), позволяющее указать путь решения для любой задачи из серии однотипных задач. Примером алгоритма может служит правило перемножения натуральных чисел. Если человек владеет общим правилом перемножения двух натуральных чисел и может перемножать и складывать однозначные натуральные числа, то он сможет перемножить два любых натуральных числа.
Широко известен алгоритм нахождения общего наибольшего делителя двух натуральных чисел путем последовательного деления (алгоритм Евклида).
Наличие алгоритма позволяет автоматизировать (нередко говорят — механически проводить) различные вычислительные процессы, связанные с решением серии однотипных задач. Если найден алгоритм решения серии однотипных задач, то можно построить машину, способную решить любую из этих задач (алгоритм позволяет составить программу, согласно которой машина будет решать каждую такую задачу). Если алгоритм разработать невозможно, иначе говоря, если он не существует, то построить такого рода машину нельзя. Конечно, это не означает, что для каждой из таких задач не существует свой способ решения, нет только единого метода их решения.
Вопросы, связанные с нахождением (разработкой) или с доказательством несуществования алгоритмов для решения задач, тех или иных серий однотипных задач, называются алгоритмическими проблемами. Алгоритмические проблемы исследуются в одной из отраслей математической логики — в теории алгоритмов, имеющей теперь большое теоретическое и практическое значение (в первую очередь для машинной математики).
Приведенное выше определение алгоритма не является точным; оно чисто описательное. Благодаря этому разработка алгоритмических проблем продолжительное время не могла быть развернута во всей полноте. Если для какого-либо круга задач алгоритм не существовал, отсутствие точного определения алгоритма не позволяло дать этому факту научное доказательство. В 30-е годы точное определение алгоритма было, наконец, разработано. Благодаря этому удалось установить наличие алгоритмически неразрешимых задач как в математической логике, так и в математике (Марков, Пост). Однако относительно некоторых математических алгоритмических проблем долгое время не удавалось выяснить, разрешимы они или нет. К их числу относилась и проблема тождества слов в теории групп, играющей фундаментальную роль в различных разделах математики. В самой теории групп эта алгоритмическая проблема была узловой: от ее решения зависело решение других важных вопросов теории групп.
Группой называют каждое множество элементов любой природы (чисел, движений и т. п.), для которых установлено одно прямое действие, называемое обычно перемножением и подчиняющееся закону ассоциативности, и обратное действие — деление. Каждый элемент группы является произведением элементов некоторого их исходного запаса. Последние называются образующими группы и обозначаются различными символами, например буквами алфавита. Результат перемножения образующих а и Ь записывают с помощью этих же букв, поставленных рядом: ab. Требование ассоциативности означает, что для любых элементов группы , ,
( · ) = ( · ).
Образующие группы называются алфавитом, а каждое их произведение — словом. Например, если группа строится из трех образующих а, Ь, с, то такой алфавит позволяет составлять слова а, а– 1, а– 1Ь, ас, abbc и т. п. Перемножать можно не только отдельные буквы алфавита, но и слова. Так, из двух последних слов можно получить два новых слова; acabbc и abbcac (закона коммутативности ab = ba, вообще говоря, в группах нет).
В группах можно разными способами определить равенство слов. Это определение может состоять из одной или конечной системы равенств между словами. Так, если принять, что в группе (а, Ь, с) слова ab и bc равны: ab = bcb, то в каждом слове на место ab можно подставить bcb и наоборот. Благодаря этому можно утверждать, что слова abc и bcbc равны, или тождественны, между собой. Соотношение ab = bcb и ему подобные называют определяющими соотношениями группы.
Проблема тождества слов была поставлена в 1912 году. Теперь ее формулировали так: пусть дана группа с конечным числом образующих и с конечным числом определяющих соотношений. Требуется построить алгоритм, позволяющий для любых двух слов установить, равны они между собой или нет.
В некоторых частных случаях, например, когда задается только одно определяющее соотношение, эту проблему удалось решить. Однако в общем случае вопрос о существовании алгоритма для решения проблемы тождества слов оставался открытым. В 1955 году П. С. Новиков опубликовал названную выше работу, в которой доказал, что существуют группы, для которых нет алгоритма, решающего проблемы тождества слов. Этот результат позволил ученому установить неразрешимость других алгоритмических проблем теории групп: проблемы сопряженности и проблемы изоморфизма. Следуя идеям П. С. Новикова, некоторые математики (в том числе его ученики) решили ряд других алгоритмических проблем и получили значительные результаты.