Профессор Калабрийского университета (Италия) Ярослав Сергеев несколько лет назад предложил использовать новый математический символ — гроссван, который обозначает самое большое натуральное число. Введение этого символа позволяет решить некоторые неразрешимые с точки зрения классических представлений о бесконечности вычислительные задачи. Однако не менее ценен он и для компьютерной науки. Математическая модель, предложенная Сергеевым, хорошо переносится на компьютерную платформу — в ней значение гроссвана всегда известно: для байта — это 256, для целого типа со знаком, состоящего из двух байтов, — это 32768. Фактически количество байтов, выбранное разработчиком системы для указанного типа данных, и определяет значение гроссвана для него.

РАЗРАБОТАННЫЙ ПРОФЕССОРОМ Сергеевым калькулятор позволяет работать с бесконечно большими и бесконечно малыми числами

РАЗРАБОТАННЫЙ ПРОФЕССОРОМ Сергеевым калькулятор позволяет работать с бесконечно большими и бесконечно малыми числами

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

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

Еще одним применением аппарата натуральной бесконечности в теории вычислений является развитие теории сложности и добавление нового типа машин Тьюринга. В первоначальной концепции идеальный исполнитель алгоритмов имел бесконечную ленту вывода и бесконечное время, что и создавало проблемы. При добавлении определения реализуемой машины Тьюринга, в которой гроссван ограничивает выходную последовательность символов и время ее работы, становится очевидно, что такая машина гарантированно остановится либо по достижении конца алгоритма, либо по исчерпании ресурсов времени или ленты. Второй вариант останова существенно отличает «натуральную» машину Тьюринга от идеальной.

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

Поделитесь материалом с коллегами и друзьями

Купить номер с этой статьей в PDF