Книга: Размышления о думающих машинах. Тьюринг. Компьютерное исчисление
ЛУННАЯ МИССИЯ «АПОЛЛОН-11»
ЛУННАЯ МИССИЯ «АПОЛЛОН-11»
Один из самых интересных примеров машины Тьюринга — миникомпьютер миссий «Аполлон», организованных 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. Решить уравнение.
— Шаг 4. Подставить полученную величину в одно из двух уравнений, где выделена одна неизвестная.
— Шаг 5. Решить получившееся в предыдущем пункте уравнение.
— Шаг 6. Конец программы.
Эти заключения приводят нас к выводу о том, что компьютер представляет собой машину Тьюринга, работающую с алгоритмами. Когда решение задачи может быть выражено в виде алгоритма, считается, что задача разрешима. Швейцарский инженер Никлаус Вирт (р. 1934), автор языков программирования «Алгол», «Модула-2» и «Паскаль», участвовал в разработке определения программы в 1975 году. Согласно его определению, программа — соединение алгоритма с формой организации данных внутри программы; организация данных также получила название структура данных. Отсюда происходит знаменитое выражение Вирта: алгоритм + структура данных = программа.
- А-МАШИНА ТЬЮРИНГА
- ПАРАДОКС ЛЖЕЦА
- СОСТОЯНИЯ МАШИНЫ
- У-МАШИНА ТЬЮРИНГА. МОЖЕТ ЛИ МАШИНА БЫТЬ УНИВЕРСАЛЬНОЙ
- ЛУННАЯ МИССИЯ «АПОЛЛОН-11»
- АЛОНЗО ЧЁРЧ, ЛЯМБДА-ИСЧИСЛЕНИЕ И «ЛИСП»
- Новый синтаксис
- Проблема остановки
- ДРУГИЕ МАШИНЫ ТЬЮРИНГА
- ПРОБЛЕМА ОСТАНОВКИ. ПОЧЕМУ КОМПЬЮТЕР «ЗАВИСАЕТ»
- БЕСКОНЕЧНОСТЬ МАШИН ТЬЮРИНГА
- Современные компьютеры
- ПОСТРОИТЬ МАШИНУ ТЬЮРИНГА
- СОЗДАНИЕ МАШИНЫ ТЬЮРИНГА С ПОМОЩЬЮ ИГРЫ «ЖИЗНЬ»
- АМЕРИКАНСКОЕ ПРИКЛЮЧЕНИЕ
- Цели и миссия проекта SAP
- Глава 33 Секретная миссия
- Миссия, видение и ценности
- 7.4.1. Миссия кадровой службы
- Миссия и цели проекта SAP
- Это непонятное слово – миссия
- Миссия
- 9.3. Конус – миссия сокрыта до ее завершения
- Миссия выполнима?
- Миссия компании
- Федеральная торговая комиссия
- 11.3. Архимед и Аполлоний