ГЛАВА VIII. ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ КАК ЭВРИСТИЧЕСКОЕ СРЕДСТВО ИССЛЕДОВАНИЯ

1. Введение

В последние годы благодаря развитию быстродействующих электронных вычислительных машин стало возможным значительное количество интересных эвристических математических исследований. В недалеком будущем можно ожидать еще большего количества таких исследований, главным образом в математической физике, но также в комбинаторном анализе и в теории чисел. Изучение частных случаев всегда было полезно, и экспериментальные результаты играли важную роль, особенно в теории чисел; это подчеркивал сам Гаусс. Сейчас в нашем распоряжении имеются средства для чрезвычайного расширения этого экспериментального базиса, причем время, нужное для проведения вычислений, неизмеримо уменьшилось по сравнению с временем, нужным для ручного счета. В следующих пунктах мы дадим как некоторые примеры уже проделанной работы, так и довольно произвольные иллюстрации возможных в будущем задач такого рода.

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

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

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

В некоторых случаях, задав можно a priori получить в терминах оценку такую, что для Эта оценка будет наиболее чувствительной к изменению Такая априорная оценка не может быть дана для всех рекурсивных функций. Это следует из результатов Гёделя. Во многих практических случаях, однако, можно ожидать результата типа