Глава 1

Вычислительные модели

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

1.1 Машина Тьюринга:
Определение пределов вычислений

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

Машина Тьюринга концептуально состоит из:

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

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

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

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

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

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

1.2 Модель фон Неймана:
Архитектура современных компьютеров

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

Центральный процессор (ЦП): «мозг» компьютера, отвечающий за выполнение инструкций. ЦП далее делится на: Блок управления (CU): Извлекает инструкции из памяти, декодирует их и генерирует сигналы управления, необходимые для координации других компонентов системы. Арифметико-логическое устройство (АЛУ): Выполняет арифметические (сложение, вычитание, умножение, деление) и логические (И, ИЛИ, НЕ) операции над данными.
Блок управления (БУ): Извлекает инструкции из памяти, декодирует их и генерирует сигналы управления, необходимые для координации других компонентов системы.
Арифметико-логическое устройство (АЛУ): Выполняет арифметические (сложение, вычитание, умножение, деление) и логические (И, ИЛИ, НЕ) операции над данными.
Память: Используется для хранения как обрабатываемых данных, так и инструкций программы. Эта память концептуально организована как последовательность мест, каждое из которых идентифицируется уникальным адресом. Память обеспечивает прямой доступ к любому месту за относительно постоянное время (оперативная память или ОЗУ).
Устройства ввода/вывода (I/O): Разрешают компьютеру взаимодействовать с внешним миром. Устройства ввода позволяют вводить данные и команды в компьютер (например, клавиатура, мышь), а устройства вывода позволяют отображать или передавать результаты обработки (например, монитор, принтер).
Шина: Система проводников (проводов или дорожек на печатной плате), которая служит каналом связи между различными компонентами системы. Обычно существует три основных типа шин: Шина данных: Переносит данные между ЦП, памятью и устройствами ввода-вывода. Адресная шина: Указывает адрес памяти или устройства ввода-вывода, к которому осуществляется доступ. Шина управления: Передает сигналы управления, которые координируют операции между различными компонентами.
Шина данных: Переносит данные между ЦП, памятью и устройствами ввода-вывода.
Адресная шина: Указывает адрес памяти или устройства ввода-вывода, к которому осуществляется доступ.
Шина управления: Передает сигналы управления, которые координируют операции между различными компонентами.

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

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

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

1.3 Теория информации Шеннона:
Измерение неопределенности

Одновременно с разработкой первых компьютеров и формализацией вычислительных моделей, новаторская работа Клода Шеннона по теории информации , опубликованная в его основополагающей статье 1948 года «Математическая теория коммуникации», обеспечила строгую теоретическую основу для количественной оценки и понимания концепции информации. Эта работа оказала глубокое влияние не только на информатику, но и на телекоммуникационную технику и многие другие области.

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

Математически количество информации (H) о событии с вероятностью p наступления определяется как:

H = -log₂(p)

Где логарифм имеет основание 2, что отражает двоичную природу бита.

Теория информации Шеннона предоставила фундаментальные математические инструменты для:

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

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

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

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