1. Нормализованные числа и алгоритмы их преобразования

Вещественное число X может быть представлено в двух формах - естественной и нормализованной. В естественной форме у X имеется целая и дробная части, между которыми помещается разделитель (запятая или точка), например, 123,4567. Однако такая запись неудобна для слишком больших или, наоборот, слишком малых чисел. Кроме того, использование такой формы (она называется также "представление числа с фиксированной запятой") в компьютере вызвало бы снижение точности вычислений из-за необходимости приведения в соответствие разрядов обрабатываемых чисел и связанных с этим округлений или могло бы породить ситуацию, называемую переполнением, когда старший разряд числа не умещается в отведенной разрядной сетке. По указанным причинам вещественные числа в компьютере представляются в нормализованном виде (другое название - "представление числа с плавающей запятой"), главным достоинством которой является автоматическое масштабирование числа на каждом этапе обработки, что, с одной стороны, обеспечивает максимально возможную точность вычислений, а с другой - избавляет от необходимости принимать меры по предотвращению переполнения (за исключением достаточно экзотических ситуаций с выходом числа за отведенную разрядную сетку). По сути, это универсальная форма записи всех чисел, кроме определенных как "тип: целые" (например, Integer, Word или Byte в PASCAL'е).

Сначала познакомимся с необходимыми понятиями применительно к десятичной системе счисления.

Число X₁₀ называется нормализованным, если оно представлено в виде

X₁₀ = [+|-] M₁₀· 10 ^{[+|-] k}₁₀

В этой записи M₁₀ называется мантиссой нормализованного числа; значения мантиссы лежат в интервале 0,1 M₁₀<1.>10 называется порядком нормализованного числа - это целое положительное десятичное число. Примеры: - 1234₁₀ = - 0,1234·10⁴; 0,03456₁₀ = 0,3456·10^-1.

Понятие нормализованного числа следует отличать от понятия числа в нормальной форме; данная форма достаточно часто используется при записи чисел в математике, физике, технических дисциплинах и отличается от нормализованного представления тем, что мантисса лежит в интервале 1M₁₀<10,>Б=1,38·10^-23.

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

Аналогично нормализации десятичного числа можно в нормализованной форме представить и число в произвольной системе счисления p:

X_p = [+|-] M_p · p ^{[+|-] k}_p (12)

При этом значения мантиссы лежат в интервале p^-1M_p<1>p). Например, для p = 2:

X₂ = - 101,01₂ = - 0,10101₂ · 2¹¹²

Мантисса располагается в промежутке 0,1₂ M₂<1,>10M₁₀<1.>

Рис.1. Алгоритм нормализации

Подобно задаче о преобразовании целых и дробных чисел, можно поставить задачу о преобразовании представления числа в нормализованной форме в системе счисления p к нормализованному представлению в системе q. Практическое значение такого преобразование состоит в том, что, как было сказано, в компьютере все вещественные числа хранятся и обрабатываются в нормализованном двоичном представлении и, следовательно, при их вводе осуществляется перевод X₁₀ X₂, а при выводе - обратный перевод X₂ X₁₀. Однако прежде, чем обсуждать такой перевод, необходимо рассмотреть, как производится преобразование вещественного числа из естественной формы к нормализованному виду.

При нормализации различаются ситуации X_p>1 и X_p<>-1. В первом случае для нормализации необходимо перемещать разделитель разрядов влево по числу до тех пор, пока не исчезнет целая часть числа, но первая цифра после разделителя будет ненулевой; каждое перемещение разделителя на 1 разряд влево эквивалентно делению числа на p и, чтобы число не менялось, показатель должен возрастать на 1 при каждом сдвиге. Если обозначить эту операцию N (будем называть ее "нормализация влево"), то N [(123,45)₁₀] = 0,12345₁₀·10³; N [(23,4·10⁵)₁₀] = 0,234₁₀·10⁷; N [(1212,2)₃] = 0,12122₃·3¹¹. Аналогично можно ввести операцию "нормализация вправо" (N), обеспечивающая нормализацию чисел меньших p^-1; очевидно, такие числа необходимо умножать на p с одновременным уменьшением показателя на 1 до тех пор, пока первая цифра после разделителя станет ненулевой. Например, N[(0,000101·2^-101)₂] = 0,101·2^-1000; N[(0,000987)₁₀] = 0,987₁₀·10^-3. Общий алгоритм нормализации можно изобразить в виде блок-схемы на рисунке 1.

При практической реализации данного алгоритма не следует забывать, что изменение значения k_p на 1 должно производиться по правилам арифметики системы счисления p. В дальнейшем при необходимости проведения нормализации в ходе каких-либо преобразований будем просто ссылаться на приведенный алгоритм как готовый модуль.

Вернемся к задаче перевода нормализованного числа из одной системы счисления в другую. Пусть, имеется число X_p = [+|-]M_p · p ^[+|-]kp, для которого необходимо найти соответствующее ему X_q = [+|-] M_q · q ^[+|-]kq. Представляется достаточно очевидным, что преобразование не затронет знаков мантиссы и показателя степени. Таким образом, для осуществления преобразования необходимо установить соответствие между (M_p, k_p) и (M_q, k_q). Оно получается достаточно просто, исходя из того, что X_p = X_q, откуда следует:

(13)

Из (13) вытекает, что для осуществления преобразования можно M_p умножить на p^kp, т.е. перейти к естественной форме числа в системе p, перевести его в систему q, а затем нормализовать. Однако в таком варианте действий теряется точность числа и возможно переполнение на промежуточных этапах преобразования. Во избежание этого необходимо чередовать умножение (или деление) на p и нормализацию по основанию q. При этом, поскольку все операции выполняются по правилам арифметики в системы p, будут получены не (M_q ,k_q) в окончательном варианте, а их представления в системе p - обозначим их (M_q)_p и (k_q)_p, которые затем нужно будет перевести в систему q. Различаются также ситуации k_p 0 и k_p<0>p будет менять свой значение на 1; продолжать действия следует до тех пор, пока не выполнится условие k_p= 0. Алгоритм действий для ситуации k_p 0 представлен на рисунке 2.

Рис.2. Алгоритм действий для ситуации k_p 0

Пример 8. Выполнить преобразование X₁₀=16,510 _X2.

Перевод можно осуществить отдельно для целой и дробной части, а затем их объединить - для нас этот результат послужит эталоном для проверки нового алгоритма. Легко получить, что 16₁₀ = 10000₂, а 0,5₁₀ = 0,1₂; следовательно, 16,5₁₀ = 10000,1₂ = (0,100001·2¹⁰¹)₂.

Алгоритм Real_1 начинает функционировать после нормализации исходного числа; для этой цели можно воспользоваться алгоритмом Norma; в результате начальными значениями будут M₁₀ = 0,165; k₁₀ = 2. Результаты операций будем заносить в таблицу:

Шаг	Действие	M=(M2)10	k10	(k2)10
0		0,165	2	0
1	M:=M·10; k10= k10-1	1,65	1	0
2	M:=M/2; k2= k2+1	0,825	1	1
3	M:=M·10; k10= k10-1	8,25	0	1
4	Т.к. k10= 0, MM2	1000,012		1
5	Нормализация по q=2	0,1000012		5
6	(k2)10k2	1000,012		101

Таблица 1. Результаты выполнения операций

Окончательно имеем: X₂ = (0,100001·2¹⁰¹)₂.

Подобным же будет алгоритм преобразования X₁₀X₂ и при k_p<0.>

Последовательность действий при обратном переводе X₂X₁₀ отчасти противоположна только что рассмотренной; для k_p 0 она представлена в виде блок-схемы на рисунке 3. Нормализация в конце (после k=0) производится при необходимости.

Рис.3. Последовательность действий при обратном переводе

Пример 9. Выполнить преобразование: X₂ = (0,11·2¹¹⁰)₂X₁₀.

Для контроля результата: 0,11₂=0,75₁₀; (2¹¹⁰)₂=(2⁶)₁₀=64; следовательно, (0,11·2¹¹⁰)₂=0,75·64=48₁₀. Для преобразования воспользуемся построенным алгоритмом Real_2 (рис. 3). Промежуточные результаты снова будем заносить в таблицу:

Таблица 1. Результаты выполнения операций

Шаг	Действие	M=(M2)10	(k2)10	k10
0	Перевод	0,75	6	0
1	M:=M·2; k=k-1	1,5	5	0
2	M:=M/10; k10= k10+1	0,15	5	1
3	M:=M·2; k = k-1	0,3	4	1
4	M:=M·2; k = k-1	0,6>	3	1
5	M:=M·2; k = k-1	1,2	2	1
6	M:=M/10; k10= k10+1	0,12	2	2
7	M:=M·2; k = k-1	0,24	1	1
8	M:=M·2; k = k-1	0,48	0	2
9	Т.к. k= 0, M = M10	0,48	0	2

Таким образом, получаем: (0,11·2¹¹⁰)₂=0,48·102=48.

Как и в предыдущем преобразовании, алгоритм в случае k_p<0>

2. Абстрактные кибернетические системы. Кибернетический подход к изучению объектов любой природы.

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

Абстрактная кибернетическая система представляет собой множество взаимосвязанных объектов, называемых элементами системы, способных воспринимать, запоминать и перерабатывать информацию, а также обмениваться информацией. Примерами кибернетических систем могут служить разного рода автоматические регуляторы в технике (например, автопилот или регулятор, обеспечивающий поддержание постоянной температуры в помещении), электронные вычислительные машины (ЭВМ), человеческий мозг, биологические популяции, человеческое общество.
Элементы абстрактной кибернетической системы представляют собой объекты любой природы, состояние которых может быть полностью охарактеризовано значениями некоторого множества параметров. Для подавляющего большинства конкретных приложений К. оказывается достаточным рассматривать параметры двух родов. Параметры 1-го рода, называемые непрерывными, способны принимать любые вещественные значения на том или ином интервале, например на интервале от - 1 до 2 или от -¥ до +¥. Параметры 2-го рода, называемые дискретными, принимают конечные множества значений, например значение, равное любой десятичной цифре, значения "да" или "нет" и т.п.

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

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

Организация связей между элементами кибернетической системы носит название структуры этой системы. Различают системы с постоянной и переменной структурой. Изменения структуры задаются в общем случае как функция от состояний всех составляющих систему элементов и от входных сигналов всей системы в целом.

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

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

Разделение кибернетических систем на непрерывные и дискретные является до известной степени условным. Оно определяется глубиной проникновения в предмет, требуемой точностью его изучения, а иногда и удобством использования для целей изучения системы того или иного математического аппарата. Так, например, хорошо известно, что свет имеет дискретную, квантовую природу. Тем не менее, такие параметры, как величина светового потока, уровень освещенности и др. принято обычно характеризовать непрерывными величинами поскольку, постольку обеспечена возможность достаточно плавного их изменения. Другой пример - обычный проволочный реостат. Хотя величина его сопротивления меняется скачкообразно, при достаточной малости этих скачков оказывается возможным и удобным считать изменение непрерывным.

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

Последний пример показывает, что дискретный способ представления величин является универсальным способом, ибо имея в виду недостижимость абсолютной точности измерений, любые непрерывные величины сводятся в конечном счете к дискретным. Обратное сведение для дискретных величин, принимающих небольшое число различных значений, не может привести к удовлетворительным (с точки зрения точности представления) результатам и поэтому на практике не употребляется. Таким образом, дискретный способ представления величины является в определённом смысле более общим, чем непрерывный.

Разделение кибернетических систем на непрерывные и дискретные имеет большое значение с точки зрения используемого для их изучения математического аппарата. Для непрерывных систем таким аппаратом является обычно теория систем? обыкновенных дифференциальных уравнений, для дискретных систем - алгоритмов теория и автоматов теория. Ещё одной базовой математической теорией, используемой как в случае дискретных, так и в случае непрерывных систем (и развивающейся соответственно в двух аспектах), является информации теория.

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

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

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

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

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

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

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

"Запоминание" информации в кибернетических системах может производиться двумя основными способами - либо за счет изменения состояний элементов системы, либо за счет изменения структуры системы (возможен, разумеется, смешанный вариант). Между этими двумя видами "памяти" по существу нет принципиальных различий. В большинстве случаев это различие зависит лишь от принятого подхода к описанию системы. Например, одна из современных теорий объясняет долговременную память человека изменениями проводимости синаптических контактов, т. е. связей между отдельными составляющими мозг нейронами. Если в качестве элементов, составляющих мозг, рассматриваются лишь сами нейроны, то изменение синаптических контактов следует рассматривать как изменение структуры мозга. Если же наряду с нейронами в число составляющих мозг элементов включить и все синаптические контакты (независимо от степени их проводимости), то рассматриваемое явление сведется к изменению состояния элементов при неизменной структуре системы.

Подходы к измерению количества информации.

Термодинамическая мера.

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

Пусть дана термодинамическая система (процесс) S, и Н₀, Н₁ – термодинамические энтропии системы S в начальном (равновесном) и конечном состояниях термодинамического процесса, соответственно. Тогда термодинамическая мера информации (негэнтропия) определяется формулой:

Н(Н₀,Н₁)=Н₀ — Н₁.

Эта формула универсальна для любых термодинамических систем. Уменьшение Н(Н₀,Н₁) свидетельствует о приближении термодинамической системы S к состоянии статического равновесия (при данных доступных ей ресурсах), а увеличение - об удалении.

Поставим некоторый вопрос о состоянии некоторой термодинамической системы. Пусть до начала процесса можно дать p1 равновероятных ответов на этот вопрос (ни один из которых не является предпочтительным другому), а после окончания процесса - p2 ответов. Изменение информации при этом:

D I = k ln(p1 / p2) = k (ln p1 — ln p2 ).

Если p1 > p2 (D I >0) - прирост информации, т.е. сведения о системе стали более определёнными, а при p1

Пример. Предположим, что имеется термодинамическая система - газ в объёме 10 (м³), который расширяется до объёма 20 (м³). Нас интересует вопрос о координате некоторой молекулы газа. В начале мы знали ответ на вопрос и поэтому p1=1 (ln p1=0). Число ответов было пропорционально [ln 10]. После поднятия заслонки мы знаем координату, микросостояние, т.е. изменение информации о состоянии системы равно D I=-k ln(20/10)=-k ln2 (нат). Это известное в термодинамике выражение для прироста энтропии в расчёте на одну молекулу и оно подтверждает второе начало термодинамики. Энтропия - мера недостатка информации о микросостоянии статической системы.

Величина D I может быть интерпретирована как количество информации, необходимой для перехода от одного уровня организации системы к другой (при D I>0 - более высокой, а при D I<0>

Термодинамическая мера (энтропия) применима к системам, находящимся в тепловом равновесии. Для систем, далёких от теплового равновесия, например, живых биосистем, мера - энтропия - менее подходящая.

Понятие энтропии впервые было введено Клаузиусом как мера необратимого рассеяния энергии. Для обратимых (квазиравновесных) процессов оно было определено так:

,

где ΔS — изменение энтропии, ΔQ — изменение теплоты, T — абсолютная термодинамическая температура.

В дифференциальной форме энтропия представляется как:

и, в отличие от первого, оно применимо не только к изотермическим процессам.

Интегральная форма энтропии для обратимых (квазиравновесных) процессов имеет вид:

,

где SA и SB — энтропия начального (A) и конечного (B) состояния соответственно.

Несмотря на то, что энтропия выражается через процессы, она является функцией состояния, то есть каждому состоянию соответствует определённое её значение. Однако, как видно из формул, она определена с точностью до константы, и выбор состояния с нулевым значением условен. Основываясь на третьем начале термодинамики, за нулевое значение энтропии принимают таковое у системы с температурой, равной абсолютному нулю.

Для необратимых процессов выполняется неравенство (следующее из неравенства Клаузиуса):

,

из которого следует закон неубывания энтропии.

2. Этические аспекты информатики.

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

Число компьютерных преступлений растет, также увеличиваются масштабы компьютерных злоупотреблений. Умышленные компьютерные преступления составляют заметную часть преступлений, но злоупотреблений компьютерами и ошибок еще больше.

Основной причиной потерь, связанных с компьютерами, является недостаточная образованность в области безопасности.

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

Цель информационной безопасности - обезопасить ценности системы, защитить и гарантировать точность и целостность информации и минимизировать разрушения, которые могут иметь место, если информация будет модифицирована или разрушена.

На практике важнейшими являются три аспекта информационной безопасности:

• доступность (возможность за разумное время получить требуемую информационную услугу);

• целостность (ее защищенность от разрушения и несанкционированного изменения);

• конфиденциальность (защита от несанкционированного прочтения).

Кроме того, использование информационных систем должно производиться в соответствии с существующим законодательством.

Формирование режима информационной безопасности - проблема комплексная. Меры по ее решению можно разделить на четыре уровня:

• законодательный (законы, нормативные акты, стандарты и т.п.);

• административный (действия общего характера, предпринимаемые руководством организации);

• процедурный (конкретные меры безопасности, имеющие дело с людьми);

• программно-технический (конкретные технические меры).

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

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

Этика - система норм нравственного поведения человека.

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

Ярким примером особой психологической атмосферы в среде информатиков является расширяющееся международное движение программистов, предоставляющих созданные ими программные средства для свободного распространения.

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

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

Не следует декларировать отсутствие законопослушности в сфере профессиональной деятельности (равно как и ни в какой другой). Бравада типа "воровал программы и буду воровать" не может быть оправдана недостаточностью финансирования. Задумайтесь: ведь подавляющее большинство тех, кто занимается незаконным копированием программного обеспечения, никогда не позволит себе украсть компьютер.

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

НЕСКОЛЬКО ПРАВИЛ ПРИ РАБОТЕ В СЕТЯХ

1. Не делайте сами того, чего вы не хотели бы, чтобы делали другие.

2. Не забывайте об авторских правах на копируемые вами и получаемые от вас материалы сети.

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

4. Пишите кратко, грамотно и аккуратно.

5. Используйте только стандартные текстовые символы — чем проще, тем лучше.

6. Заботьтесь о секретности вашей информации. Не пишите в электронном письме ничего такого, чего вы не написали бы на почтовой открытке.

7. Помните, что если вы отправили письмо, вернуть его практически невозможно.

8. Не используйте в телеконференциях прямую рекламу.

9. Не цитируйте письмо другого человека, пока вы не получили его разрешение на это.

10. Будьте предельно вежливы.

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

12. Не распространяйте в сети файлы с нецензурной информацией и др.

Итог:

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

Введение в теорию алгоритмов

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

Термин «алгоритм» происходит от имени ученого средневекового Востока Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Он жил приблизительно с 783 по 850 год. Им было написано первое руководство по арифметике, основанное на позиционном принципе. Это руководство сыграло очень роль в развитии арифметики. Кроме того, сохранились его трактаты об алгебре и о календаре. Мухаммед написал знаменитую книгу «Китаб аль-джебр валь-мукабала» – «Книга о восстановлении и противопоставлении» (посвящена решению линейных и квадратных уравнений), от названия которой произошло слово «алгебра». В латинских переводах с арабского арифметического трактата ал-Хорезми его имя транскрибировалось как algorismus. Откуда и пошло слово «алгоритм» – сначала для обозначения алгоритмов цифровых вычислений десятичной позиционной арифметики, а затем для обозначения произвольных процессов, в которых искомые величины решаемых задач находятся последовательно из исходных данных по определенным правилам.

Вплоть до 30-х годов ХХ века понятие алгоритма оставалось интуитивно понятным, имело скорее методологическое, а не математическое значение. Известно много ярких алгоритмов, таких, например, как алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел или многочленов, алгоритм Гаусса решения системы линейных уравнений и др. Эти проблемы были решены путем указания конкретных разрешающих процедур. Для получения результатов такого типа достаточно интуитивного понятия алгоритма.

Алгоритм – это точное и понятное предписание исполнителю о том, какие действия и в каком порядке нужно выполнить, чтобы решить любую задачу из класса однотипных задач.

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

Свойства алгоритмов

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

2. Понятность. Алгоритм должен быть сформулирован на языке, понятном исполнителю, т. е. не должен содержать действий, не входящих в систему команд исполнителя (СКИ – совокупность всех команд, которые может выполнять данный исполнитель).

3. Массовость. Алгоритм должен представлять собой единый метод решения бесконечной серии однотипных задач.

4. Результативность. Исполнение алгоритма за конечное число шагов должно приводить к искомому ответу – решению задачи либо к информации о том, что задача решения не имеет.

5. Дискретность. Шаги алгоритма должны быть дискретны, т. е. каждый шаг должен быть четко отделен от другого, за исполнением каждого шага, кроме последнего, должен однозначно определяться следующий и между этими шагами не должно быть других действий.

Предпосылки возникновения необходимости уточнения (формализации) понятия алгоритма и возникновения теории алгоритмов

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

Но к началу ХХ века стали усложняться объекты, с которыми оперировали алгоритмы. Появилась необходимость выполнять операции над векторами, матрицами, множествами, функциями и т. п. Возникла масса вопросов: одни из них были связаны с трактовкой элементарности тех или иных шагов (например, можно ли считать взятие интеграла таким шагом?), другие – с оценкой конечности и однозначности алгоритма.

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

Структура современной теории алгоритмов

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

Поиск теоретических моделей алгоритмов происходил в трех направлениях, которые определили три основных класса таких моделей, три способа уточнения (формализации) понятия алгоритма:

1. Теория рекурсивных функций – основана на арифметизации алгоритма. Это направление является исторически первым уточнением понятия алгоритма, т. е. первой универсальной алгоритмической моделью. Используя эту модель, австрийский математик К. Гедель доказал свою знаменитую теорему о принципиальной неполноте формальных теорий.

2. Абстрактные машины (например, машина Поста и машина Тьюринга). Идея проста. Для того чтобы алгоритм понимался однозначно, а каждый его шаг можно было считать элементарным и выполнимым, он должен быть представлен так, чтобы его могла выполнять машина. Чем проще структура машины и ее действия, тем убедительнее выглядит утверждение, что ее работа и есть выполнение некоторого алгоритма. При этом структура машины должна быть универсальной, такой, чтобы на ней можно было выполнить любой алгоритм.

3. Нормальные алгоритмы Маркова. Это направление близко к абстрактным машинам, но не использует машинных механизмов.

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

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

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

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

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

Установить нижнюю оценку – значит доказать, что никакой алгоритм вычисления не имеет сложности меньшей, чем заданная граница. Для получения результатов такого типа необходима точная фиксация рассматриваемой алгоритмической модели, и такие результаты получены только в очень жестких вычислительных моделях. В связи с этим получила развитие проблематика получения «относительных» нижних оценок, так называемая теория NP-полноты, связанная с труднорешаемостью переборных задач.

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

Абстрактные машины

Чтобы формализовать понятие алгоритма, надо:

1) формализовать понятие объекта;

2) формализовать действия над этим объектом.

Формализация объекта

Объекты могут быть различными: числа, слова, фигуры и так далее, но во всех случаях можно считать, что алгоритм имеет дело не с объектами реального мира, а с их изображениями. Например, когда алгоритм сложения работает с числами 23 и 56, можно считать, что алгоритм работает с объектом, который изображен пятью знаками: 23+56. Результат работы этого алгоритма тоже изображение, состоящее из двух знаков: 79. При этом мы исходим из того, что у нас в распоряжении имеется набор из 11 различных знаков: {0,1,2,3,4,5,6,7,8,9,+}. Эти знаки мы будем называть буквами, а весь набор – алфавитом.

Буквами могут быть любые знаки, но алфавит должен быть конечным и все буквы в нем должны быть различны. Любая конечная последовательность букв алфавита называется словом. Количество букв в слове – длина слова.

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

Слово, к которому применяется алгоритм, называется входным словом. Слово, которое получается в результате, – выходным словом.

Совокупность слов, к которым может быть применен алгоритм, называется областью применимости алгоритма.

Любой алфавит можно заменить другим, при этом каждой букве из первого алфавита нужно поставить в соответствие ее код, представляющий собой слово во втором алфавите.

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

1-е направление – рекурсивные функции;

2-е направление – абстрактные машины;

3-е направление – нормальные алгоритмы Маркова.

Определение. Универсальной алгоритмической моделью называется такая модель, позволяющая реализовать любой алгоритм.

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

Из истории...

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

Эта идея привела к концепции абстрактной машины как универсальной алгоритмической модели. Она была выдвинута Аланом Тьюрингом и Эмилем Постом практически одновременно (в 1936–1937 годах).

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

Свыше пятидесяти лет назад, в 1935 году, Э. Пост опубликовал в «Журнале символической логики» статью «Финитные комбинаторные процессы, формулировка 1». В этой статье и появившейся одновременно в «Трудах Лондонского математического общества» статье английского математика А. М. Тьюринга «О вычислимых числах с приложением к проблеме решения» были даны первые уточнения понятия «алгоритм» – одного из центральных понятий математической логики и кибернетики, играющего важную роль в вопросах автоматизации, а поэтому и во всей жизни общества.

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

Ее суть:

• Вся информация, которая должна быть обработана по существу, должна быть обработана по форме, т. е. с помощью двоичного алфавита.

• Вся информация должна обрабатываться побуквенно.

При этом Пост доказал, что его система обладает алгоритмической полнотой. Его идеи были настолько фундаментальны, что к ним вернулись через 30 лет. В 1967 году профессор Успенский пересказывает их с новых позиций. Он вводит термин машины Поста. Машина Поста – абстрактная машина, которая работает по алгоритмам, разработанным человеком.

Алан Тьюринг – математик и программист, предложивший стек.

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

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

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

В 1970 году машина Поста была разработана в металле в Симферопольском университете. А машина Тьюринга была построена в металле в 1973 году в Малой Крымской Академии наук.

Машина Поста

Машина Поста – абстрактная машина, обрабатывающая слова в алфавите А={_, V}. Один из символов двоичного алфавита – метка «V», другой – пустота «_» (отсутствие метки).

Устройство машины Поста

Машина Поста состоит из бесконечной в оба конца ленты, разделенной на ячейки одинакового размера. В каждую ячейку ленты заносится один из символов внешнего алфавита.

Вдоль ленты движется каретка (считывающая и записывающая головка).

Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной ячейки ленты; говорят, что каретка обозревает эту ячейку. А такая ячейка называется текущей или обозреваемой.

За единицу времени, которая называется тактом, каретка может сдвинуться на одну ячейку влево или вправо. Кроме того, каретка может также распознать, стоит или нет метка в обозреваемой ею ячейке, может заносить метку в пустую ячейку и может удалять метку из отмеченной ячейки.

Команды, по которым каретка должна занести метку в отмеченную секцию или удалить метку из пустой секции, являются недопустимыми.

Команды машины Поста

Формат команды: n K m, где

n – номер текущей команды,

K – команда из системы команд машины Поста,

m – отсылка – номер команды, которая будет выполняться следующей.

Система команд машины Поста:

1) a → b

Сдвиг каретки вправо, содержимое ленты не меняется.

2) a ← b

Сдвиг каретки влево, содержимое ленты не меняется.

3) a V b

В обозреваемую ячейку ставится метка «V». Выполнение этой команды возможно только в том случае, если обозреваемая ячейка пустая, в противном случае команда считается невыполнимой.

4) a ↕ b

Каретка стирает метку в обозреваемой ячейке. Выполнение этой команды возможно только в том случае, если обозреваемая ячейка содержит метку, в противном случае команда считается невыполнимой.

5) a ? b1, b2

Команда передачи. Проверяется содержимое текущей ячейки, если метки нет, то происходит передача управления команде с номером b1, иначе, если метка есть, – команде с номером b2. Содержимое ленты не меняется.

6) a ! [а]

Команда останова машины. Содержимое ленты не меняется. У команды остановки отсылка не обязательна.

Последовательность команд из системы команд – программа, если

1) на n-ом месте этой программы будет стоять команда с номером n,

2) отсылке m соответствует реальная команда в программе.

Порядок работы машины Поста

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

Работа машины на основании заданной программы происходит следующим образом. Машина приводится в начальное состояние и приступает к выполнению первой команды программы. Эта команда выполняется за один такт, после чего машина приступает к выполнению той команды, номер которой равен отсылке первой команды. Эта команда также выполняется за один такт, после чего начинается выполнение той команды, номер команды которой равен отсылке выполненной команды и так далее, до тех пор, пока не будет выполнена команда останова машины.

Будем считать, что в начальном и в конечном состояниях каретка находится над крайней левой меткой.

Если в ходе выполнения программы машина дойдет до выполнения команды остановки, то программа в этом случае считается выполненной, и машина является применимой к входному слову.

Если в ходе выполнения программы машина не дойдет до выполнения ни одной из команд останова, то выполнение программы при этом никогда не прекращается, машина никогда не останавливается – процесс работы машины происходит бесконечно. В этом случае говорят, что машина не применима к входному слову.

Пример. Составить программу машины Поста сложения двух чисел, разделенных одним или более пробелами.

Начальная конфигурация:

Заключительная конфигурация:

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

Программа	Комментарии
1 ↕ 2	удалить первую метку
2 → 3	цикл сдвига вправо до первой ячейки без метки
3 ? 4, 2
4 V 5	постановка метки в свободную ячейку
5 → 6	если справа ячейка пуста, то переход к 7-ой команде, в противном случае к – 10-ой
6 ? 7, 10
7 ← 8	цикл сдвига влево до первой ячейки без метки
8 ? 9, 7
9 → 1	переход на крайнюю левую метку
10 ← 11	сумма найдена, перевод каретки в начало выходного слова
11 ? 12, 10
12 → 13
13 ! 13

Трассировка приведенного алгоритма (будем отображать содержимое только используемой части ленты, над стрелкой обозначим номер выполняемой команды):

Машина Тьюринга

Машина Тьюринга – абстрактная машина, обрабатывающая слова в произвольном внешнем алфавите А={а₀, а₁, …, a_n}. Внешний алфавит для каждой задачи выбирается свой, но один символ присутствует в любом алфавите – это пустой символ («пробел»), а₀= «_».

Устройство машины Тьюринга

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

Вдоль ленты движется каретка (считывающая и записывающая головка).

Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной ячейки ленты; говорят, что каретка обозревает эту ячейку. А такая ячейка называется текущей или обозреваемой.

В каждый конкретный момент времени машина находится в одном из внутренних состояний и обозревает ровно одну ячейку. Множество всех внутренних состояний образует алфавит внутренних состояний машины Тьюринга Q={q₀, q₁, …,q_m}. Состояние q₁ – начальное состояние, а состояние q₀ – конечное состояние; присутствуют в любой машине Тьюринга. В начальном и конечном состояниях каретка находится над крайним левым значащим символом.

Команды машины Тьюринга

Формат команды: a_i q_j → a_i΄ K q_j΄, где

a_i, a_i΄ – символы внешнего алфавита А,

q_j, q_j΄– символы алфавита внутренних состояний Q,

K – команда сдвига каретки: L – сдвиг каретки влево, R – сдвиг каретки вправо, E – отсутствие сдвига каретки.

Последовательность команд – программа машины Тьюринга.

Порядок работы машины Тьюринга

Работа машины Тьюринга состоит из тактов. На каждом такте выполняется одна команда машины Тьюринга. Выбор команды определяется обозреваемым символом и тем внутренним состоянием, в котором находится машина в данный момент времени. Таким образом, если обозревается символ a_i и машина находится во внутреннем состоянии q_j, то машина выполняет команду a_i q_j → a_i΄ K q_j΄, в ходе чего выполняются следующие действия:

1) символ a_i в обозреваемой ячейке заменяется на символ a_i΄;

2) каретка сдвигается в соответствии с командой К;

3) машина переводится во внутреннее состояние q_j΄;

После выполнения команды происходит переход к следующему такту.

Действия машины прекращаются после выполнения команды останова.

Команда останова – это команда вида a_i q_j → a_i Е q_j, т. е. команда, которая не меняет обозреваемого символа, не сдвигает каретку, не меняет внутреннего состояния машины.

Все команды останова содержатся в заключительном состоянии q₀.

Если в ходе выполнения программы машина дойдет до выполнения команды останова, то программа в этом случае считается выполненной, и машина является применимой к входному слову.

Если в ходе выполнения программы машина не дойдет до выполнения ни одной из команд останова, то выполнение программы при этом никогда не прекращается, машина никогда не останавливается – процесс работы машины происходит бесконечно. В этом случае говорят, что машина не применима к входному слову.

Программу машины Тьюринга удобно отображать в виде таблицы. Например, команда a_i q_j → a_i΄ K q_j΄ будет отображаться следующим образом:

А Q	q0	q1	…	qj	…	qm
a0
a1
…
ai				ai΄ K qj΄
…
an

Пример. Составить программу машины Тьюринга сложения двух чисел в десятичной системе счисления.

Внешний алфавит: А={_,0,1,2,3,4,5,6,7,8,9}.

Пример начальной конфигурации:

Заключительная конфигурация:

Для решения задачи будем в цикле вычитать единицу из второго числа и прибавлять единицу к первому до тех пор, пока не закончится второе число.

А Q	q0	q1	q2	q3	q4	q5	q6	q7	q8
_	_Eq0	_Rq2	_Lq3	_Rq6	_Lq5	1Rq1	_Lq7	_Lq7	_Rq0
0	0Eq0	0Rq1	0Rq2	9Lq3	0Lq4	1Rq1		0Lq8	0Lq8
1	1Eq0	1Rq1	1Rq2	0Lq4	1Lq4	2Rq1		1Lq8	1Lq8
2	2Eq0	2Rq1	2Rq2	1Lq4	2Lq4	3Rq1		2Lq8	2Lq8
3	3Eq0	3Rq1	3Rq2	2Lq4	3Lq4	4Rq1		3Lq8	3Lq8
4	4Eq0	4Rq1	4Rq2	3Lq4	4Lq4	5Rq1		4Lq8	4Lq8
5	5Eq0	5Rq1	5Rq2	4Lq4	5Lq4	6Rq1		5Lq8	5Lq8
6	6Eq0	6Rq1	6Rq2	5Lq4	6Lq4	7Rq1		6Lq8	6Lq8
7	7Eq0	7Rq1	7Rq2	6Lq4	7Lq4	8Rq1		7Lq8	7Lq8
8	8Eq0	8Rq1	8Rq2	7Lq4	8Lq4	9Rq1		8Lq8	8Lq8
9	9Eq0	9Rq1	9Rq2	8Lq4	9Lq4	0Lq5	_Rq6	9Lq8	9Lq8

Трассировка приведенного алгоритма (будем отображать текущее внутреннее состояние и содержимое только используемой части ленты):

стоп

Как видно из примера, каждое внутреннее состояние отвечает за определенный шаг алгоритма:

q₁ – проход в конец первого числа;

q₂ – проход слева направо в конец второго числа;

q₃ – вычитание единицы из второго числа;

q₄ – проход справа налево в конец первого числа;

q₅ – прибавление единицы к первому числу;

q₆ – удаление второго числа после окончания сложения;

q₇ – проход справа налево по пустым ячейкам в конец первого числа;

q₈ – проход справа налево в начало первого числа;

q₀ – завершение работы алгоритма (содержит точки останова).

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