SETI@home

В другом знаменитом проекте распределенных вычислений SETI@home (SETI - Search for Extraterrestrial Intelligence at Home), в котором анализируется на наличие сигналов искусственного происхождения записанный с помощью радиотелескопа в Аресибо космический «радиоэфир», количество подключенных компьютеров составляет около 300 тысяч с общей скоростью выполнения операций более 700 терафлоп.

2 Модели вычислений

2.1 Понятие модели вычислений

Неформальное понятие модели вычислений предполагает задание языка программирования вместе с его операционной семантикой, т.е. объяснением того, каким образом программе сопоставляется процесс вычислений.

Процесс вычислений, развиваясь во времени (которое дискретно), потребляет различные (разнородные) ресурсы. Предполагается, что величина потребленного к данному моменту ресурса измеряется натуральными числами и не может быть бесконечной, т.е. бесконечный ресурс требуется только для никогда не заканчивающегося процесса. Удобно (хотя не столь существенно) также считать, что каждый никогда не заканчивающийся процесс потребляет бесконечное количество каждого ресурса, т.е.

Ресурс < ∞ ⇔ процесс вычисления заканчивается.

Основные (но не единственные) ресурсы – время и память. Но для каждой модели вычислений они свои.

Модель вычислений можно использовать для оценки трудоемкости алгоритмов. Для этого реализуют алгоритм в виде программы p на языке программирования данной модели, после чего выбирают ресурс r (из числа определенных в модели) и ищут верхние оценки f(n) на величину затрат.

Основное противоречие в данном случае: для реальных языков программирования трудно получить точные оценки затрат. Поэтому обычно используют один из следующих выходов:

· Численный эксперимент. Является машинно зависимым, поэтому результаты быстро устаревают.

· Огрубления в определении ресурса. Например, в качестве времени для C – подсчет только количества выполняемых арифметических операций (или только сравнений). Данный вариант является не вполне честным.

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

2.2 Модели Тьюринга

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

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

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

Вычислительные возможности машин Тьюринга достаточно хорошо изучены. Их качественная характеристика состоит в описании класса всех функций, вычислимых на машинах Тьюринга. Речь идет о частичных словарных функциях f: Σ ^∗ → Σ ^∗ , где Σ ^∗ – множество всех слов в конечном алфавите Σ, а термин «частичная функция» означает, что значение функции f(v) для некоторых слов v ∈ Σ ^∗ может оказаться неопределенным. Результат сравнительного изучения запасов вычислимых словарных функций для различных моделей вычислений может быть сформулирован в виде следующего неформального утверждения:

Тезис Тьюринга (неформальный): Каждую вычислимую (программой какого угодно языка программирования) частичную функцию типа Σ ^∗ → Σ ^∗ можно вычислить на подходящей машине Тьюринга.

Неформальность Тезиса Тьюринга состоит в том, что он не может быть полностью обоснован математическими средствами (доказан как математическая теорема).

2.3 λ -исчисление

λ -исчисление исходит из следующих основных идей:

Функция понимается не как преобразование одного статического множества в другое, а как преобразования, или же правила действий, перерабатывающие одни такие функции-преобразования в другие. Иначе говоря, в нашем распоряжении имеются некоторые объекты, являющиеся одновременно и функциями, и объектами, к которым эти функции применяются, причем мы изначально никак не ограничиваем возможности применения одних таких функций к другим, то есть, в принципе мы не запрещаем применение любого объекта f к любому объекту g. Результат такого применения, обозначаемый fg, также является объектом-функцией. В рамках этих представлений вполне правомерно и осмысленно применение произвольной функции f к самой себе с получением объекта ff, что невозможно при стандартной теоретико-множественной интерпретации функций множествами пар. Эта ситуация в принципе встречается, например, такими объектами могут быть некоторые тексты программ или процедур; одна программа вполне может быть применена к другой программе. Другим примером является использование в ряде современных языков программирования процедур в качестве аргументов процедур (в том числе, и самих себя).

Эта идея получила реализацию в виде операции аппликации. Аппликация означает применение или вызов функции по отношению к заданному значению. Её обычно обозначают f a, где f — функция, а a — значение. Это соответствует общепринятой в математике записи f (a), которая тоже иногда используется, однако для λ -исчисления важно то, что f трактуется как алгоритм, вычисляющий результат по заданному входному значению. В этом смысле аппликация f к a может рассматриваться двояко: как результат применения f к a, или же как процесс вычисления.

Еще одной идеей, лежащей в основе λ -исчисления, является так называемая λ -абстракция. Пусть мы построили некоторое выражение из объектов a = a₁, …, a_k и переменной x. С одной стороны, при заданном значении x мы вправе рассматривать это выражение как вполне определенный объект, получающийся в результате соответствующих преобразований этого x. С другой стороны, мы можем считать это выражение правилом, которое при своем применении к произвольному объекту x выдает . На этом различии в истолковании выражений, содержащих переменные, и основано понятие λ -абстракции. Мы считаем, что объект b (в данном случае, его можно рассматривать как правило) такой, что для любого x выполнено получается из в результате λ -абстракции и обозначается . Следующий простой пример иллюстрирует разницу между выражениями xx и : применив их к a, мы получим соответственно (xx)a и aa.

Механизм λ -абстракции и λ -аппликации приводит к еще одной операции λ -исчисления, называемой β -редукцией. Естественно считать, что если – функция, выдающая по кажому x значение f(x), то результат ее применения к A есть f(A), т.е. что . Такое преобразование называется β -контрадикцией. Если один тем получается из другого путем конечного числа β -контрадикций, тогда считается, что он получен путем β -редукции из этого терма.

Благодаря описанным выше механизмам λ -исчисление обладает богатыми выразительными возможностями и, в частности, позволяет в определенном смысле выражать любые вычислимые функции, обладая полнотой по Тьюрингу и служа, фактически, языком программирования. В частности, было доказано, что каждая частично рекурсивная функция является вычислимой и вычисляется некоторым λ -термом. Также, задав семантику λ -исчисления, а именно построив нетривиальное множество S, элементы которого можно было бы естественно отождествлять с функциями из S в S, причем так, чтобы различные элементы задавали бы различные функции (что было сделано Ю.Л. Ершовым и Д. Скоттом), получается модель вычислений, которая может быть использована, например, для доказательства вычислимости алгоритмов.