Файл: История развития средств вычислительной техники.(Счет в древнем мире).pdf

Таким образом, чтобы задать машину Тьюринга, надо указать следующие объекты:

• произвольное конечное множество A (алфавит); его элементы называются символами;
• некоторый выделенный символ a0 из A (пробел, или пустой символ);
• конечное множество S, называемое множеством состояний;
• некоторое выделенное состояние s0 из S, называемое начальным;
• таблицу переходов, которая определяет поведение машины в зависимости от состояния и текущего символа (см. ниже);
• некоторое подмножество F, входящее в S, элементы которого называются заключительными состояниями (попав в такое состояние, машина останавливается).

Таблица переходов устроена следующим образом: для каждой пары (текущее состояние, текущий символ) указана тройка (новое состояние, новый символ, сдвиг). Здесь сдвиг одно из чисел -1 (влево), 0 (на месте) и 1 (направо). Таким образом, таблица переходов есть функция типа S x A -> S x A x {-1,0,1}, определенная на тех парах, в которых состояние не является заключительным.

Остается описать поведение машины Тьюринга. В каждый момент имеется некоторая конфигурация, складывающаяся из содержимого ленты (формально говоря, содержимое ленты есть произвольное отображение Z -> A), текущей позиции головки (некоторое целое число) и текущего состояния машины (элемент S). Преобразование конфигурации в следующую происходит по естественным правилам: мы смотрим в таблице, что надо делать для данного состояния и для данного символа, то есть выясняем новое состояние машины, меняем символ на указанный и после этого сдвигаем головку влево, вправо или оставляем на месте. При этом если новое состояние является одним из заключительных, работа машины заканчивается. Остается договориться, как мы подаем информацию на вход машины и что считается результатом ее работы. Будем считать, что алфавит машины, помимо пробела, содержит символы 0 и 1 (а также, возможно, еще какие-то символы). Входом и выходом машины будут конечные последовательности нулей и единиц (двоичные слова). Входное слово записывается на пустой ленте, головка машины ставится в его первую клетку, машина приводится в начальное состояние и запускается. Если машина останавливается, результатом считается двоичное слово, которое можно прочесть, начиная с позиции головки и двигаясь направо (пока не появится символ, отличный от 0 и 1).

Детерминированность машины Тьюринга породила ложные представления об истинных возможностях компьютеров и воззрениях самого Алана Тьюринга.Немногие знают, что в 1951 г. Тьюринг выступил в Манчестере с лекцией "Интеллектуальные машины. Еретическая теория" (развитие его работы 1948 г.). Он сказал: "Моя точка зрения такова: можно сконструировать машины, которые весьма близко смогут моделировать поведение человеческого разума. Порой они будут ошибаться, а иногда смогут выдавать новые весьма интересные утверждения, и в целом их выводы будут заслуживать внимания в такой же степени, как и сделанные человеческим разумом. Данное утверждение основывается на ожидаемой большой частоте истинных утверждений, и я думаю, что ему нельзя дать строгое обоснование".

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

Машина Поста.

Эмиль Пост предложил абстрактную вычислительную машину - машину Поста. Она отличается от машины Тьюринга большей простотой. Обе машины "эквивалентны" и были созданы для уточнения понятия "алгоритм".

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

Работа машины Поста определяется программой с конечным числом строк. Программы состоит из команд, имеющих по 3 поля, в которых записываются: № команды, операция и отсылка.

Для машины Поста определены операции 6 видов:

1. Движение головки на 1 клетку вправо.
2. Движение головки на 1 клетку влево.
3. Запись метки.
4. Удаление метки.
5. Условный переход по метке.
6. STOP - остановка (завершение работы машины Поста);

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

• работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
• работа может закончиться командой Stop;
• работа никогда не закончится.

Выделим основные успехи электромеханического этапа развития вычислительной техники. Прежде всего, существенно возросли производительность и надежность вычислительной техники, на что повлияла не только более быстрая элементная база, но и сокращение ручного труда. Во-вторых, на данном этапе развития вычислительной техники происходит индустриализация обработки информации. Особенно это было заметно по концентрации вычислительных мощностей в СССР, начиная с создания в 30-х годах машинно-счетных стаций, которые к 1936 году превратились в крупнейшие в мире предприятия механизированного учета. Впоследствии эти станции явились основой создания современных вычислительных центров и коллективного пользования вычислительных центров, оборудованных ЭВМ различных типов и классов. Наконец, на электромеханическом этапе была реализована идея Бэббиджа создания универсальной вычислительной машины с программным управлением, по сложности соизмеримая с наиболее сложными техническими системами того времени. Уже на этом этапе выявляется зависимость возможностей вычислительной техники от ее системной сложности; многие наработки данного этапа легли в основу развития современного этапа развития ВТ - электронного.

8 Аналоговые вычислительные машины

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

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

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

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

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

Все АВМ можно разделить на две основных группы:

• Специализированные — предназначены для решения заданного узкого класса задач (или одной задачи);
• Универсальные — предназначены для решения широкого спектра задач.

9 Релейные вычислительные машины

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

В 1910 году у Готтхильфа Бетуландера (Gotthilf Betulander), инженера Royal Telegrafverket — государственной корпорации, контролировавшей большую часть шведского телефонного рынка (в течение десятилетий — почти весь), — возникла идея. Он верил, что может очень сильно улучшить эффективность операций Telegrafverket за счёт строительства автоматических коммутационных систем, полностью основанных на реле. Точнее, на релейных матрицах: решётках из стальных прутьев, подключённых к телефонным линиям, с реле в местах пересечения прутьев. Такой коммутатор должен работать быстрее, надёжнее и быть проще в обслуживании по сравнению с системами на основе скользящих или вращающихся контактов.

Более того, Бетуландер придумал, что можно выделить части системы, отвечающие за выбор и соединение, в независимые релейные схемы. А оставшаяся часть системы должна использоваться только для установки речевого канала, а затем освобождаться для обслуживания другого вызова. То есть Бетуландер пришёл к идее, которую позднее назвали «общее управление» (common control).

Схему, хранящую номер входящего вызова, он назвал «рекордер» (другой термин — регистр). А схему, которая находит в решётке и «помечает» доступное подключение, назвал «маркер».

В 1918-м Бетуландер узнал об американском нововведении: координатном коммутаторе, созданном инженером Bell Джоном Рейнольдсом пять лет назад. Этот коммутатор очень походил на разработку Бетуландера, но в нём использовалось n + m реле для обслуживания n + m узлов матрицы, что было гораздо удобнее для дальнейшего расширения телефонных станций. При установке соединения удерживающая рейка зажимала «пальцы» из рояльных струн, а выбирающая рейка перемещалась по матрице для соединения с другим вызовом. На следующий год Бетуландер внедрил эту идею в конструкцию своего коммутатора.

В 1936-м Клоду Шеннону было всего 20 лет, но он уже окончил Мичиганский университет со степенью бакалавра по двум специальностям: электротехнике и математике.

Шеннон сконцентрировался на преобразовании данных с бумажной ленты в инструкции для «мозга», и за эту операцию отвечала релейная схема. Он обратил внимание на соответствие между структурой схемы и математическими структурами булевой алгебры, которую он изучал в выпускном классе в Мичигане. Это алгебра, чьими операндами были ИСТИНА и ЛОЖЬ, а операторами —И, ИЛИ, НЕ и т. д. Алгебра, соответствовавшая логическим утверждениям.

Потратив лето 1937-го на работу в Bell Labs на Манхэттене (идеальное место для размышлений над релейными схемами), Шеннон написал магистерскую диссертацию под названием «Символический анализ релейных и коммутационных схем» (A Symbolic Analysis of Relay and Switching Circuits). Наряду с работой Алана Тьюринга, созданной за год до этого, диссертация Шеннона сформировала фундамент науки вычислительных машин.

Шеннон обнаружил, что систему уравнений пропозициональной логики можно напрямую механистически преобразовать в физическую схему релейных переключателей. Он заключил: «Фактически любую операцию, которая может быть описана конечным количеством шагов с использованием слов ЕСЛИ, И, ИЛИ и т. д., можно автоматически выполнить с помощью реле». Например, два управляемых реле переключателя, соединённые последовательно, формируют логическое И: ток будет течь по главному проводу только тогда, когда оба электромагнита активированы на закрытие переключателей. В то же время два реле, соединённые параллельно, формируют ИЛИ: ток течёт по главной схеме, активированный одним из электромагнитов. Выходные данные такой логической схемы могут, в свою очередь, управлять электромагнитами других реле, чтобы получить более сложные логические операции вроде (А И Б) или (В И Г).

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

Джордж Штибиц (George Stibitz), исследователь из математического отдела штаб-квартиры Bell Labs на Манхэттене, тёмным ноябрьским вечером 1937-го принёс домой странный набор оборудования. Сухие аккумуляторные ячейки, две маленькие лампочки для аппаратных щитов и пару плоских реле Type U, найденных в мусорном баке. Добавив несколько проводов и кое-какой хлам, он собрал устройство, которое могло складывать два одноразрядных двоичных числа (представляемых с помощью наличия или отсутствия входного напряжения) и выводить двухразрядное число с помощью лампочек: единица — включено, ноль — выключено.

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

Сначала баловство Штибица с реле вызвало мало интереса у руководства Bell Labs. Но в 1938 году глава исследовательской группы спросил Джорджа, могут ли его калькуляторы использоваться для арифметических операций с комплексными числами (например, a + bi, где i — квадратный корень отрицательного числа). Оказалось, несколько вычислительных отделов в Bell Labs уже стонали из-за того, что им постоянно приходилось умножать и делить такие числа. Умножение одного комплексного числа требовало четырёх арифметических операций на настольном калькуляторе, деление — 16 операций. Штибиц сказал, что может решить проблему, и разработал схему машины для таких вычислений.

Окончательную конструкцию, которую воплотил в металле телефонный инженер Сэмюэль Уильямс (Samuel Williams), назвали Complex Number Computer — или Complex Computer для краткости — и запустили в работу в 1940-м. Для вычислений использовалось 450 реле, промежуточные результаты сохранялись в десяти координатных переключателях. Данные вводились и принимались с помощью рулонного телетайпа. В департаментах Bell Labs установили три таких телетайпа, что говорит о больших потребностях в вычислительных мощностях. Реле, матрица, телетайпы — во всех отношениях это был продукт системы Bell.