Подключение библиотек подпрограмм 3 страница

Для понимания вероятностного подхода лучше всего рассмотреть несложный пример, связанный с бросанием правильной иг­ральной кости, имеющей N граней (наиболее распространенным является случай шестигранной кости: N = 6). Результатом данного опыта может быть выпадение грани с одним из следующих знаков: 1, 2,... N.

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

 

, (2.3)

 

а сама функция f является возрастающей, неотрицательной и определенной (в рассматриваемом нами примере) для N = 1, 2,... 6.

Рассмотрим процедуру бросания кости более подробно:

1) готовимся бросить кость; исход опыта неизвестен, т.е. имеется некоторая не­определенность; обозначим ее Н1;

2) кость брошена; информация об исходе данного опыта получена; обозначим количество этой информации через I;

3) обозначим неопределенность данного опыта после его осуществления через H2.

За количество информации, которое получено в ходе осуществления опыта, примем разность неопределенностей “до” и “после” опыта:

(2.4)

 

Очевидно, что в случае, когда получен конкретный результат, имевшаяся неоп­ределенность снята (H2=0), и, таким образом, количество полученной информации совпадает с первоначальной энтропией. Иначе говоря, неопределенность, заклю­ченная в опыте, совпадает с информацией об исходе этого опыта. Заметим, что значение H2 могло быть и не равным нулю, например, в случае, когда в ходе опыта следующей выпала грань со значением, большим трех.

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

 

(2.5)

 

Так, в случае двух бросаний кости с шестью гранями имеем: Х=62=36. Фактически каждый исход Х есть некоторая пара (X1, X2), где Х1 и X2 – соответственно исходы первого и второго бросаний (общее число таких пар – X).

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

(2.6)

 

Из приведенных формул выводится мера Хартли:

 

(2.7)

 

Важным при введении какой-либо величины является вопрос о том, что прини­мать за единицу ее измерения. Очевидно, H будет равно единице при N = 2. Иначе говоря, в качестве единицы измерения информации принимается количество информации, связанное с проведением опыта, состоящего в получении одного из двух равновероятных исходов (примером такого опыта может служить бросание монеты при котором возможны два исхода: “орел”, “решка”). Такая единица количества информации называется бит.

В случае, когда вероятности различных исходов опыта не равновероятны (а имеют вероятности Pi), меру энтропии вычисляют по формуле Шеннона:

(2.8)

 

В качестве примера определим количество информации, связанное с появлением каждого символа в сообщениях, записанных на русском языке. Будем считать, что русский алфавит состоит из 33 букв и знака “пробел” для разделения слов. По формуле (2.7) получаем: Н» 5 бит.

Однако, в словах русского языка (равно как и в словах других языков) различ­ные буквы встречаются неодинаково часто. Для учета данного обстоятельства воспользуемся для подсчета Н вероятностными частотами употребления различных знаков русского алфавита, полученных на основе анализа очень больших по объему текстов. По формуле (2.8) получаем: Н» 4.72 бит. Полученное значе­ние Н, как и можно было предположить, меньше вычисленного ранее. Величина Н, вычисляемая по формуле (2.7), является максимальным количеством информации, которое могло бы приходиться на один знак.

 

2.2.3. Семантическая мера информации

 

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

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

Содержательность события i выражается через функцию меры m(i) – содержательности его отрицания. Оценка содержательности осно­вана на математической логике, в которой логические функции истинно­сти m(i) и ложности m(о) имеют формальное сходство с функциями ве­роятностей события p(i) и антисобытия q(i) в теории вероятностей.

Как и вероятность, содержательность события изменяется в пределах 0?m(i)?1.

Логическое количество информации Inf, сходное со статистическим количеством информации, вычисляется по выражению:

Inf = log2 [1/m(i)] = – log2 m(о)

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

Если информация используется в системах управления, то ее полез­ность целесообразно оценивать по тому эффекту, который она оказывает на результат управления.

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

Мера целесообразности в общем виде может быть аналитически выра­жена в виде соотношения:

(2.8)

где p0и p1– начальная (до получения информации) и конечная (после получения информации) вероятности достижения цели.

Следует различать: существенность самого события; существенность времени совершения события или его наблюдения (рано–поздно–момент); существенность координаты совершения события.

Измерение некоторого параметра Х можно характеризовать несколь­кими функциями величины х: вероятностью р(х), погрешностью измере­ния е(х) и существенностью с(х). Каждой из этих функций можно поста­вить в соответствие определенную меру информации. Мерой Хартли оценивается функция погрешности е при фиксированных значениях функ­ции вероятности (р = const) и существенности (с = const). Мерой Шеннона оценивается функция вероятности (р = var) при фиксированных значениях функций погрешности (е = const) и существенности (с = const). Мера су­щественности относится к ситуации с фиксированными функциями по­грешности (е = const) и вероятности (р = const).

 

2.3. Свойства информации

 

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

Можно привести немало разнообразных свойств информации. Каждая научная дисциплина рассматривает те свойства информации, которые ей наиболее важны. Рассмотрим наиболее важные свойства информации с позиций изучаемой дисциплины.

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

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

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

Доступность информации – мера возможности получить ту или иную информа­цию. На степень доступности информации влияют одновременно как доступность данных, так и доступность адекватных методов для их интерпретации. Отсутствие доступа к данным при наличии адекватных методов обработки данных приводят к одинаковому результату: информация оказывается недоступной. Отсутствие адекват­ных методов для работы с данными во многих случаях приводит к применению неадекватных методов, в результате чего образуется неполная, неадекватная или недостоверная информация.

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

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

· формальная точность, измеряемая значением единицы младшего разряда числа;

· реальная точность, определяемая значением единицы последнего разряда числа, вер­ность которого гарантируется;

· максимальная точность, которую можно получить в конкретных условиях функциони­рования системы;

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

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

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

Своевременность информации означает ее поступление не позже заранее на­значенного момента времени, согласованного со временем решения поставленной задачи.

 

3. Теоретические аспекты обработки информации

 

3.1. Абстрактные автоматы и понятие алгоритма. Программное управление

 

3.1.1. Понятие алгоритма

 

Су­ществует много определений термина “алгоритм”. Например, по определе­нию академика А. Н. Колмогорова, алгоритм или алгорифм – это всякая система вычислений, выполняемых по строго определенным правилам, кото­рая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

В инженерной практике часто используется следующее определение: алгоритм – конечная совокупность точно сформулированных правил ре­шения какой-то задачи.

Само слово “алгоритм” происходит от algorithmi – латинской формы написания имени великого математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами и понима­ли только правила выполнения четырех арифметических действий над многознач­ными числами.

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

1. Обозревая два числа а и b, переходи к следующему пункту.

2. Сравни обозреваемые числа (а равно b, а меньше, больше b) и пере­ходи к следующему пункту.

3. Если а и b равны, то прекрати вычисление: каждое из чисел дает ис­комый результат. Если числа не равны, то переходи к следующему пункту.

4. Если первое число меньше второго, то переставь их местами и пере­ходи к следующему пункту.

5. Вычти второе число из первого и сделай обозрение двух чисел: вы­читаемого и остатка; переходи к п. 2.

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

Характеристиками алгоритма являются:

· детерминированность, определяющая однозначность результата решения задачи при заданных исходных данных;

· дискретность определяемого алгоритмом процесса, означающая расчлененность его на отдельные элементарные шаги;

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

Эти характеристики не дают точного описания алгоритма, а лишь объ­ясняют смысл этого термина в математике.

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

Детерминированный алгоритм – алгоритм, имеющий место при чет­кой и ясной системе правил и указаний и однозначных действиях.

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

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

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

Таким образом, алгоритм дает возможность ответить на вопрос “что делать?” в каждый момент времени, однако создать алгоритм не всегда возможно.

Численный алгоритм – алгоритм, соответствующий решению постав­ленной задачи с помощью арифметических действий.

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

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

 

3.1.2. Формализация алгоритма. Абстрактные автоматы

 

Алгоритмы являются объектом систематического исследования пограничной между математикой и информатикой научной дисциплины, примыкающей к математической логике, – теории алгоритмов.

Как фундаментальное научное понятие алгоритм требует более обстоятельного изучения. Оно невозмож­но без уточнения понятия “алгоритм”, более строгого его описания или, как еще говорят, без его формализации.

Одним из подходов к формализации понятия “алгоритм” является теория конечных и бесконечных автоматов.

Рассмотрим формализацию понятия алгоритма в теории автоматов на примере машин Поста, Тьюринга, а также нормальных алгоритмов Маркова.

Машина Поста. Абстрактные (т.е. существующие не реально, а лишь в воображении) машины Поста и Тьюринга, предназначенные для доказательств различных утверждений о свойствах программ для них, были предложены независимо друг от друга (и прак­тически одновременно) в 1936 г. американским математиком Эмилем Постом и английским математиком Алланом Тьюрингом. Эти машины представляют собой универсальных исполнителей, являющихся полностью детерминированными, позволяющих “вводить” начальные данные и после выполнения программ “читать” результат. Машина Поста менее популярна, хотя она значительно проще машины Тьюринга.

Абстрактная машина Поста представляет собой бесконечную ленту, разделен­ную на одинаковые клетки, каждая из которых может быть либо пустой, либо заполненной меткой “V”, и головку, которая может перемещаться вдоль ленты на одну клетку вправо или влево, наносить в клетку ленты метку, если этой метки там ранее не было, стирать метку, если она была, или проверять наличие в клетке метки. Информация о заполненных метками клетках ленты характеризует состояние ленты, которое может меняться в процессе работы машины. В каждый момент времени головка (“–”) находится над одной из клеток ленты и, как говорят, обозре­вает ее. Информация о местоположения головки вместе с состоянием ленты харак­теризует состояние машины Поста (рис. 3.1).

 

Рис. 3.1. Абстрактная машина Поста

 

Команда машины Поста имеет следующую структуру:

n Km,

где n – порядковый номер команды, K-действие, выполняемое головкой, m- номер следующей команды, подлежащей выполнению.

Существует всего шесть команд машины Поста (рис. 3.2).

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

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

1) на n-м месте команда с номером n;

2) номер m каждой команды совпадает с номером какой-либо команды списка.

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

1) останов по команде “стоп”; такой останов называется результативным и ука­зывает на корректность алгоритма (программы);

2) останов при выполнении недопустимой команды; в этом случае останов назы­вается безрезультативным;

3) машина не останавливается никогда; в этом и в предыдущем случае мы имеем дело с некорректным алгоритмом (программой).

 

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

 

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

Рассмотрим реализацию некоторых типичных элементов программ машины Поста.

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

 

Рис. 3.3. Пример элемента программы машины Поста

 

2. Покажем, как можно воспользоваться командой условного перехода для ор­ганизации циклического процесса. Пусть на ленте имеется запись из нескольких меток подряд и головка находится над самой крайней меткой справа. Требуется перевести головку влево до первой пустой позиции.

Программа будет иметь следующий вид:

 

Команда условного перехода является одним из основных средств организации циклических процессов, например, для нахождения первой метки справа (или слева) от головки, расположенной над пустой клеткой; нахождение слева (или справа) от головки пустой клетки, если она расположена над меткой и т.д.

3. Остановимся на представлении чисел на ленте машины Поста и выполнении операций над ними.

Число k представляется на ленте машины Поста идущими подряд k + 1 метками (одна метка означает число “0”). Между двумя числами делается интервал как минимум из одной пустой секции на ленте. Например, запись чисел 3 и 5 на ленте машины Поста будет выглядеть так:

 

Используемая в машине Поста система записи чисел яв­ляется непозиционной.

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

 

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

Программа, добавляющая к числу метку слева, имеет вид:

 

 

Программа, добавляющая к числу метку справа, имеет вид:

 

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

 

Машину Поста можно рассматривать как упрощенную модель ЭВМ. В самом деле, как ЭВМ, так и машина Поста имеют:

· неделимые носители информации (клетки – биты), которые могут быть за­полненными или незаполненными;

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

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

Машина Тьюринга. Машина Тьюринга подобна машине Поста, но функционирует несколько иначе.

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

Читающая и пишущая головка может читать буквы рабочего алфавита А=[а0,а1,...,аt}, стирать их и печатать. Каждая ячейка ленты в каждый момент времени занята буквой из множества А. Чаще всего встречается буква a0– “пробел”. Головка находится в каждый момент времени над некоторой ячейкой ленты – текущей рабочей ячейкой. Лентопротяжный механизм может перемещать ленту так, что головка оказывается над соседней ячейкой ленты. При этом возможна ситуация выхода за левый край ленты (ЛК), которая является аварийной (недопустимой), или машинного останова (МО), когда машина выполняет предписание об остановке.

Порядок работы МТ (с рабочим алфавитом а0,а1,...,аtи состояниями q0,q1,...,qs) описывается таблицей машины Тьюринга. Эта таблица является матрицей с че­тырьмя столбцами и (s+1)(t+1) строками. Каждая строка имеет вид:

qi aj vij qij, где 0 Ј I Ј s, 0 Ј j Ј t, qijО{q0,q1,...,qs}.

Здесь через vijобозначен элемент объединения алфавита {а0,а1,...,аt} и множест­ва предписаний для лентопротяжного механизма: g – переместить ленту влево, r -переместить ленту вправо, s – остановить машину; vij– действие МТ, состоящее либо в занесении в ячейку ленты символа алфавита а0,а1,...,аt, либо в движении головки, либо в останове машины; qijявляется последующим состоянием.

МТ работает согласно следующим правилам: если МТ находится в состоянии qi, головка прочитывает символ ajв рабочей ячейке. Пусть строка qi aj vij qij, начинаю­щаяся с символов qi aj, встречается только один раз в таблице. Если vij– буква рабочего алфавита, то головка стирает содержимое рабочей ячейки и заносит туда эту букву. Если vij– команда r или g для лентопротяжного механизма, то лента сдвигается на одну ячейку вправо или влево (если не происходит выхода за левый край ленты) соответственно. Если vij = s, то происходит машинный останов.

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

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

Рассмотрим примеры нескольких схем машины Тьюринга.

1. Алгоритм прибавления единицы к числу n в десятичной системе счисления.

Дана десятичная запись числа n (т.е. представление натурального числа n в деся­тичной системе счисления); требуется получить десятичную запись числа n+1.

Очевидно, что внешний алфавит МТ должен состоять из десяти цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и символа пробела _. Эти цифры записывают по одной в ячейке (подряд, без пропусков).

Оказывается достаточным иметь два внутренних состояния машины: q1и q2.

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

 

 

2. Алгоритм записи числа в десятичной системе счисления.

Дана конечная последовательность меток, записанных в клетки ленты подряд, без пропусков. Требуется записать в десятичной системе число этих меток (пересчитать метки).

Суть алгоритма может состоять в том, что к числу 0, записанному на ленте в начале работы машины, машина добавляет 1, стирая метку за меткой, так что вместо нуля возникает число 0+k.

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

Нормальные алгоритмы Маркова. Для формализации понятия алгоритма российский математик А.А.Марков предложил использовать ассоциативные исчисления.

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

Рассмотрим два слова N и М в некотором алфавите А. Если N является частью М, то говорят, что N входит в М.

Зададим в некотором алфавите конечную систему подстановок N-М, S-Т,..., где N, М, S, Т,... – слова в этом алфавите. Любую подстановку N-М можно приме­нить к некоторому слову К следующим способом: если в К имеется одно или не­сколько вхождений слова N, то любое из них может быть заменено словом М, и, наоборот, если имеется вхождение М, то его можно заменить словом N.