Тьюринг. Компьютерное исчисление

Один из самых интересных примеров машины Тьюринга — миникомпьютер миссий «Аполлон», организованных NASA для доставки человека на Луну. Это была машина Тьюринга, разработанная в Массачусетском технологическом институте для навигации и прилунения. Среди множества мини-компьютеров, созданных для разных миссий, AGC (Apollo Guidance Computer — бортовой компьютер «Аполлона») был самым популярным. Программа, с помощью которой можно моделировать работу мини-компьютера миссий «Аполлон», а также выполнять современные программы, написанные для Windows, Linux, Mac Os или другой операционной системы, называется Virtual AGC. Она написана на Ассемблере, низкоуровневом языке программирования, в связи с тем что память мини-процессора AGC — всего 38912 символа длиной 15 бит (последовательность 15 единиц и нулей). Программа моделирует виртуальный компьютер в машине AGC, выполняющий программу, хранящуюся в его памяти. На лунном модуле мини-компьютер AGC использовал программу Luminary, в то время как на командном модуле применялась программа Colossus. Обе они доступны на симуляторе.

Модель мини-компьютера миссий «Аполлон» на эмуляторе Virtual AGC.

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

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

— Во-вторых, шаги или правила должны быть определены четко и однозначно. Приведем простой школьный эксперимент для «измерения числа я»: 1) обмотайте банку бумажной лентой, лишний материал ленты обрежьте; 2) снимите бумажную ленту и измерьте ее длину; 3) поместите банку между двумя книгами и измерьте расстояние между краями книг, соприкасающимися с банкой, для получения диаметра; 4) вычислите частное длины и диаметра. Полученная величина и будет я.

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

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

Например, процедура стирки состоит из следующих шагов.

— Шаг 1. Разобрать одежду по цветам. Белые вещи и вещи светлых тонов должны стираться отдельно от цветных и темных вещей.

— Шаг 2. Прочитать этикетки на одежде, чтобы выяснить максимальную температуру и способ стирки (а также сушки, глажки и так далее).

— Шаг 3. Насыпать в лоток стиральной машины порошок.

— Шаг 4. Уложить одежду в стиральную машину. Выбрать соответствующую программу и температуру.

— Шаг 5. Достать выстиранную одежду.

— Шаг 6. Конец программы.

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

— Шаг 1. В обоих выражениях выделить одну неизвестную.

— Шаг 2. Уравнять выражения.

— Шаг 3. Решить уравнение.