История развития вычислительной техники 

Пальцы, камешки и счёты.

  Развитие  вычислительной "техники" шло  паралельно с развитием понятия  числа. Исторически первым был  пальцевый счёт - для небольшого  числа предметов. Даже счёт  на пальцах стал возможен после  того, как сформировалась абстракция  числа - когда люди осознвли, что два дерева и две овцы имеют общее ,их число - два.  
  Возникновение "следующего поколения" - абак, русские и китайские счёты, стало возможным после изобретения позиционной системы счисления (до этого были непозиционные системы, например римская, иероглифическая, древнеславянская, алфавитная и т.д.)  
  Позиционная десятичная система с нулём впервые появилась около 500 г. н.э. в Индии. Разработка алгоритмов сложения чисел позволила сконструировать первые механические устройства для сложения многозначных чисел - счёты и т.п. Развитие механики способствовало созданию новых механизмов, в том числе - счётных устройств. Начало таким устройствам положил французский математик Блез Паскаль, который в середине 17^го века изобрёл и построил счётную машину.  
  Механические вычислительные машины стали быстро совершенствоваться с появлением в начале 18^го века зубчатых шестерёнок и реек. В конце 19^го века появился арифмометр.  
  Большая заслуга в его создании принадлежит русскому инженеру Однеру - основной частью арифмометра было "Колесо Однера", использовавшееся во всех поздних конструкциях арифмометра. Одновременно шло развитие логических основ вычислительных устройств.  
  Англичанин Чарльз Беббидж в середине 19^го века создал в теории "ананлитическую машину", способную производить серию арифметических действий в определённой последовательности. Он ввёл(говоря современным языком) понятия данных, команд, цикла, ветвления. Но реализовать до конца свои замыслы Бэббидж не смог - небыло ещё технических возможностей.  
  Только в 20 веке с появлением электромеханических реле стало возможным реализовать эти идеи. Ввод данных осуществлялся с помощью перфокарт, изобретённых в конце 19 века американцем Германом Холлеритом, действия с числами выполнялись логическими схемами, идеи которых были заложены английским математиком Джоном Булем.  
  Вторая мировая война ускорила развитие электронной техники. Появились первые электронные лампы, логические схемы, усилители, тригеры и т.д. Технически возможным стало создание электронных вычислительных машин (ЭВМ).  
  Считается, что первая ЭВМ, выполнявшая вычисления с помощью электронных устройств появилась в США в 1946 году. В том же году появилась научная статья трёх американских математиков - фон-Неймона, Голдстайна и Бернса, в которой были изложены основныепринципы построения универсальной ЭВМ, которые позднее получили название принципов фон-Неймона.  
  Первая советская вычислительная машина была построена в Киеве под руководством академика Лебедева 1951-52 гг. Она называлась МЭСМ - малая электронно-счётная машина. Несколько позже была создана БЭСМ - большая электронно-счётная машина. Для того времени это была уникальная машина. Она занимала большой зал, для своего обслуживания требовала множество людей: инженеров, операторов, программистов.  
  Кроме БЭСМ, ставшей родоночальницей целой серии машин (БЭСМ-2, 4, 6), появились серии М (м-20, 220, 222), Минск (Минск 2, 22, 32), Урал (Урал 2, 4). Позже их вытеснили машины серии ЕС, которые во многом были скопированы с американской техники фирмы IBM (в то время она выпускала БЭСМ). Стали появляться и небольшие машины, Мир, Электроника.  
  Наконец, в 80^х годах появились мини- и микрокомпьютеры - прообразы современных персональных ЭВМ.  
  Лавинообразный рост производства и использования персональных ЭВМ мы наблюдаем сейчас. Можно считать, что всё развитие ЭВМ уложилось в последние 50 лет - очень небольшой в сущности период.

Принципы  фон-Неймана 

1) Принцип произвольного  доступа к основной  памяти.

  Структурно, основная память состоит из  одинаковых элементов (ячеек).  
  Процессору в любой момент времени доступна любая ячейка для чтения или записи информации, причём время поиска ячейки одно и то-же для любой из них.  
  Чтобы обеспечить доступ к ячейкам памяти, каждая из них имеет свой номер - число от 0 до N-1. Этот номер называется адресом ячейки. Общее число ячеек (N), называют объёмом основной памяти.  
  Максимальное число одновременно адресуемых ячеек зависит от технических параметров компьютера.Для современных компьютеров, стандарт - 16-бит(реальный) режим: 1МБайт, из которых доступно пользователю 640 кБайт основной памяти, 32-бит(защищённый) режим: 4ГБайт одновременно загруженных данных.

2) Принцип хранимой  программы.

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

3) Принцип универсальности.

  Универсальность  ЭВМ - отличает её от специальных  счётных устройств, предназначенных  для решения одного типа задач.  
  Информация, находящаяся в основной памяти, не имеет признаков принадлежности к определённому типу, т.е. по содержимому ячейки ЭВМ, вообще говоря, нельзя установить, что в ней хранится. Это означает, что команды могут рассматриваться как данные, соответственно над ними можно производить какие-то действия. На самом деле так и происходит при выполнении программы на машинном уровне.  
  Кроме того, сама программа может быть результатом работы другой программы. На этом основаны методы трансляции с языка программирования высокого уровня.

Представление информации в ЭВМ. 
Системы счисления. 

  В большинстве  ЭВМ информация представляется  в двоичном виде(Существуют так-же  двоично-десятичные и троичные  ЭВМ). Это обусловлено, в основном, техническими особенностями - простой  реализации электронного устройства  с двумя(а не с десятью) устойчивыми  состояниями: есть сигнал - нет сигнала. Эти два состояния обозначаются символами 0 и 1.Каждый двоичный символ несёт 1 бит информации.  
  Любая информация в ЭВМ представляется последовательностью двоичных символов. Каждому символу внешнего алфавита(т.е. алфавита пользователя). каждой команде или элементу данных сопоставляется своя последовательность символов. Способ кодирования для нас сейча сне имеет значения, те более длина кода.  
  С помощью последовательности из 4^-х нулей и единиц можно закодировать 2⁴=16 символов. Увеличив длину последовательности до 8 символов ожно получить 2⁸=256. Этого вполне достаточно для кодирования символов внешнего алфавита(цифры, строчные и прописные буквы, специальные знаки и т.д.)  
  Поэтому размер ячейки в ЭВМ у современных машин равен восьми двоичным символам(разрядам). Единица информации, содержащая 8 двоичных символов называется байтом. Т.е. 1 байт = 8 бит. Это наименьшая адресуемая часть памяти машины. Однако многие данные и команды требуют больше места(в командах кроме кода операции нужны и адреса ячеек). Поэтому выделяют машинное слово, которое на разных ЭВМ может состоять из двух или четырех байт.

Кодирование текстовых данных

  Каждый символ  занимает 1 байт. Для кодирования  могут использоваться различные  стандарты. На IBM-совместимых ЭВМ - это ASCII (American Standart Code for Information Interchange - американский стандартный код для обмена информацией), на наших - КОИ-7, КОИ-8 (Коды для Обена Информацией, 7 и 8 битные).  
  ASCII - 7-разрядный код, т.е. стандарт задаёт тольк 128 символов. Восьмой бит используется для расширения таблицы (есть много разных вариантов), куда включают символы Кириллицы, псевдографику, математические символы и прочее.  
  Обычно код символа записывают не в двоичной, а в шестнадцатиричной системе счисления. При этом каждая четвёрка двоичных символов образует один шестнадцатиричный.

Дать Алгоритмы  перевода 10 -> 2 и т.д. 
 
  В 16-ричной системесчисления 16 циф. От 0 до 9 берутся из десятичной, остальные обозначаются латинскими буквами A(10), B(11), C(12), D(13), E(14), F(15).  
  Так что AC₁₆ = (10)*16+12=172₁₀

Кодирование целых чисел

  Кодиовать  числа можно "посимвольно", но это очень расточительно  (1 символ = 1 байт!).  
В принципе, для цифры достаточно 4 бит:  
 0 <=> 0000, 1 <=> 0001, 2 <=> 0010, ..., 9 <=> 1001. (Так называемое двоично-десятичное кодирование). Такое представление применяется в ряде случаев при обработке экономичесой информации (в языке КОБОЛ в частности). - Это кодирование не эффективно по памяти, поэтому в большинстве случаев используют двоичное кодирование.  
 Использование двоичной системы требует перевода вводимых чисел из 10-ной в двоичную при вводе и из двоичной в десятичную при выводе данных.  
 Это снижает эффективность, если необходимо вводить и выводить большие массивы информации при небольшом времени их обработки (как в экономических задачах).  
 Для представления дробных чисел существуют два варианта - с фиксированной и плавающей запятой.  
Для целых чисел используется первый вариант (точка фиксирована после целой части), для вещественных - второй вариант.

Кодирование вещественных чисел

 Максимальная  величина целого числа зависит от того, сколько места ему разрешено занять - байт, два байта или больше.  
Диапазон целого без знака:  
      от 0 до 2ⁿ-1, где n - общее число разрядов.  
т.е. от 0 до 255 (1 байт)  
       от 0 до 65535 (2 байта)  
 Обычно один разряд выделяется для знака числа, поэтому диапазон изменяется.  
Знаковое целое:  
 от -128 до 127 (1 байт)  
 от -32768 до 32767 (2 байта)  
 Т.к. диапазон целых чисел сравнительно небольшой (хотя в некоторых языках есть и длинное целое), для расчётов используются вещественные числа, которые кодируются в форме с плавающей запятой.  
 В этом случае число представляется в виде ±M*2^±p.  
В машинном слове фиксируется расположение всех элементов: мантиссы (±M - целое со знаком) и порядка (±p - целое со знаком).  
  При выполнении операций учитывается, в каком виде представлены числа. Операции над целыми числами реализуются аппаратно, а над вещественными - программно. Для ускорения вычислений используется математический сопроцессор (дополнительно к основному процесоору), который выполняет арифметические операции с вещественными числами аппаратно.  
 Диапазон представления числа с плавающей запятой намного больше, чем целого. Обычно вещественному числу выделяется 4 байта (32 бита).  
Тогда диапазон чисел - от -3,4*10³⁸ до 3,4*10³⁸  
Это не значит, что можно представить любое число из этого диапазона. Фактически представимой оказывается дискретная последовательность чисел. Шаг дискретизации зависит от количества знаков мантиссы.  
       
 Например после 0 следует число ~3,4*10^-38, внутри вещественных чисел нет. Из формы представления возникают следующие эффекты:

1. Ошибка округления. => вычислительные алгоритмы не должны допускать роста погрешности вычислений из-за ошибок округления.
2. Потеря значимости: число стало таким маленьким, что не может быть представлено в ЭВМ - оно превращается в "машинный ноль".
3. Переполнение (эффект, обратный потере значимости): число слишком велико.

 Ошибки  округления  
 Что почучится, если к миллиону прибавить одну миллионную?  
 1 000 000.000 001 - 13 знаков, в мантиссу не поместится, следовательно, миллион не изменится - вроде бы естественно. А если к миллиону прибавить модну миллионную милион раз? В математике - 1 000 001, в ЭВМ останется тот-же миллион.  
 А если складывать в другую сторону: сначала миллионные доли - получим 1, потом уже прибавим 1 000 000 - получится правильно!  
 Следовательно коммутативность сложения в ЭВМ нарушается! (от перемены мест слагаемых, сумма изменяется!!)  
 Правило: При большом числе слагаемых сумммрование начинаем с наименьших. 
 
 Потеря значимости и переполнение  
 При вычитании двух близких чисел может получиться "машинный ноль". Что может сделать невозможным последующие вычисления.  
 Пример: Для вычисления производной f(X) в т. Xo нужно вычислить

 
 Сначала всё хороше, потом приходится делить друг на друга маленькие значения - начинает растипогрешность, процесс  разбалтывается и наконец X-Xo - превращается в машинный ноль. Если числитель при этом не ноль, то теоретически получается бесконечность - переполнение.  
 Переполнение может получиться и при вычислении по формулам типа  
       
 где n - большое. Если сначала вычислять сумму, а потом умножать - переполнение. В этом случае используют формулу в преобразованном виде  
       
 Уменьшая каждое слагаемое, мы избавляемся от переполнения. Но это значит, что нарушается дистрибутивный закон L(a+b)=La+Lb.  
 Задание: Придумайте пример нарушения ассоциативного закона (a+b)+c=a+(b+c). 
 
 Как правило, диапазона и точности ЭВМ хватает с избытком, за исключением случаев, когда при вычислениях необходимо получить результат с точностью, близкой или большей того, что даёт ЭВМ  
(не 10^-3, а 10^-6 при машинной точности 10^-7). Выход - использовать типы данных двойной точности (при этом увеличивается и диапазон). Такие типы есть в большинстве языков, (Fortran, Pascal, C).  
 Представление команд  
 Машинные команды представляются в двоичном виде и состоят из двух основных полей - поля операции и поля адреса. В поле операции указывается двоичный код команды, в поле адреса - номера ячеек, над которыми должнабыть выполнена операция.Операции выполняет процессор (АЛУ)  
 Команды могут быть одноадресными, двухадресными, трехадресными. Большинство арифметических опрераций используют регистры процессора и могут не содержать адресов ячеек. По этому в принципе можно обойтись одноадресными командами.  
 Пример:  
    а) перслать число из ячейки A1 в регистр прочессора  
    б) сложить содержимое регистра с содержимым A2  
    в) переслать результат в ячейку A3  
 Если результат участвует в следующей операции , то пункт в) можно не выполнять, а вычислять дальше  
 Машинные команды записываются набором нулей и единиц, что очень неудобно для восприятия. Использование восьмиричной и 16-ричной только облегчило но не решило проблему. Только создание языка ассемблера стало существенным шагом вперёд. В ассемблере каждая машинная команда получила буквенное обозначение, легкое для запомнинания.  
 Пример: (для x86-процессоров)  
     регистры: AX, BX, CX, DX (регистры общего назначения) и другие...  
     MOV - пересылка данных MOV AX,BX (AX:=BX)  
     Вместо адресов так-же используются символические имена  
     MOV AX,IDENT (AX:=IDENTR)  
 Конкретный адрес переменная получит при ассемблировании программы.

Структурные особенности современных  ЭВМ

 
 Адресация памяти (сегментный адрес, смещение)  
 Для адресации памяти в процессоре x86 используются 16-битные регистры. Но 16 бит позволяют получить значения от 0 до 65535 (64Кб), поэтому используется следующее:  
Адресация производится двумя регистрами.  
В одном из регистров хранится сегментный адрес, в другом - смещение.  
Это усложняет адресацию памяти , но упрощает аппаратную реализацию(Чтобы получить реальный адрес, нужно умножить сегментный адрес на 16 и сложить со смещением). Один и тот-же реальный адрес может быть представлен по разному.  
 Прерывания  
 В компьютере одновременно работает много устройств. Если бы центральный процессор всё время отслеживал их работу, времени на выполнение основной задачи оставалось бы на много меньше. Поэтому в современных ЭВМ реализован принцип прерываний.  
 Прерывание генерируется устройством в момент, когда необходимо вмешательство процессора - при нажатии клавиши, сигнале принтера, таймера и множества других причин.  
 Прерывание "прерывает" работу компьютера. Процессор запоминает место программы, на котором он остановился и некоторую вспомогательную информацию. Затем выполняется программа обработки прерывания и процессор возвращается к запомненному месту и продолжает выполнение программы.  
 Прерывание может быть и программным. При выводе данных на экран вызывается подпрограмма, которая находится в операционной системе. Этот вызов так-же реализуется через механизм прерываний.  
 Защита памяти  
 В современных операционных системах предусмотрен т.н. многозадачный режим, когда в памяти находится одновременно несколько программ. И даже если нет многозадачности, всёравно кроме основной программы в памяти постоянно находится множество других программ, в т.ч. BIOS(базовая система ввода-вывода), command.com(командный процессор), файловая оболочка NC и д.р.  
 Чтобы нечаянно не перезаписать данные чужой программы, реализуется защищённый режим, в котором пресекается выход программы за пределы отведённого ей адресного пространства. Такой механизм был реализован в больших ЭВМ, т.к. они изначально были ориентированы на многопользовательский режим.  
 Параллельная обработка  
 Для повышения быстродействия современные супер-ЭВМ снабжаются не одним, а несколькими десятками процессоров, которые работают одновременно. Это усложняет программирование, но в ряде решаемых научных задач (с большим количеством вычислений), повышает быстродействие. Элементарный пример: Требуется найти максимальное значение в каждой строке матрицы. Обычный алгоритм будет обрабатывать строки по очереди: 1, 2, 3...  
Для многопроцессорных ЭВМ алгоритм должен строиться по другому: каждый процессор ищет максимум в своей строке(примем, что строк меньше чем процессоров) - выигрыш очевиден.

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

  Понятие алгоритма  возникло задолго до появления  ЭВМ и стало одним из основных  понятий математики. Слово "алгоритм" произошло от имени среднеазиатского  математика IX века аль-Харезми и  сначала использовалось в математике  для обозначения правил выполнения  четырёх арифметических действий: сложения, вычитания, деления и умножения, которые предписывают определённую последовательность действий, благодаря которым по двум данным произвольным числам можно получить их сумму, произведение и т.д.  
  Математика располагает огромным количеством алгоритмов: вычисление квадратного корня, нахождение наибольшего общего делителя (алгоритм Евклида), алгоритм решения квадратного уравнения, вычисление площади фигур и т.д.  
  В математической энциклопедии 1977 года понятие "алгоритм" определяется следующим образом:  
  алгоритм - точное предписание, которое задаёт вычислительный процесс, начинающийся с произвольного исходного данного из совокупности всех возможных, и направленный на получение полностью определяемого этим данным результата.  
  Отметим два момента: 1) - для математики все алгоритмы носят вычислительный характер. Естественно, это определение устарело, т.к. в информатике существуют и нечисловые алгоритмы. 2) - понятие "алгоритм" даётся через понятие "предписание", а что такое "предписание"? Понятие "алгоритм" принадлежит к числу основных понятий математики и не допускает определения в терминах более простых понятий. Фактически в определении перечислены свойства алгоритма, которые отличают его от других предложений языка.  
  Для пояснения понятия "алгоритм" важное значение имеет определение понятия "исполнитель алгоритма".  
  Любой алгоритм предназначен для конкретного исполнителя. Этим исполнителем может быть человек, станок с ЧПУ, калькулятор, микроволновая печь, транслятор с некоторого алгоритмического языка и т.д. Для исполнителя следует чётко оговорить, какие предписания он понимает и умеет исполнять. Перечень таких предписаний называется множеством предписаний исполнителя. Для ЭВМ - это набор машинных команд, поэтому , строго говоря, когда мы набираем текст в текстовом редакторе, исполнителем является программа-редактор, которая умеет обрабатывать нажатия клавишь - для ввода символов, выделения, удаления, вставки фрагментов, установки шрифтов, форматирования и т.д.  
  Пример исполнителя - Черепашка. Исполнитель Черепашка понимает язык Лого, придуманный Пейпертом.  
  Базовые предписания:  
  вперёд число  
  назад число  
переместиться на заданное число шагов (единиц длины)  
  направо число  
  налево число  
повернуть на заданное число градусов  
  При движении черепашки за ней остаётся след (хвост играет роль пера). Чтобы след не оставался, следует выполнить команду поднять хвост. Теперь след появится только после выполнения команды опустить хвост.  
  Пример алгоритма:

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

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

  1. Массовость алгоритма. Алгоритм должен быть пригодным для решения задач с любыми исходными данными из некоторого множества. Формально множество может состоять из одного элемента, но фактически это свойство означает пригодность алгоритма для некоторого класса исходныйх данных. Например, алгоритм поиска НОД применим к любой паре натуральных чисел, а не только к числам 51 и 34.  
  Будем считать, что для каждого алгоритма существует свой класс объектов, допустимых в качестве исходных данных. Тогда св-во массовости означает применимость алгоритма ко всем объектам этого класса. А количество объектов класса (конечное или бесконечное) - свойство самого класса исходных данных.  
  С массовостью связаны трудности, возникающие при доказательстве правильности алгоритма - для бесконечного числа исходных данных его нельзя проверить выполнением.  
  Пример:  
   
   
  Доказать, что последовательность сходится к единице.  
  Например n=17:  
   
  2. Понятность алгоритма. Для данного исполнителя - каждое предписание должно входить в систему команд исполнителя. Исполнитель должен знать как выполнить каждое предписание. Нарушение этого принципа вызывает диагносту ошибки типа "не понимаю", или "не могу выполнить".  
  3. Дискретность алгоритма. Алгоритм состоит из конечного числа шагов, каждый из которых начинается только после завершения предыдущего. Это свойство может нарушаться при выполнении программы на компьютерах с параллельной обработкой (матричные процессоры).  
  4. Результативность алгоритма. Алгоритм должен "выдавать" результат через конечное число шагов. При этом либо достигается конечная цель, либо выдаётся сообщение о невозможности решения задачи.  
  В математике существуют вычислительные процедуры, имеющие алгоритмический характер, но не обладающие свойством конечности. Например, есть алгоритм, позволяющий вычислить точное значение числа Пи.  
  Например:  
   
  Этот вычислительный процесс бесконечен, и если его оборвать на некотором шаге, мы получим приближенное значение Пи. Т.е. любой алгоритм должен быть не только потенциально, но и актуально выполнимым.  
  Проиллюстрируем понятие результативности алгоритма на следующем примере. Пусть возможными исходными данными являются слова (последовательности символов), состоящие только из букв {а} и {b}, и начинающиеся на {a}или{ba}.  
  Определим две операции над этими словами 
Операция V₁: aP Pb (где P - произвольное слово) 
Операция V₂: baP Paba 
Рассмотрим следующий алгоритм:  
  Начало  
      пока X aaP повторять  
          если X = aP то X := Pb  
          иначе если X = baP то X := Paba  
          иначе сотп  
      конец цикла пока  
      сообщить P  
  Конец  
  1) Пусть х = babaa = ba (baa), слово P будем брать в скобки 
ba(baa) (baa)aba = ba(aaba) (aaba)aba = aa(baaba) 
Алгоритм останавливается. Результат P = baaba.  
  2) Пусть x = baaba = 
= ba(aba) (aba)aba = 
= a(baaba) (baaba)b = 
= ba(abab) (abab)aba = 
= a(bababa) (bababa)b = 
= ba(babab) (babab) aba =... 
= ba (bababa) (bababa) aba 
Можно показать, что этот процесс никогда не закончится (т.е. никогда не возникнет слово, начинающее : с "aa", но к каждому промежуточному слову можно применить операцию V₁ либо V₂ (зацикливание)  
  3) Пусть x = abaab = 
= a(baab) (baab)b = 
= ba(abb) (abb)aba = 
= a(bbaba) (bbaba)b = bbabab 
Что будет дальше? Алгоритм остановится, но никакого результата мы не получим - его нет (безрезультативная остановка).  
  5. Определённость алгоритма. - заключается в однозначности выполнения всех предписаний алгоритма. Благодаря этому свойству процесс реализации алгоритма не зависит от конкретного исполнителя и рассчитан на число механическое выполнением автоматом, не обладающим "здравым смыслом".  
  6. Эффективность алгоритма. - заключается в том, что каждый шаг алгоритма должен быть выполнен точно и за конечное время. Например, условие типа: "Если в десятичном представлении числа встретится подряд три семёрки, то…" неэффективно, т.к. его проверка может занять бесконечное время.  
  Неэффективным может быть и алгоритм, требующий, вообще говоря, конечного, но очень большого числа шагов, так что его выполнение займёт неприемлемо большое время (например, 100лет). К таким алгоритмам относится в частности, алгоритм перебора большого количества вариантов. Однако развитие вычислительной техники может сделать неэффективный алгоритм - эффективным (или же следует искать более эффективный алгоритм).

Уточнение понятия алгоритма. Машина Тьюринга.

  Прогресс в развитие математики и алгоритмических методов породил представление о том, что окончательным решением любой поставленной математической задачи должно быть её алгоритмическое решение.  
  Рене Декарт развивал аналитическую геометрию с намерением сделать геометрию доступной алгебраическим методам вычислений, что позволило существенно продвинуться по пути алгоритмизации геометрии.  
  Исааку Лейбницу принадлежит первая попытка придумать автоматически работающую машину для решения алгоритмических проблем.  
  Давид Гильберт знаменит постановкой в начале ХХ века целого рода проблем. В ряде задач требовалось построить некоторый алгоритм и т.д.  
  Со временем пришло понимание того, что алгоритмические методы не являются универсальными. Примеры даёт та же математика: большинство теорем, которые доказывают существование чего-либо, не дают алгоритма построения этого чего-либо.  
  Начиная с 1935 года был предложен род формальных определений алгоритма, который бы обладал всеми свойствами интуитивно понимаемого алгоритма. Относительно всех уточнений была доказана их эквивалентность. Мы рассмотрим одно из них, предложенное Тьюрингом.  
  Машина Тьюринга - это некоторое воображаемое устройство, которое тем не менее можно представить в виде некоторого гипотетического механизма. Его основа - бесконечная лента, разделённая на ячейки.  
   
  a₀ - "пустой" символ  
  В каждую ячейку можно записать один символ из некоторго алгоритма A = {a₀}{a₁, ... ,a_n} Запись/чтение производится с помощью головки, которая в каждый данный момент времени находится над некоторой ячейкой ленты. Головка с помощью исполнительного мезанизма может перемещаться вдоль ленты "шагами" по одной ячейке.  
  Исполнительный механизм может находиться в одном из состояний {q₀,q₀, ... q_s}. Алгоритм работы машины Тьюринга описывается матрицей, каждая строка которой имеет формат:  
   
  В матрице перечислены все варианты сочетаний состояние - символ. Машина Тьюринга Т работает согласно следующим правилам.  
  Пусть Т находится в состоянии q, а читающая головка прочла на ленте символ a. Находим в таблице строку, которая начинается с символов qa (она единственна!). 
Если V A, то головка стирает содержимое рабочей ячейки и заносит туда символ V. 
Если V A, то он обозначает одно из следующих действий:  
V=L - сдвинуться влево, V=R - сдвинуться вправо, V=S - конец работы. Если V S , то машина Тьюринга после выполнения действия V переходит в состояние q'  
  Пример машины Тьюринга.  
  Опишем машину, в альфавите A = {a₀,a₁}, где a₀ - пустой символ, a₁="*" , которая сдвигается на 3 позиции вправо, записывает символ a₁ на ленту и останавливается.  
   
  Начинаем заполнять таблицу с начального состояния q₀

  Задача. Сконструировать в алфавите A = {0,1} с дополнением "пустого" символа (пробела) машину Тьюринга для решения следующей задачи: Если слово начинается с 0, то приписать в конце 1, а если с 1 - то 0.Начальное положение головки чтение/запись - перед словом.  
Используем более компактный способ записи:

Средства  записи алгоритмов.